Fine-Grained AC$^0$ Lower Bounds for $k$-OV, $k$-XOR, and $k$-SUM via Colored Subgraph Isomorphism

Haoxing Lin

REVIEW 1 major objections 5 minor 33 references

Fine-Grained AC$^0$ Lower Bounds for $k$-OV, $k$-XOR, and $k$-SUM via Colored Subgraph Isomorphism

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Interesting architecture, but a systematic polarity error inverts all three projection guards; the theorems are false as written, though readily repairable. read the letter →

arxiv 2608.08578 v1 pith:LQSTKPBB submitted 2026-08-09 cs.CC

Haoxing Lin This is my paper · ORCID

classification cs.CC MSC 68Q1768Q15

keywords AC^0lowerboundsk-OrthogonalVectorsk-XORk-SUMcoloredsubgraphisomorphismdepth-zeroprojectionsfine-grainedcomplexity

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

You 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.

The 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.

Soft 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.

Net: 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.

Referee Report

1 major / 5 minor

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.

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 (1)

[Sections 4.1–4.3, Theorems 13/15/16, Appendix C] 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.

minor comments (5)

[Throughout] 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 1.3] The phrase 'Once S∈... is fixed, i.e., that is, once' contains a redundant 'that is' and should be edited.
[Corollary 6 proof] The displayed chain of inequalities has a duplicated term '≥N^{γ(k−1)}' and should be trimmed to a single inequality.
[Section 2.1 / Appendix A] 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 4.2, Equation (29)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the target lower bounds are obtained by explicit depth-zero projections from independently cited source lower bounds; the only assumption tailored to this paper is an openly labeled conjecture.

full rationale

I find no circular step in the derivation chain. The paper's target lower bounds are produced by explicit depth-zero projections (Theorem 10 and the three instantiations in Section 4) from a structured colored subgraph isomorphism source to k-OV, odd-k k-XOR, and k-SUM. The source-side hardness is imported from published fixed-pattern lower bounds of Li-Razborov-Rossman (Theorem 2, with the citation assembly in Appendix A) and from Beame's small-clique PRAM lower bound (Fact 18), neither of which is derived from the target statements and neither of which is a self-citation by the present author. No parameter is fitted to the target functions: the constants C_OV, C_U0002FB23, and C_U0001D6F4 are universal construction budgets fixed by explicit coordinate counts (Equations (21), (29), and (32)), and the target exponent rate beta is obtained from the imported source rate c_kappa under the explicit slack condition 2*beta < gamma (Equation (40)); beta is not estimated from k-OV/k-XOR/k-SUM data. The only assumption tailored to this paper, Pattern-Uniform LRR (Conjecture 26), is explicitly flagged as a strengthening of the cited theorem and as not known to follow from it; it is used only for the conditional results of Theorem 28. The paper even records the quantifier-order obstruction (Lemma 32) explaining why the published theorem does not yield the conjecture, which further confirms that the conditional path is an openly stated hypothesis rather than a disguised use of the paper's own conclusions. No self-definitional construction, no fitted input renamed as a prediction, and no renaming of a known result is present. The lower-bound architecture is therefore self-contained relative to its cited source theorems, and the conditional completion is transparently stated as conjectural.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new physical or formal entities beyond two pattern families, the padded expander and the clique plus matching, plus an explicit conjecture. These are constructions and hypotheses, not invented entities with independent falsifiable handles. Nontrivial background is cited published mathematics; the only unproved input is Pattern-Uniform LRR, confined to conditional theorems.

free parameters (3)

source rate gamma = any 0 < gamma < 1/147
Chosen in Theorem 17 as slack below the LRR expansion rate of the degree-7 expander family; not fitted to data.
target rate beta = any 0 < beta < gamma/2
Universal exponent rate in Theorem B; exists by a slack condition and is independent of d, k, and n.
construction constants C_OV, C_oplus, C_Sigma = unspecified, sufficiently large
Fixed in Theorem 10 and Lemma 11 to bound the O(k log n) budget scale; exact values do not affect asymptotic claims.

assumptions (7)

