{"id":"0f328b4f-6e4a-4040-a985-966daf1832f5","arxiv_id":"2608.05468","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Unless P=NP, A/E-design under partition constraints has no polynomial-time approximation better than 2^{poly(d)+(1−ε)B}; the proof reduces three-dimensional matching to the inverse matrix norm.","lead":"This paper proves that two classic experimental design problems, A-design and E-design, become computationally intractable when the chosen measurements must satisfy partition constraints. The proof gives a sharp contrast with D-design, where polynomial-time approximation algorithms are known, and settles an open question from recent work.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The paper gives a complete reduction from three-dimensional matching to A/E-design with partition constraints. I independently checked the block matrix in Equation (7) and the claimed inverse in Equation (8): the block multiplication is exact, including the lower-middle block where the identity A_x 1_n = A x is used. The Frobenius norm computation in Lemma 3.2 is consistent: the diagonal blocks contribute d, the top-middle block contributes nR^2, the bottom-left block contributes R^2||A_x||_F^2, and the bottom-middle block contributes R^4||Ax-1_m||^2. Completeness when Ax=1_m gives A(x) = d + R^2(n+m) = d + R^2(d-1) ≤ 2dR^2 for all R≥1, so E(x)≤2dR^2. Soundness when Ax≠1_m gives ||Ax-1_m||^2≥1, so the corresponding column of the inverse has squared norm at least R^4, implying E(x)≥R^4. The gap ratio is R^2/(2d). With R=2^{d^{c+1}}, the maximum bit length is B=2d^{c+1}+O(1), so the gap is 2^{B-O(log d)}. For any fixed polynomial p, choosing c so that p(d)≤d^c for large d yields p(d)+(1−ε)B < B - O(log d) for all sufficiently large d, because εB grows faster than d^c. Thus any algorithm with the claimed approximation guarantee would distinguish YES from NO instances, solving 3-DM. The only presentation issue is the order of quantifiers over c and the need to pad 3-DM instances to ensure d is large enough, but both are standard and do not affect correctness. The reader's identified weakest assumption, the block inverse, is indeed verified and not a source of failure.","tokens_in":5762,"tokens_out":21743,"duration_ms":177212,"concrete_test":"Run an independent symbolic or numeric check: for random 0/1 matrices A, random x in {0,1}^n, and R=2, construct V_x from Equation (7), verify that multiplying by the claimed inverse in Equation (8) gives the identity, and compare the squared Frobenius norm of (8) with the expression in Lemma 3.2 (Equation 9); any mismatch would indicate a hidden error in the gap argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern found. The reduction from 3-DM is sound: the exact inverse in Lemma 3.1 (Equation 8) is verified by block multiplication, the completeness bound A(x)≤2dR^2 and soundness bound E(x)≥R^4 in Lemma 3.2 follow exactly, and the bit-length calculation B=2d^{c+1}+O(1) yields a gap of 2^{B-O(log d)}, which dominates 2^{poly(d)+(1−ε)B} for suitable c and large d. The only minor imprecision is the quantifier over c and the handling of small d (standard padding), which does not affect the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies A- and E-optimal design under partition matroid constraints: given vectors v_1,...,v_N in R^d and a partition matroid, the goal is to choose a base S minimizing tr(M(S)^{-1}) (A-design) or lambda_max(M(S)^{-1}) (E-design), where M(S)=sum_{i in S} v_i v_i^top. The main result, Theorem 1.1, states that, assuming P != NP, for every epsilon in (0,1) there is no polynomial-time algorithm with approximation guarantee 2^{poly(d)+(1-epsilon)B}, where d is the dimension and B the maximum coordinate bit length. The proof gives an elementary reduction from three-dimensional matching. Each base corresponds to a 0/1 vector x of chosen triples, and the inverse of the associated matrix V_x contains the block R^2(Ax-1_m). A perfect matching exists iff some base has A-cost at most 2dR^2; otherwise every base has E-cost at least R^4. Choosing R = 2^{d^{c+1}} yields a gap of 2^{B-O(log d)}, which dominates the claimed approximation factor for suitably chosen c.","tokens_in":51,"tokens_out":22275,"duration_ms":259124,"significance":"If the result holds, it answers an open question of Brown, Laddha and Singh [BLS24] and establishes a sharp contrast with D-design under matroid constraints, for which constant-factor estimation and polynomial approximation algorithms exist. The reduction is elementary and fully explicit: the exact inverse in Lemma 3.1 is verified by direct block multiplication, the completeness and soundness bounds in Lemma 3.2 are exact, and the gap calculation is parameter-free once R is chosen. The paper is short, readable, and the central argument is convincing. The remaining concerns are presentation-level: the quantifier over the polynomial p(d) in Theorem 1.1 and the treatment of small d are not fully spelled out, but both are straightforward to fix and do not affect the substance.","major_comments":[],"minor_comments":[{"comment":"The quantifier over c is imprecise: the proof fixes an integer c before specifying the polynomial p(d) in the approximation guarantee, yet later uses d^c to dominate 'any polynomial'. To make the proof rigorous, one should first fix an arbitrary polynomial p, then choose c (and R = 2^{d^{c+1}}) large enough so that p(d) <= d^c and epsilon B - O(log d) > d^c for all sufficiently large d.","section":"Section 3.2, proof of Theorem 1.1"},{"comment":"The statement 'For d large enough' needs an explicit treatment of small d. Since d = n+m+1, small d means bounded 3-DM instance size; such instances can be solved by brute force in constant time, or the instance can be padded to increase d. Please state this explicitly so the reduction covers all instances.","section":"Section 3.2, proof of Theorem 1.1"},{"comment":"The displayed definition 'R:= 2 dc+1' should read 'R := 2^{d^{c+1}}', and 'd c + (1-epsilon)B' should be 'd^c + (1-epsilon)B'; the exponents appear to have been lost in typesetting.","section":"Section 3.1"},{"comment":"The phrase 'has squared Euclidean norm is at least R^4' should be 'has squared Euclidean norm at least R^4'.","section":"Section 3.2, Lemma 3.2"},{"comment":"The sentence 'All coordinates with be integers' should read 'All coordinates will be integers'.","section":"Abstract"},{"comment":"The citation '[L WZ25]' contains an unintended space and should be '[LWZ25]'.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a clean and correct hardness result that answers an open question. The only issues are presentation-level and can be addressed with a small revision. I support publication after these fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I agree with the reader's ACCEPT, and I verified the key algebra independently. The reduction from 3-DM to A/E-design under partition constraints is genuinely new and answers the open question from Brown, Laddha and Singh. The construction is elementary in the good sense: a block matrix whose exact inverse exposes Ax−1_m, so the completeness and soundness bounds fall out.\n\nWhat the paper does well: Lemma 3.1's inverse is checkable by direct multiplication; Lemma 3.2's bounds follow exactly. The completeness bound uses ‖Ax‖²=3Σx_i=m when Ax=1_m, giving A(x)≤2dR². The soundness bound uses the nonzero integer vector Ax−1_m in the h-column, giving E(x)≥R⁴. With R=2^{d^{c+1}}, B=2d^{c+1}+O(1), the gap is 2^{B−O(log d)}. For any fixed ε and any polynomial p(d), choosing c large enough gives gap > 2^{p(d)+(1−ε)B}. The bit-length calculation is consistent, and the padding to k>d via zero vectors is standard.\n\nSoft spots: the quantifier order in the proof of Theorem 1.1 is a bit loose — c is picked before d, but you can choose c after p — and small d needs a padding remark. Neither is load-bearing. The paper would benefit from making this explicit.\n\nThe contrast with D-design is accurate and the citations support it. The hardness proof uses no self-citations and no fitted parameters. This is reproducible, formal work.\n\nI'd send this to peer review without hesitation. The main theorem is correct, the method is clean, and the open question deserves a definitive answer. After minor revision, it should be accepted. I'd also bring it to a reading group; the inverse gadget is a neat trick that people in approximation algorithms should see.","headline":"A correct, clean hardness result for A/E-design under partition constraints; the elementary 3-DM reduction verifies cleanly and deserves serious peer review.","tokens_in":6346,"tokens_out":4059,"would_cite":true,"duration_ms":34658,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Assuming P≠NP, A/E-design under partition constraints admits no efficient algorithm with approximation guarantee $2^{poly(d)+(1-\\varepsilon)B}$.","keywords":["A-optimal design","E-optimal design","partition matroid","hardness of approximation","three-dimensional matching","experimental design","inapproximability","P vs NP"],"falsifier":"For the smallest instance, $m=3$, $n=1$, with $R=2$, write out the $5\\times 5$ matrices $V_x$ from (7) and the proposed inverse from (8) for both $x=0$ and $x=1$, and multiply them by hand; if any block of the product deviates from the identity, especially the lower middle block where $R^2A_x\\mathbf{1}_n$ must cancel, the claimed $R^4$ separation is wrong.","tokens_in":5535,"feed_emoji":"🧩","tokens_out":6991,"duration_ms":61020,"temperature":0.7,"pith_summary":"The paper asks whether A- and E-optimal design remain approximable when the chosen set of vectors must be a base of a partition matroid, and answers no: assuming P≠NP, any efficient algorithm must have approximation factor at least $2^{poly(d)+(1-\\varepsilon)B}$, where $d$ is the dimension and $B$ is the maximum coordinate bit length. This is established by an elementary reduction from three-dimensional matching. The result matters because D-design, the sister objective, is known to admit poly$(d)$ estimation and approximation algorithms under the same matroid constraints, so A/E-design breaks the pattern. If correct, the problem has no reasonable approximation in general, resolving a question raised in earlier work on E-design with partition constraints.","feed_headline":"A/E-design is inapproximable under partition constraints","feed_subtitle":"Partition matroids force exponential-in-bit-length approximation hardness for A- and E-optimal design, unlike D-design.","key_machinery":"The load-bearing object is the block matrix $V_x=\\begin{pmatrix} I_n & R\\mathbf{1}_n & 0 \\\\ 0 & 1 & 0 \\\\ RA_x & R^2\\mathbf{1}_m & I_m \\end{pmatrix}$ and its exact inverse, Lemma 3.1. The construction chooses one vector per part, with triple parts offering either $u_i$ or $u_i+Ra_i$, and the special vector $w=h+R\\sum_i u_i+R^2\\sum_j e_j$ forces any base to represent $h$ with coefficients involving $Ax-\\mathbf{1}_m$. The exact inverse places $R^2(Ax-\\mathbf{1}_m)$ in a block, so the Frobenius norm formula for $A(x)$ follows immediately. It is this algebra that converts the combinatorial matching problem into a numeric gap between $R^4$ and $2dR^2$.","core_discovery":"The central claim is Theorem 1.1: for every $\\varepsilon\\in(0,1)$, assuming P≠NP, no polynomial-time algorithm approximates A-design or E-design under partition constraints within factor $2^{poly(d)+(1-\\varepsilon)B}$. The reduction builds $d=m+n+1$ dimensions and a partition matroid with $d$ singleton-or-pair parts; bases correspond exactly to 0/1 vectors $x$ indexed by triples. A perfect three-dimensional matching exists iff $Ax=\\mathbf{1}_m$, and the gadget embeds the residual vector $R^2(Ax-\\mathbf{1}_m)$ as a block of $V_x^{-1}$. Thus yes-instances have $A(x)\\le 2dR^2$ while no-instances have $E(x)\\ge R^4$, giving a separation ratio $R^2/(2d)$ that is tuned to be exponential in $B$.","pith_inferences":["The block-inverse gadget is reusable: any objective that reads a large block of $V_x^{-1}$ involving $\\|Ax-\\mathbf{1}_m\\|$ will inherit the same hardness, so one can expect similar inapproximability for other spectral functions of $M(S)^{-1}$.","The result highlights precision, not just dimension, as an inherent source of intractability; algorithms for fixed dimension or strongly bounded coordinate size would not contradict the theorem.","A natural next target is to ask whether the same hardness holds for A/E-design under richer combinatorial constraints, such as intersections of two partition matroids or general matroids, since the current construction needs only simple partition constraints.","The exact inverse formula could be verified exhaustively on small random 3-DM instances by comparing it with brute-force computation of all bases, providing a concrete consistency test of the reduction's internal algebra."],"forward_implications":["No polynomial-time constant-factor or even subexponential-in-$B$ approximation exists for A/E-design under partition matroids, unless P=NP.","The known contrast with D-design is confirmed: D-design has poly$(d)$-guarantee algorithms for partition matroids, while A/E-design cannot.","The hardness transfers to rank $k>d$ by appending zero-vector parts, so allowing extra measurements does not make the problem tractable.","Because $E(x)\\le A(x)\\le dE(x)$, the same reduction certifies hardness for both objectives simultaneously.","The approximation must depend on the bit length $B$, so any tractable regime would have to constrain coordinate magnitudes or dimensions."],"supporting_citations":[{"why":"Supplies the NP-completeness of three-dimensional matching, the starting point of the reduction.","marker":"[Kar72]"},{"why":"The prior study of E-design with partition constraints whose open question is answered.","marker":"[BLS24]"},{"why":"Establishes the D-design positive result under partition matroids that motivates the contrast.","marker":"[MNST20]"},{"why":"Provides polynomial-time poly(d)-guarantee algorithms for D-design under matroid constraints, the comparison point for A/E hardness.","marker":"[BLP+22]"},{"why":"Extends determinant maximization to all matroids, reinforcing the D-design side of the contrast.","marker":"[BLPS22]"}],"fun_headline_variants":["A/E-design turns inapproximable under partition constraints","Partition matroids make A/E-design hard to approximate","3D matching proves A/E-design inapproximability","No approximations for A/E-design with partition matroids","Partition constraints make A/E-design inapproximable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole gap rests on the exact block-inverse identity in Lemma 3.1; if that algebraic formula were wrong, the no-answer cost would not jump to $R^4$ while the yes-answer cost stays near $2dR^2$, and the claimed separation would collapse.","fun_headline_variants_meta":{"raw":{"variants":["A/E-design turns inapproximable under partition constraints","Partition matroids make A/E-design hard to approximate","3D matching proves A/E-design inapproximability","No approximations for A/E-design with partition matroids","Partition constraints make A/E-design inapproximable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001179,"raw_usage":{"total_tokens":4826,"prompt_tokens":851,"completion_tokens":3975,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":3895}},"tokens_in":467,"tokens_out":3975,"duration_ms":26030,"temperature":1.0,"reasoning_tokens":3895,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:30:35.378192+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the smallest instance, $m=3$, $n=1$, with $R=2$, write out the $5\\times 5$ matrices $V_x$ from (7) and the proposed inverse from (8) for both $x=0$ and $x=1$, and multiply them by hand; if any block of the product deviates from the identity, especially the lower middle block where $R^2A_x\\mathbf{1}_n$ must cancel, the claimed $R^4$ separation is wrong.","supporting_citations":[],"review_version":1}