{"id":"89812716-3e12-48e2-a423-87cbe91eaf99","arxiv_id":"2608.08578","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Colored subgraph isomorphism projects by depth-zero reductions to k-OV, odd-k k-XOR, and k-SUM, yielding unconditional AC0 lower bounds n^{Ω(k)} for fixed k and n^{Ω_d(min{sqrt k, log n})} for growing k.","lead":"This paper proves new unconditional size lower bounds for constant-depth circuits solving k-Orthogonal Vectors, k-XOR, and k-Sum, tracking how the exponent grows with k. It builds one reduction framework from colored subgraph isomorphism and transfers hardness to all three targets without adding depth or gates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The projection theorems invert the source edge variable: Definition 1 fixes X=1 as present, but the guard constructions treat present edges as X=0, so Theorems 13/15/16 fail as written.","rationale":"The reader's ACCEPT verdict identifies the LRR fixed-pattern theorem as the weakest assumption, but the more fundamental problem is internal: the projection constructions contradict the paper's own Definition 1 on the meaning of the source variables. Since the guards are used verbatim in all three transfer theorems, the central claim does not currently hold as stated. However, the flaw looks like a systematic polarity error rather than a conceptual collapse: replacing the guard entries X with ¬X makes the projections align with Definition 1, and because input negations are free in this model, the lower bounds would still transfer with the same size exponents. I therefore recommend CONDITIONAL acceptance: the authors must correct the polarity convention in Sections 4.1-4.3, in the proofs of Theorems 13/15/16, and in the corresponding appendix proofs, and re-verify the three target constructions. This is a concrete, checkable repair; it is not a rejection of the proof strategy or a challenge to the cited source theorems.","tokens_in":56200,"tokens_out":26317,"duration_ms":308905,"concrete_test":"Run the minimal k=2, P = single-edge case. Take a source input with X_{1,1} = 1 and all other X-variables 0; by Definition 1 the source accepts. Apply Theorem 13's construction with N = 1, n = 1. On the edge-guard coordinate q_f, the anchor vector has entry 1 and the selected edge vector has entry X_{1,1} = 1, so the selected tuple is non-orthogonal and the constructed k-OV instance rejects. This directly contradicts the asserted projection P-SUB_N ≤proj k-OV. Repeat the audit after changing every presence-guard entry to the literal ¬X_{f,u,w} in the k-OV, k-XOR, and k-SUM constructions; if all three then pass the single-edge and multi-edge witness tests, re-derive the transferred theorems with the corrected polarity.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 1 fixes the polarity of the source: X_{f,u,w} = 1 means the host edge is present, and acceptance requires X = 1 on the witness edges. The three target constructions are internally written with the opposite polarity. In Section 4.1, the k-OV edge-guard coordinate q_f assigns entry X_{f,u,w} to the genuine edge vector, and Theorem 13's proof says 'the selected group-f vector contributes X = 0'. But under Definition 1 a present edge has X = 1, so the guard product is 1 and the projected target rejects the supposed witness. The same contradiction appears in Lemma 48: 'A present candidate has X_{f,u,w} = 0 and contributes the zero label.' Section 4.3 likewise defines the k-SUM guard coordinate as Q = X and claims its nonnegative sum vanishes exactly when every selected edge is present; again this requires present = 0. Thus, as written, the claimed depth-zero projections map accepting source instances to rejecting target instances, invalidating Theorems 13, 15, and 16 and everything transferred through them. This is more load-bearing than the cited LRR import: the transfer itself is internally inconsistent under the stated Definition 1. The error appears uniformly repairable by replacing the guard literals X with ¬X; because input negations are free in this circuit model and size_d(P-SUB_N(¬x)) = size_d(P-SUB_N), the lower-bound architecture could survive a corrected polarity convention. But the submitted formal statements are false as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified framework of depth-zero projections from colored subgraph isomorphism (Definition 1) to three target problems: k-OV, odd-k k-XOR, and k-SUM, at constraint budgets of order k log n. Combining these projections with two source-side lower bounds—the Li–Razborov–Rossman fixed-pattern lower bound for colored subgraph isomorphism and Beame's small-clique PRAM lower bound—the paper obtains unconditional AC^0 size lower bounds whose exponents scale with k: n^{Ω(k)} for fixed k and k-OV, (n/k)^{Ω(k)} for fixed k and the list targets, n^{Ω_d(min{√k, log n})} for growing k at every fixed depth, and n^{Ω(k)} at depth two. A conjectural pattern-uniform strengthening of the LRR theorem (Conjecture 26) is shown to complete the linear-in-k exponent for all depths d≥3, and the paper supplies matching or near-matching upper bounds at the principal width for top-disjunction depth-three circuits. Several auxiliary results cover even-k XOR via a lifting projection, row-rich PARITY reductions, boundary cases for k-SUM, and depth-sensitive upper bounds.","tokens_in":56480,"tokens_out":10711,"duration_ms":118616,"significance":"If the central projections are correct, this is a substantial contribution: it transfers unconditional AC^0 lower bounds to fine-grained target problems while tracking the exponent in k, uses no running-time hypothesis, preserves gate orientation, and cleanly separates the proved source statements from the explicitly conjectural Pattern-Uniform LRR. The paper is careful about quantifier order: the universal fixed-k rate β is not allowed to depend on k or d, and the onset thresholds are separated from exponent rates. The appendices give unusually detailed citation assembly for the LRR import, explicit constructions for the expander and clique pattern families, and full projection proofs. The AI-disclosure passages are transparent and do not affect the technical assessment. However, the submitted version has a load-bearing polarity error in the guard constructions that makes the three projection theorems false as written; the error appears uniformly repairable, but the current manuscript cannot be accepted without correction.","major_comments":[{"comment":"The three guard constructions use the opposite edge polarity from Definition 1. Definition 1 fixes X_{f,u,w}=1 to mean the host edge is present and requires X=1 on every witness edge. The k-OV guard coordinate q_f carries entry X_{f,u,w}, and the proof in Appendix C.1 asserts that the selected group-f vector contributes X_{f,u,w}=0 for a present edge; Lemma 48 states 'A present candidate has X_{f,u,w}=0 and contributes the zero label'; and Section 4.3 defines the k-SUM guard coordinate as Q=X and claims its nonnegative sum vanishes exactly when every selected edge is present. Under Definition 1 all three statements require the opposite polarity: an accepting source witness has X=1, so the k-OV guard product is 1 and the k-XOR/k-SUM guard sums are nonzero, making the projected target reject the witness. The claimed equivalences in Theorems 13, 15, and 16 are therefore false as written, and the error propagates to every lower bound transferred through Theorem 10. The repair is uniform—replace the guard literals X by ¬X in the three instantiations—and should preserve the lower bounds because input negations are free in the model, but the submitted statements and their proofs must be corrected before the results can be considered established.","section":"Sections 4.1–4.3, Theorems 13/15/16, Appendix C"}],"minor_comments":[{"comment":"The text contains many OCR/LaTeX rendering artifacts (for example 'AC 0', 'F m 2', 'H ˚ astad', and similarly broken math symbols) that should be cleaned before final submission.","section":"Throughout"},{"comment":"The phrase 'Once S∈... is fixed, i.e., that is, once' contains a redundant 'that is' and should be edited.","section":"Section 1.3"},{"comment":"The displayed chain of inequalities has a duplicated term '≥N^{γ(k−1)}' and should be trimmed to a single inequality.","section":"Corollary 6 proof"},{"comment":"After the polarity repair, the paper should explicitly state and justify that size_d(f(¬x)) = size_d(f(x)) under the input-negation convention, since the repaired guard literals negate source variables.","section":"Section 2.1 / Appendix A"},{"comment":"The definition of m⊕(P,N) as e(P)+r_guard+|I(P)|ℓ_N+1 is correct, but the text could state more clearly that the '+1' is the anti-dummy row, because the same symbol is later reused for the packing constant.","section":"Section 4.2, Equation (29)"}],"recommendation":"major_revision","confidential_remarks":"The polarity issue is severe enough that I could not recommend acceptance of the current version, but it has the character of a consistent sign convention error rather than a fundamental flaw: replacing the guard literals X by ¬X appears to repair all three projections without changing the lower-bound architecture. I would encourage the editor to treat the revision as substantive but scoped. The paper's explicit disclosure of AI-suggested components is unusual but appears transparent and does not affect my assessment of the technical content."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know this paper before you spend time on it: it has a clean architectural idea, but the three projection theorems as written are inverted by a polarity error. Definition 1 fixes X=1 as \"edge present,\" and acceptance requires X=1 on witness edges. Yet every guard role in Sections 4.1–4.3 treats present edges as X=0: the k-OV guard coordinate q_f sets the candidate's entry to X and then claims a present edge contributes 0 to the product; Lemma 48 says \"a present candidate has X=0\"; the k-SUM guard Q is X and requires its sum to vanish when all selected edges are present. All three projections therefore send accepting source instances to rejecting target instances. The error is uniform and trivially fixable by substituting ¬X for X in the guards—negations are free in this circuit model, so the monotonicity argument and the size/depth transfer survive—but the theorems as stated are false.\n\nThe rest of the paper is much better. The depth-zero projection interface is a nice unification: the same source witness maps to k-OV, odd-k k-XOR, and k-SUM, with the n vs n/k packing distinction falling out of storage. The depth-two counting for both DNF and CNF orientations is clean and self-contained. The source-side appendices are careful: the LRR citation assembly, the Beame simulation, and the expander construction are all written at a level that would survive scrutiny once the polarity is corrected. The Pattern-Uniform LRR conjecture is explicitly flagged and used only for conditional statements, which is honest.\n\nSoft spots beyond the polarity issue: the entire transfer relies on imported source theorems, and the unproved conjecture is a real gap, but the paper is transparent about that. The depth-two source bound is proved directly and doesn't depend on the broken guards. The parity caveat for even-k XOR is handled by a black-box lift that also looks sound.\n\nNet: this deserves a serious referee, but not because the current version is correct—rather because the core architecture is salvageable and the fix is mechanical. I would send it out with a request for major revision. The reader's ACCEPT verdict is too generous; this is a reject-and-resubmit in its present form. After the guard polarity is corrected, I'd be eager to re-read.","headline":"Interesting architecture, but a systematic polarity error inverts all three projection guards; the theorems are false as written, though readily repairable.","tokens_in":57034,"tokens_out":3973,"would_cite":false,"duration_ms":42527,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"One family of depth-zero projections transfers colored-subgraph hardness to $k$-OV, odd-$k$ $k$-XOR, and $k$-SUM, giving $n^{\\Omega(k)}$-scale size lower bounds for constant-depth circuits at every fixed depth.","keywords":["AC^0 lower bounds","k-Orthogonal Vectors","k-XOR","k-SUM","colored subgraph isomorphism","depth-zero projections","fine-grained complexity"],"falsifier":"Check the imported fixed-pattern lower bound (Theorem 2) at the host sizes the projections actually use, $N=\\lfloor\\sqrt{n}\\rfloor$ for $k$-OV and $N=\\lfloor\\sqrt{(n-1)/(k-1)}\\rfloor$ for the list targets with $n\\ge 16k$: if the quoted size $N^{\\kappa(P)-\\eta}$ fails to dominate the convention-bridge term $2e(P)N^2+2$ at those sizes, or if the onset threshold $N_0(d,k)$ exceeds the reachable host sizes, the transferred $n^{\\beta(k-1)}$ bound is vacuous. A second decisive test targets the conditional part: show, for depth three, a sequence of host sizes $N=k^{O(1)}$ on which every depth-three circuit for $P^{\\exp}_k\\text{-SUB}_N$ has size below $N^{\\gamma_3 k}$, and Conjecture 26 fails, so the claimed $n^{\\Omega_d(k)}$ completion loses its only source of hardness.","tokens_in":55944,"feed_emoji":"🧩","tokens_out":33524,"duration_ms":289444,"temperature":0.7,"pith_summary":"The paper proves worst-case size lower bounds for three canonical fine-grained problems — $k$-Orthogonal Vectors, $k$-XOR, and $k$-SUM — against nonuniform constant-depth circuits, with the exponent tracking the number $k$ of selected objects and with no running-time hypothesis assumed. The unifying device is a family of depth-zero projections: an instance of colored subgraph isomorphism on a pattern with exactly $k-1$ edges is encoded, by substitution of constants and negated literals only, into each target at dimension, row-count, or bit-width budgets of $O(k\\log n)$, so the projections neither add gates nor increase depth. Taking the source to be a padded expander pattern whose treewidth-like parameter $\\kappa$ is linear in $k$, the paper obtains for every fixed depth and every sufficiently large fixed $k$ circuit size $n^{\\beta(k-1)}$ for $k$-OV and $(n/k)^{\\beta(k-1)}$ for odd-$k$ $k$-XOR and for $k$-SUM, with one exponent-rate constant $\\beta$ independent of $k$, of the depth, and of $n$ (only the onset threshold may depend on $d$ and $k$). For growing $k=n^{o(1)}$ it obtains $n^{\\Omega_d(\\min\\{\\sqrt{k}, \\log n\\})}$ at every fixed depth, strengthening to $n^{\\Omega(k)}$ at depth two for both top-gate orientations; a conjectured strengthening of the source lower bound would lift every fixed depth $d\\ge 3$ to $n^{\\Omega_d(k)}$. A reader should care because the results pinpoint how the constant-depth circuit size of these problems scales with $k$, and for fixed $k$ the depth-three lower bounds are exponent-scale matched by simple brute-force circuits.","feed_headline":"Constant-depth circuits for k-OV, k-XOR, k-SUM need n^{Ω(k)} size","feed_subtitle":"One depth-zero projection from colored subgraph isomorphism carries the hardness to all three targets.","key_machinery":"The carrying mechanism has three parts. First, the source function: the structured colored subgraph isomorphism problem $P\\text{-SUB}_N$ (Definition 1), whose Boolean inputs are the possible colored host edges $X_{f,u,w}$ and which accepts when one map $\\varphi:V(P)\\to[N]$ realizes every pattern edge; its hardness is quantified by $\\kappa(P)$, a treewidth-like parameter of the pattern that serves as the source-side exponent. Second, the carrier: the depth-zero projection, a substitution of constants and literals that the paper proves is monotone with respect to circuit size at every depth and preserves the orientation of every gate; its concrete form is a common universe skeleton in which each of the $k-1$ pattern edges becomes one candidate object, a single anchor fills the $k$-th slot, and coordinates or rows of the target enforce the five witness roles. Third, the two pattern families: a bounded-degree expander core padded with a disjoint matching, whose $\\kappa$ is linear in $k$ and which carries the fixed-$k$, the depth-two, and the conditional results; and a clique core padded with a matching, which carries the unconditional every-fixed-depth growing-$k$ floor through a small-clique lower bound whose range cap $r\\le\\log N$ is depth-independent. The three target algebras — coordinate-wise orthogonality for $k$-OV, $F_2$ selector equations for $k$-XOR (where even multiplicities escape detection, forcing odd $k$), and exact signed coordinates packed in a large power-of-two base for $k$-SUM — are interchangeable implementations of that skeleton. At depth two the switching method is replaced by exact counting, which supplies both orientations simultaneously.","core_discovery":"The central claim is that three algebraically different target problems share one witness-selection skeleton with colored subgraph isomorphism, and that the correspondence is computation-free: a depth-zero projection replaces every target input bit by a constant or a negated source bit, so any circuit computing a target would compute the source at the same depth and size. For a simple pattern $P$ with $k-1$ edges the paper constructs projections $P\\text{-SUB}_N \\to k$-OV at dimension $O(k\\log n)$ with host size $N=\\lfloor\\sqrt{n}\\rfloor$, and $P\\text{-SUB}_N \\to$ odd-$k$ $k$-XOR and $P\\text{-SUB}_N \\to k$-SUM (both parities) at row or bit budgets $O(k\\log(en/k))$ with host size $N=\\lfloor\\sqrt{(n-1)/(k-1)}\\rfloor$; each projection realizes five witness roles — selection rigidity, an edge-presence guard, shared-label consistency at pattern vertices, dummy purge, and pairwise distinctness for $k$-OV — inside the target's own algebra. Combined with the published fixed-pattern lower bound for colored subgraph isomorphism, whose source exponent is the parameter $\\kappa(P)$, and with the padded expander family satisfying $\\kappa(P^{\\exp}_k) \\ge c_\\kappa(k-1)$, this yields, for every fixed depth $d$ and fixed $k$, size at least $n^{\\beta(k-1)}$ for $k$-OV and $(n/k)^{\\beta(k-1)}$ for odd-$k$ $k$-XOR and $k$-SUM, with one universal constant $\\beta$. The paper further proves a growing-$k$ floor $n^{\\Omega_d(\\min\\{\\sqrt{k},\\log n\\})}$ at every fixed depth by switching to a padded clique pattern that imports a uniform small-clique lower bound, and proves the depth-two exponent $n^{\\Omega(k)}$ for both gate orientations by direct counting: every colored copy is a distinct minimal positive input forcing one DNF term, and $2^N$ minimal transversals force distinct CNF clauses. The parity asymmetry is isolated as a selection phenomenon — $F_2$ equations cannot exclude an even-multiplicity anchor-free branch, which is why the direct $k$-XOR projection requires odd $k$, while $k$-SUM's signed large-base packing is parity-free — and the depth-three and higher-depth linear-in-$k$ statements are conditional on a pattern-uniform strengthening (Conjecture 26) that the paper does not claim to prove.","pith_inferences":["Because the projections are depth-zero and orientation-preserving, the target constructions are effectively a solved layer: every future improvement on the source side — in particular any proof of the Pattern-Uniform conjecture — would transfer verbatim to all three targets, so the paper's open problems are mostly source-side.","The framework reads as a template rather than a trio of coincidences: any joint predicate over $k$ selected objects that can encode the five witness roles in its own algebra should inherit the same bounds, suggesting that other modular or polynomial identity targets admit the same $n^{\\Omega(k)}$-scale hardness.","The odd/even split in $k$-XOR looks structural rather than technical: over $F_2$, a support with an unselected anchor and even multiplicities in every pattern-edge group is invisible to the selector equations, so any direct projection for even $k$ must either change the selection algebra or accept an exponent governed by an odd factor $r$; the paper's lifting lemma quantifies exactly what an admis","The row-rich PARITY comparison points to a two-anchor landscape: at $m=\\Theta(n)$ rows a PARITY embedding beats the subgraph route at depths two and three but loses at every fixed depth $d\\ge 4$, so interpolating between the two anchors as a function of the row budget is a natural next question."],"forward_implications":["For every fixed depth $d$ and every sufficiently large fixed $k$, no polynomial-size constant-depth circuit can decide $k$-OV, odd-$k$ $k$-XOR, or $k$-SUM, since the required size grows like $n^{\\beta(k-1)}$ or $(n/k)^{\\beta(k-1)}$ with a single universal exponent-rate $\\beta$.","For subpolynomial $k=n^{o(1)}$, every fixed-depth circuit still demands size $n^{\\Omega_d(\\min\\{\\sqrt{k},\\log n\\})}$, and depth two demands $n^{\\Omega(k)}$ for both top-gate orientations, so even a slowly growing $k$ cannot be handled by polynomial-size constant-depth circuits.","At the principal $O(k\\log n)$-scale budgets for fixed $k$, the top-disjunction depth-three specializations of the lower bounds meet elementary brute-force upper bounds at the exponent scale for all three targets, pinning the exponent in that regime.","The $k$-SUM projection works for both parities, whereas $k$-XOR is directly hard only for odd $k$; for even $k$ an odd-to-even lifting projection transfers the odd-$k$ exponent through any admissible decomposition $K=tr+s$, at a factor governed by the odd parameter $r$.","If the Pattern-Uniform conjecture (Conjecture 26) holds, the same projections, unchanged, give $n^{\\Omega_d(k)}$ at depth three for both orientations and at every fixed depth $d\\ge 4$, completing the subpolynomial frontier."],"supporting_citations":[{"why":"Supplies the fixed-pattern constant-depth lower bound for colored subgraph isomorphism (Theorem 2), whose treewidth-like parameter $\\kappa$ fixes the source exponent that every fixed-$k$ bound inherits.","marker":"[LRR17]"},{"why":"Supplies the small-clique PRAM memory-cell lower bound from which Fact 18 derives the uniform gate-count bound used for the growing-$k$ every-fixed-depth floor.","marker":"[Bea90]"},{"why":"Provides the explicit near-Ramanujan base graphs that become the degree-7 expander cores of Lemma 5 after Alon's transformation.","marker":"[MOP20]"},{"why":"Provides the exact-size transformation turning near-Ramanujan graphs into simple $\\Delta$-regular graphs of every allowed vertex count, needed to obtain a core of exactly the right edge budget.","marker":"[Alo21]"},{"why":"Supplies the discrete Cheeger inequality and the $\\kappa$ restatements used to lower-bound $\\kappa$ of the expander cores by $\\Omega(k)$.","marker":"[Ros21]"},{"why":"Introduces the large-base positional encoding device on which the $k$-SUM projection's exact packing of signed integer coordinates rests.","marker":"[Kar72]"}],"fun_headline_variants":["AC0 needs n^Ω(k) size for k-OV, k-XOR, k-SUM","One projection: AC0 lower bounds for k-OV, k-XOR, k-SUM","Unconditional: AC0 needs n^Ω(k) for k-OV, k-XOR, k-SUM","Three problems, one projection: AC0 size exponent n^Ω(k)","k-OV, k-XOR, k-SUM need n^Ω(k) size in any fixed-depth AC0"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the published constant-depth lower bound for detecting colored copies of a fixed graph, applied here to padded expander patterns with no isolated vertices, together with, for the depth-three and higher completion, an unproved pattern-uniform strengthening of that bound; if the published bound does not extend to this paper's structured input encoding, or if the strengthening is false, the claimed exponents collapse.","fun_headline_variants_meta":{"raw":{"variants":["AC0 needs n^Ω(k) size for k-OV, k-XOR, k-SUM","One projection: AC0 lower bounds for k-OV, k-XOR, k-SUM","Unconditional: AC0 needs n^Ω(k) for k-OV, k-XOR, k-SUM","Three problems, one projection: AC0 size exponent n^Ω(k)","k-OV, k-XOR, k-SUM need n^Ω(k) size in any fixed-depth AC0"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001023,"raw_usage":{"total_tokens":4599,"prompt_tokens":1514,"completion_tokens":3085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":1130,"completion_tokens_details":{"reasoning_tokens":2958}},"tokens_in":1130,"tokens_out":3085,"duration_ms":23493,"temperature":1.0,"reasoning_tokens":2958,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:31:07.435541+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the imported fixed-pattern lower bound (Theorem 2) at the host sizes the projections actually use, $N=\\lfloor\\sqrt{n}\\rfloor$ for $k$-OV and $N=\\lfloor\\sqrt{(n-1)/(k-1)}\\rfloor$ for the list targets with $n\\ge 16k$: if the quoted size $N^{\\kappa(P)-\\eta}$ fails to dominate the convention-bridge term $2e(P)N^2+2$ at those sizes, or if the onset threshold $N_0(d,k)$ exceeds the reachable host sizes, the transferred $n^{\\beta(k-1)}$ bound is vacuous. A second decisive test targets the conditional part: show, for depth three, a sequence of host sizes $N=k^{O(1)}$ on which every depth-three circuit for $P^{\\exp}_k\\text{-SUB}_N$ has size below $N^{\\gamma_3 k}$, and Conjecture 26 fails, so the claimed $n^{\\Omega_d(k)}$ completion loses its only source of hardness.","supporting_citations":[],"review_version":1}