standard math Li-Razborov-Rossman fixed-pattern AC0 lower bound for colored subgraph isomorphism (Theorem 2; [LRR17, Thm 3.12])
Supplies the source hardness n^{κ(P)-η} used by Theorem B and the conditional Theorem E; load-bearing.
standard math Structural estimates for κ: expansion lower bound, treewidth upper bound, minor monotonicity (Theorem 4; [LRR17, Thm 4.9, Prop 4.3, Thm 5.1])
Used to show κ(P_exp_k)=Ω(k) on the padded expander family.
standard math Beame's small-clique lower bound for CRCW PRAMs and its gate-count consequence (Fact 18; [Bea90, Thm 3.1(b)])
Supplies the growing-clique source bound that yields Theorem C, the unconditional growing-k floor.
standard math Explicit near-Ramanujan simple graphs of every degree and size (Alon [Alo21, Thm 1.3] using MOP [MOP20])
Used in Appendix B.1 to construct the degree-7 expander core with the needed edge counts.
standard math Håstad's depth-d parity lower bound [Hås86]
Used in the complementary row-rich PARITY projection for k-XOR, not for the main AC0 frontier.
standard math Erdős-Ginzburg-Ziv theorem [EGZ61]
Used only for the boundary degeneracy statement in Proposition 62.
ad hoc to paper Pattern-Uniform LRR conjecture (Conjecture 26)
Sufficient condition for the n^{Ω_d(k)} depth-three and all-depth conditional completion; explicitly unproved and not claimed to follow from LRR.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fine-Grained AC$^0$ Lower Bounds for $k$-OV, $k$-XOR, and $k$-SUM via Colored Subgraph Isomorphism." pith.science (2026). https://pith.science/paper/LQSTKPBB

@misc{pith2026260808578,
  author       = {Pith},
  title        = {Pith review of: Fine-Grained AC$^0$ Lower Bounds for $k$-OV, $k$-XOR, and $k$-SUM via Colored Subgraph Isomorphism},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LQSTKPBB}},
  note         = {Machine review of arXiv:2608.08578}
}

abstract

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-OV and $(n/k)^{\Omega(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{\Omega_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = \Theta(k\log(en/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

Figures

Figures reproduced from arXiv: 2608.08578 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Annals of Pure and Applied Logic , volume =

Mikl. Annals of Pure and Applied Logic , volume =

work page
[2]

Combinatorica , volume =

Noga Alon , title =. Combinatorica , volume =. 2021 , doi =

work page 2021
[3]

Proceedings of the 47th Annual

Arturs Backurs and Piotr Indyk , title =. Proceedings of the 47th Annual. 2015 , doi =

work page 2015
[4]

Journal of the

Avrim Blum and Adam Kalai and Hal Wasserman , title =. Journal of the

work page
[5]

2026 , doi =

Guy Bresler and Alina Harbuzova , title =. 2026 , doi =

work page 2026
[6]

Theorem in the additive number theory , journal =

Paul Erd. Theorem in the additive number theory , journal =

work page
[7]

Saxe and Michael Sipser , title =

Merrick Furst and James B. Saxe and Michael Sipser , title =. Mathematical Systems Theory , volume =

work page
[8]

Computational Complexity , volume =

Parikshit Gopalan and Raghu Meka and Omer Reingold , title =. Computational Complexity , volume =. 2013 , doi =

work page 2013

Show all 33 references

[9]

Almost Optimal Lower Bounds for Small Depth Circuits , booktitle =

Johan H. Almost Optimal Lower Bounds for Small Depth Circuits , booktitle =. 1986 , doi =

1986
[10]

2017 , doi =

Yuan Li and Alexander Razborov and Benjamin Rossman , title =. 2017 , doi =

2017
[11]

Algorithmica , volume =

Gregory Rosenthal , title =. Algorithmica , volume =. 2021 , doi =

2021
[12]

1997 , doi =

Alexander Vardy , title =. 1997 , doi =

1997
[13]

On Some Fine-Grained Questions in Algorithms and Complexity , booktitle =

Virginia. On Some Fine-Grained Questions in Algorithms and Complexity , booktitle =. 2018 , doi =

2018
[14]

Proceedings of the 26th Annual

Andrew Chi-Chih Yao , title =. Proceedings of the 26th Annual
[15]

Lawrence and Wegman, Mark N

Carter, J. Lawrence and Wegman, Mark N. , title =. Journal of Computer and System Sciences , volume =. 1979 , month = apr, doi =

1979
[16]

Information Processing 77, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8--12, 1977 , editor =

Freivalds, Rusins , title =. Information Processing 77, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8--12, 1977 , editor =

1977
[17]

, title =

Karp, Richard M. , title =. Complexity of Computer Computations , editor =. 1972 , doi =

1972
[18]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , series =

Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro , title =. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , series =. 2020 , doi =. 1909.06988 , archivePrefix =

2020 arXiv
[19]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing , series =

Rossman, Benjamin , title =. Proceedings of the 40th Annual ACM Symposium on Theory of Computing , series =. 2008 , doi =

2008
[20]

2026 , month = jul, note =

Tameem Choudhury and Nutan Limaye and Karteek Sreenivasaiah and Srikanth Srinivasan , title =. 2026 , month = jul, note =

2026
[21]

Discrete Applied Mathematics , volume =

Paul Beame , title =. Discrete Applied Mathematics , volume =. 1990 , doi =

1990
[22]

Computational Complexity , volume =

Kazuyuki Amano , title =. Computational Complexity , volume =. 2010 , doi =

2010
[23]

Journal of Computer and System Sciences , volume =

Russell Impagliazzo and Ramamohan Paturi , title =. Journal of Computer and System Sciences , volume =. 2001 , doi =

2001
[24]

Journal of Computer and System Sciences , volume =

Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. Journal of Computer and System Sciences , volume =. 2001 , doi =

2001
[25]

Ryan Williams , title =

Lijie Chen and R. Ryan Williams , title =. Proceedings of the Thirtieth Annual. 2019 , doi =

2019
[26]

2026 , note =

Tameem Choudhury and Karteek Sreenivasaiah , title =. 2026 , note =

2026
[27]

Kane and R

Daniel M. Kane and R. Ryan Williams , title =. 10th Innovations in Theoretical Computer Science Conference (. 2019 , doi =

2019
[28]

The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds , journal =

R. The Orthogonal Vectors Conjecture and Nonuniform Circuit Lower Bounds , journal =. 2025 , note =

2025
[29]

Advances in Cryptology---

David Wagner , title =. Advances in Cryptology---. 2002 , doi =

2002
[30]

Journal of the

Itai Dinur and Nathan Keller and Ohad Klein , title =. Journal of the. 2024 , doi =

2024
[31]

Schwartzbach and Akhil Vanukuri and Prashant Nalini Vasudevan , title =

Shweta Agrawal and Sagnik Saha and Nikolaj I. Schwartzbach and Akhil Vanukuri and Prashant Nalini Vasudevan , title =. Advances in Cryptology---. 2024 , doi =

2024
[32]

Proceedings of the 50th Annual

Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof , title =. Proceedings of the 50th Annual. 2018 , doi =

2018
[33]

Average-Case Hardness of Parity Problems: Orthogonal Vectors,

Mina Dalirrooyfard and Andrea Lincoln and Barna Saha and Virginia. Average-Case Hardness of Parity Problems: Orthogonal Vectors,. Proceedings of the 2025 Annual. 2025 , doi =

2025

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Annals of Pure and Applied Logic , volume =

Mikl. Annals of Pure and Applied Logic , volume =

work page

[2] [2]

Combinatorica , volume =

Noga Alon , title =. Combinatorica , volume =. 2021 , doi =

work page 2021

[3] [3]

Proceedings of the 47th Annual

Arturs Backurs and Piotr Indyk , title =. Proceedings of the 47th Annual. 2015 , doi =

work page 2015

[4] [4]

Journal of the

Avrim Blum and Adam Kalai and Hal Wasserman , title =. Journal of the

work page

[5] [5]

2026 , doi =

Guy Bresler and Alina Harbuzova , title =. 2026 , doi =

work page 2026

[6] [6]

Theorem in the additive number theory , journal =

Paul Erd. Theorem in the additive number theory , journal =

work page

[7] [7]

Saxe and Michael Sipser , title =

Merrick Furst and James B. Saxe and Michael Sipser , title =. Mathematical Systems Theory , volume =

work page

[8] [8]

Computational Complexity , volume =

Parikshit Gopalan and Raghu Meka and Omer Reingold , title =. Computational Complexity , volume =. 2013 , doi =

work page 2013