thecomplexitychronicles
PRICE: ONE ORACLE QUERY
WEEKLY · P ≠ NP (PROBABLY)
VOL. 1  NO. 45
2026-W45
All the news that's fit to reduce
Upper bounds, lower bounds, and the hypotheses in between.
Monday 9 November 2026  ·  covering 2–8 November 2026  ·  132 papers  ·  arXiv cs.CC, ECCC, Hexagon, Diderot
Inside this issue

▸ p.2: After ETH, what holds the lower bounds up. The Stearns–Hunt Satisfiability Hypothesis is shown equivalent to Weak ETH, and it keeps the usual reductions working. ▸ p.2: Mod-\(p\) equations, four colours easy, three hard. A complete classification for \(p>3\), with tractability obtained from Abelian embeddings. ▸ p.3: Resolution lower bounds now provable in constant depth. Quasipolynomial-size \(\mathbf{AC}^0\)-Frege proofs, and \(\mathbf{NP}\)-hardness of proof analysis. ▸ p.4: Splitting the variables. How the hyperclique wall was built, and what this week took out of it. ▸ Column: Shell Scott takes an inventory after the refutations.

FINE-GRAINED COMPLEXITY

The hyperclique conjecture falls

For every fixed \(k\) there is an \(\varepsilon_k > 0\) such that \(k\)-hypercliques in an \(n\)-vertex \((k-1)\)-uniform hypergraph can be counted in \(O(n^{k-\varepsilon_k})\) time, unconditionally; as corollaries, Max-\(k\)SAT runs in \(2^{(1-\varepsilon)n}\cdot\mathrm{poly}(m,n)\) time and length-\(k\) arithmetic progressions are detected in \(n^{2-\varepsilon}\) time, with \(\varepsilon\) depending on \(k\).

Alman, Li, Pant, Pratt and Williams [arXiv:2611.05082] count the \(k\)-hypercliques of a \((k-1)\)-uniform hypergraph on \(n\) vertices in \(O(n^{k-\varepsilon_k})\) time, for every fixed \(k\) and some \(\varepsilon_k > 0\). Brute force takes \(n^k\). The hyperclique conjecture of Lincoln, Vassilevska Williams and Williams (SODA 2018) said that no polynomial saving of this kind was possible. It is refuted, and no assumption is needed.

The method is algebraic. The authors build a uniform family of arithmetic circuits of size \(O(n^{k-\varepsilon_k})\) for the \(k\)-hyperclique tensor, the higher-order generalisation of the matrix multiplication tensor. When \(k = 3\) the hypergraph is an ordinary graph, the hypercliques are triangles, and fast matrix multiplication has long supplied the saving. For larger \(k\) there was no such tool. The conjecture was, in effect, a bet that none existed.

Two corollaries follow. For every \(k\) there is an \(\varepsilon > 0\) such that Max-\(k\)SAT can be solved in \(2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)\) time. And for every \(k\), arithmetic progressions of length \(k\) in subsets of \(\{0,1,\ldots,n\}\) can be detected in \(n^{2-\varepsilon}\) time. The authors state that both corollaries refute other prominent conjectures in the literature.

What it does not show is just as clear. The saving \(\varepsilon\) depends on \(k\), so the Max-\(k\)SAT result does not touch SETH, which asks for a saving that holds uniformly as the clause width grows. The abstract gives no value for \(\varepsilon_k\). Until one is computed, the improvement is a fact about exponents rather than about running times.

A perspective inside traces the split-and-list route from Max-2SAT to hypercliques.

[arXiv:2611.05082] Finding Hypercliques Faster Than Brute Force (Josh Alman, Baitian Li, Neha Pant, Kevin Pratt et al.)

FINE-GRAINED COMPLEXITY

k-Clique conjecture refuted, even if ω = 2

Vassilevska Williams and Zamir count weighted \(k\)-cliques in \(n\)-vertex graphs in \(n^{(\omega/3-c)k}\) time for every sufficiently large \(k\), with \(c > 0\) independent of both \(\omega\) and \(k\), refuting the \(k\)-Clique conjecture whatever the value of \(\omega\).

The \(k\)-Clique conjecture held that the matrix-multiplication approach, at roughly \(n^{\omega k/3}\) time, is essentially optimal for finding a \(k\)-clique. Vassilevska Williams and Zamir [arXiv:2611.09764] beat it by a constant \(c\) in the coefficient of \(k\), for every large enough \(k\). Because \(c\) does not depend on \(\omega\), the refutation holds even if \(\omega = 2\). The algorithm solves the more general problem of counting weighted \(k\)-cliques.

Any conditional lower bound obtained by reduction from \(k\)-Clique must now find another source of hardness or settle for a weaker statement. Read beside the lead story, the week has removed two of the field's standard assumptions.

The abstract states neither the value of \(c\) nor how large \(k\) must be.

[arXiv:2611.09764] The k-Clique hypothesis is dead, for good (Virginia Vassilevska Williams, Or Zamir)

BOOLEAN FUNCTIONS

Aaronson–Ambainis conjecture claimed proved

Turturean claims that every \(f\colon\{-1,1\}^n\to[-1,1]\) of degree at most \(d\) has a variable of influence at least \(c \mathrm{Var}(f)^{5/2}/d^6\), which by Aaronson and Ambainis would mean the acceptance probability of any \(T\)-query quantum algorithm can be approximated on most inputs by a classical algorithm making \(\mathrm{poly}(T)\) queries.

Aaronson and Ambainis conjectured that every bounded low-degree polynomial on the discrete cube has an influential variable. Turturean [arXiv:2611.09773] claims a proof, with an explicit bound: influence at least \(c \mathrm{Var}(f)^{5/2}/d^{6}\) for an absolute constant \(c > 0\). In the original formulation, for \([0,1]\)-valued polynomials on \(\{0,1\}^n\) with variance at least \(\varepsilon\), this gives a variable of influence at least \((\varepsilon/d)^7\).

The consequence was shown by Aaronson and Ambainis themselves: quantum query algorithms can be simulated classically, on most inputs, with polynomially many queries. Superpolynomial quantum speedups in the query model would then require structure, such as a promise on the inputs. The author describes the proof as elementary, with steps inspired by the work of others.

The paper is 60 pages, has a single author and comes with a Lean formalisation. A formalisation is only as strong as its statement, and the first check will be that the formal theorem is the one in the title.

[arXiv:2611.09773] A proof of the Aaronson-Ambainis conjecture (David Turturean)

CIRCUIT LOWER BOUNDS

Two lower bounds, one of them true

Unconditionally, either \(\mathrm{NE}\) contains a language requiring Boolean circuits of size at least \(2^n/(2n)\), which implies \(\mathrm{NP}\not\subseteq\mathrm{SIZE}[n^k]\) for every constant \(k\), or the constant-free Valiant conjecture \(\mathrm{VP}^0_{\mathbb{Z}} \ne \mathrm{VNP}^0_{\mathbb{Z}}\) holds.

Kabanets and Impagliazzo (2004) showed that derandomising polynomial identity testing yields circuit lower bounds. Chukhin, Gajulapalli, Golovnev and Mihajlin [arXiv:2611.07972] give a fine-grained version and observe that the particular identity tests the argument needs can be run over the integers without any derandomisation assumption. The tool is a deterministic PIT algorithm for syntactically set-multilinear circuits running in \(s^{O(1)}t^{5d/6}\) time. The result is a disjunction that holds outright: a \(2^n/(2n)\) Boolean lower bound in \(\mathrm{NE}\), or \(\mathrm{VP}^0_{\mathbb{Z}} \ne \mathrm{VNP}^0_{\mathbb{Z}}\).

Over a fixed finite field they give deterministic \(O(st^{d-1})\)-time PIT for size-\(s\) circuits computing degree-\(d\) polynomials in \(t\) variables. Improving this by a factor of \(t^{\varepsilon}\), even nondeterministically, would give either the same Boolean bound or a \(t^{1+\varepsilon/2}\) arithmetic lower bound for a \(\mathrm{VNP}\) family. Combined with range avoidance, an \(\mathrm{NP}\) algorithm for PIT over \(\mathbb{Z}\) would give a purely arithmetic win-win.

The theorem does not say which alternative holds. Nor does it say how one would find out.

[arXiv:2611.07972] A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT (Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin)

In depth2026-W45
Fine-grained complexity

After ETH, what holds the lower bounds up

Taking the claimed refutation of ETH as given, the MIT Hardness Group prove that Stearns and Hunt's 1990 Satisfiability Hypothesis is equivalent to Weak ETH, and that it preserves reduction-based, parameterised, gap and counting lower bounds up to an arbitrarily small loss in the exponent. Separately, Chukhin proves without any hypothesis that constant-depth circuits for \(k\)-OV in polylogarithmic dimension need \(n^{k-\varepsilon}\) gates.

Two papers this week answer the same question. If ETH has fallen, what do the field's hardness results stand on? [arXiv:2611.02650] answers with an older hypothesis. [arXiv:2611.06231] answers with no hypothesis at all, in a model weak enough to be analysed.

The background is the pair of claimed algorithms from OpenAI and Anthropic, which count the satisfying assignments of a \(k\)-CNF in time \((n+m)^{O(1)}2^{O(n\log\log n/\sqrt{\log n})}\). Both papers take these as refuting ETH and SETH. Neither paper's own theorems depend on those algorithms being correct.

Stearns and Hunt, again

The claimed exponent is \(o(n)\), which kills ETH. It is also \(n^{1-o(1)}\), which does not touch the Satisfiability Hypothesis (SH) that Stearns and Hunt stated in 1990: CNF SAT on inputs of length \(L\) has no \(O(2^{L^{1-\varepsilon}})\)-time algorithm for any constant \(\varepsilon>0\).

One answer leans on a hypothesis from 1990. The other leans on nothing, in a model small enough to be analysed.

Brunner, Demaine, Frei, Gomez, Hecher, Li and Lynch, writing as the MIT Hardness Group, prove SH equivalent to Weak ETH, which forbids \(2^{n^{1-\varepsilon}}(n+m)^{O(1)}\)-time algorithms for 3SAT on \(n\) variables. It is also equivalent to the \(k\)SAT version for each fixed \(k\ge 3\). The counting versions, #SH and Weak #ETH, are equivalent to each other, and so are the bounded-error randomised versions.

The proof has two steps. A parsimonious Tseitin encoding relates input length to the formula size \(n+m\). Sparsification then relates size to variable count. The usual ETH argument uses a fixed sparsification parameter, which here costs too much. Instead the parameter shrinks with \(n\), as \(n^{-\delta}\). This produces fewer branches but denser formulas, and \(\delta\) is chosen small enough that both exponents stay below one.

What survives, and at what price

The main result is a transfer rule. Take a reduction from 3SAT of size \(s\) to an instance of size \(N\le s^{b+o(1)}\). Under SH, it rules out \(2^{O(N^{1/b-\varepsilon})}\)-time algorithms for every \(\varepsilon>0\), and the same holds with a parameter \(k\) in place of \(N\).

The paper's table applies the rule to known reductions. Vertex Cover, Independent Set and 3-Colouring have no \(2^{O(n^{1-\varepsilon})}\) algorithms. Planar Hamiltonian Cycle has none in \(2^{O(n^{1/2-\varepsilon})}\). Graph Homomorphism, previously excluded at \(2^{o(n\log n)}\) under ETH, is now excluded only at \(2^{O(n^{1-\varepsilon})}\). Constant-gap hardness for Max-3SAT is rederived through Dinur's nearly linear PCP. Under #SH, #2SAT has no \(O(2^{(n+m)^{1-\varepsilon}})\) algorithm, even on formulas of constant degree.

The price is precision. The \(\varepsilon\) swallows logarithmic factors in the exponent, so \(2^{o(N)}\) and \(2^{o(N\log N)}\) bounds collapse into one. The \(2^{o(k\log k)}\) bound for \(k\times k\) Clique is lost. The paper points to a separate \(k\times k\) Clique Hypothesis, proposed by Szeider, for anyone who needs it back. Tight bounds of the Graph Homomorphism kind, stated to a logarithm in the exponent, now need more than SAT hardness alone. SH forbids saving a polynomial factor in the exponent, and the claimed algorithms save only a polylogarithmic one; that is the room the field now works in.

No hypothesis at all

Chukhin takes the other route. Exhaustive search for a hyperclique on \(\ell\) vertices, in an \(r\)-uniform hypergraph on \(m\) vertices, is a depth-two circuit with at most \(m^\ell\) gates. Amano showed in 2010 that this is almost optimal in constant depth, but only for constant \(\ell\). Chukhin extends the bound to hypercliques of polynomial size. Depth-\(h\) circuits need \(m^{\Omega(\ell)}\) gates for \(\ell\le m^{1/h-\varepsilon}\). When \(\ell=m^{o(1)}\) tends to infinity they need \(m^{(c_r-o(1))\ell}\) gates, with \(c_r\) tending to one as \(r\) grows.

Three consequences follow. Rossman's \(n^{k/4}\) bound for \(k\)-Clique, known for constant \(k\), extends to \(n^{\Omega(k)}\) gates for \(k\le n^{1/(h-1)-\varepsilon}\). Through a reduction of Choudhury, Limaye, Sreenivasaiah and Srinivasan, \(k\)-OV in dimension \((\log n)^{O(1)}\) needs \(n^{k-\varepsilon}\) gates at every fixed depth. That proves the \(k\)-OV Conjecture for constant-depth circuits in polylogarithmic dimension, where the earlier bound needed dimension \(n^\varepsilon\). A separate, simpler argument shows that depth-three circuits for 2-OV in dimension \((1+\eta)\log n\) need \(\Omega(n^2)\) wires, which answers a question of Kane and Williams.

The method plants a hyperclique in a dense random hypergraph. Earlier work planted into a sparse one and used the switching lemma, which fails once the edge probability tends to one. Here each gate is read as a multilinear polynomial. The circuit must eventually build a monomial touching every planted vertex, so some gate must multiply two smaller pieces into a larger one. Tal's Fourier tail bound for constant-depth circuits shows that this is unlikely at any fixed gate, because the gate cannot know where the planted set lies.

What remains open

SH itself is a conjecture, and the paper names fallbacks should it fail, down to ruling out quasipolynomial time. Chukhin's bounds hold only in constant depth. Against circuits of arbitrary depth, an \(n^{\Omega(k)}\) bound for \(k\)-Clique with \(k=\omega(1)\) would give \(\mathrm{NP}\not\subseteq\mathrm{P/poly}\). The general \(k\)-OV Conjecture remains open, even for \(k=2\). The paper also notes that the claimed SAT algorithms are not known to give \(f(k)n^{o(k)}\) algorithms for \(k\)-Clique, or \(n^{k-\varepsilon}\mathrm{poly}(d)\) algorithms for \(k\)-OV.

Elsewhere this week, [arXiv:2611.05082] refutes the hyperclique conjecture with arithmetic circuits beating brute force. The two results are consistent. One concerns constant-depth Boolean circuits, and an algorithm built from arithmetic circuits need not fit that model.

[arXiv:2611.02650] ETH is Dead, Long Live SH (MIT Hardness Group, Josh Brunner, Erik D. Demaine, Fabian Frei et al.) · [arXiv:2611.06231] Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors (Nikolai Chukhin)

Promise CSPs

Mod-\(p\) equations: four colours easy, three hard

Nakajima, Verwimp and Živný classify the promise problem of colouring the variables of a system \(x+y+z\equiv 0 \pmod p\), promised to have a solution that is nonconstant on every equation, so that no equation is monochromatic. For primes \(p\ge 5\) the problem is polynomial-time solvable with \(c\ge 4\) colours and NP-hard with \(c=3\), and the same holds for every finite Abelian group without elements of order 2 or 3. The tractable side comes from a new reduction built on Abelian embeddings.

The problem

Take a system of equations, each of the form \(x+y+z\equiv 0 \pmod p\). Suppose it is promised that some assignment satisfies every equation without giving all three variables of any equation the same value. For \(p\ne 3\) this simply rules out \((0,0,0)\). The task is weaker than finding that assignment: colour the variables with \(c\) colours so that no equation is monochromatic. In promise CSP notation this is \(\mathrm{PCSP}(\mathrm{Eqn}^*(\mathbb{Z}_p),\mathrm{NAE}_c)\) [arXiv:2611.04569].

The linear system alone is solved by Gaussian elimination. The ban on constant equations is what makes the exact problem NP-hard. Not-all-equal on \(c\) colours is the weakest target that still excludes constant tuples, so the question is whether the relation is promise-useful at all, and with how many colours.

Two cases were already settled. For \(p=2\) and \(c=2\) the problem is, after complementation, 1-in-3 versus NAE-3-SAT, which Brakensiek and Guruswami showed tractable. For \(p=3\) it is 3-rainbow versus \(c\)-colouring of 3-uniform hypergraphs, for which McDiarmid gave a randomised algorithm; deterministic algorithms for all \(c\) follow from the \(p=c=2\) case.

A reconfigurable relation admits no Abelian embedding, and the detrivialised equation relations have no single-coordinate moves at all.

The result

For every prime \(p\ge 5\) the classification is complete. With \(c\ge 4\) colours the search problem is solvable in polynomial time. With \(c=3\) even the decision version is NP-hard. With \(c=2\) the problem is not well defined, because some instances satisfy both the yes and the no condition. The theorem extends to every nontrivial finite Abelian group with no elements of order 2 or 3.

The four-colour algorithm is not captured by the standard tools. The authors show that neither \(k\)-consistency, for any fixed \(k\), nor the combined BLP+AIP relaxation solves it. It is a singleton algorithm in Zhuk's sense.

The idea of the algorithm

An Abelian embedding, a notion Bhangale, Khot and Minzer introduced for quantitative approximation of satisfiable CSPs, maps the values of a relation into an Abelian group so that, coordinate by coordinate, every tuple of the relation sums to zero, and not trivially. The second ingredient is a \(c\)-rounding: a colouring of the nonzero group elements such that, in any nonzero solution of \(g_1+g_2+g_3=0\), the nonzero entries do not all share a colour. \(\mathbb{Z}_p\) has a 4-rounding for \(p\ge 5\). \(\mathbb{Z}_2\) and \(\mathbb{Z}_3\) have none, because of \(1+1+0=0\) and \(1+1+1=0\).

The algorithm repeatedly solves the linear system for a solution in which some variable is nonzero, colours every nonzero variable by the rounding, and deletes those variables with every constraint they touch. Any constraint touched for the first time has two or three nonzero entries summing to zero, so it is already nonmonochromatic whatever happens later. If no nonzero solution exists, the promised solution must map entirely to zero, and the instance reduces to the subrelation sitting over zero. For \(\mathrm{Eqn}^*(\mathbb{Z}_p)\) that subrelation is empty, so the procedure finishes. In general it gives a polynomial-time reduction from \(\mathrm{PCSP}(R,\mathrm{NAE}_c)\) to the same problem with a strengthened promise. The same framework recovers the Brakensiek–Guruswami algorithm, through an embedding of 1-in-3 into \(\mathbb{Z}\) with the sign as a 2-rounding. The authors also show the reduction can be carried out by constraint singleton AIP, and characterise such reductions algebraically along the lines of Dalmau and Opršal.

The hardness side

Recent conditional hardness, by Banakh, Barsukov and Nakajima under the Rich 2-to-1 conjecture, covers symmetric reconfigurable relations: those whose tuples are connected by single-coordinate changes. For symmetric relations the two regimes are disjoint. A reconfigurable relation admits no Abelian embedding, and the detrivialised equation relations have no single-coordinate moves at all. The three-colour hardness therefore needs a different route, and it is unconditional.

That route is an additive-combinatorial rigidity theorem. Call a partition of \(\mathbb{Z}_p\) into three parts valid if \((0,0,0)\) is the only solution of \(x+y+z\equiv 0\) lying inside one part. For every prime \(p\ge 7\) there is exactly one valid partition up to scaling and relabelling: cut \(\{0,\ldots,p-1\}\) into thirds. The proof uses the Cauchy–Davenport and Vosper theorems. For \(p=5\) there are two, and that case is handled separately, by a minion homomorphism to a promise problem on an unbalanced directed cycle already known to be NP-hard.

What remains open

The authors name the complexity of \(\mathrm{PCSP}(\mathrm{Eqn}^*(\mathbb{Z}_2^n),\mathrm{NAE}_c)\) for \(n\ge 2\) and large \(c\) as an open question. These relations have Abelian embeddings, but not of a kind the framework can use. The tractability argument extends to equations of arity \(r\), with more colours, but no matching hardness is claimed there.

The broader question is how far Abelian embeddings explain promise-usefulness in general. Concurrent work of Chan and Ng also gives such embeddings an algorithmic role, on the quantitative side. One classified family is evidence, not a theory. It is, though, a family that the usual relaxations miss and that the reconfiguration-based hardness cannot reach, and both facts are now on record.

[arXiv:2611.04569] Abelian embeddings make useful promises: approximation of detrivialised equations (Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný)

Proof complexity

Resolution lower bounds now provable in constant depth

Arteche, de Rezende, Khaniki and Risse show that a satisfying assignment can be extracted from a Resolution proof of a trivial Resolution lower bound by polynomial-size \(\mathbf{TC}^0\) or quasipolynomial-size \(\mathbf{AC}^0\) circuits. They prove the Atserias–Müller lower bound in quasipolynomial-size constant-depth Frege for every size parameter, and show that the Proof Analysis Problem is NP-hard under quasipolynomial-time reductions for any system that p-simulates depth-2 Frege. Separately, Riis proves linear degree lower bounds for Nullstellensatz and Polynomial Calculus, which give a four-way classification of uniform polynomial consequences over fields of positive characteristic.

Two papers this week ask how much a proof system can prove about proofs, and how hard proofs in a weak system can be forced to be. One moves a central Resolution lower bound down into constant-depth Frege. The other replaces logarithmic degree bounds with linear ones across a whole classification.

What was known

In 2019 Atserias and Müller showed that Resolution cannot be automated unless \(\mathrm{P}=\mathrm{NP}\). Their reduction maps a CNF \(\varphi\) to a formula \(\mathrm{Ref}_s(\varphi)\), which says that \(\varphi\) has a Resolution refutation of length \(s\). If \(\varphi\) is satisfiable, \(\mathrm{Ref}_s(\varphi)\) has short refutations. If \(\varphi\) is unsatisfiable, every refutation is exponentially long. Pudlák had asked when proof systems can prove such lower bounds about themselves, and called that question more fundamental than automatability.

Last year Arteche, Atserias, de Rezende and Khaniki made the question computational. They defined the Proof Analysis Problem. You are given \(\varphi\) and a proof of \(\neg\mathrm{Ref}_s(\varphi)\), and you must decide whether \(\varphi\) is satisfiable, or find an assignment if it is. They gave a polynomial-time extraction algorithm for Resolution proofs and formalised it in \(\mathsf{PV}_1\), so Extended Frege proves the Atserias–Müller bound. They also showed the problem is NP-hard for Extended Frege. Their algorithm looked inherently sequential. Li, Li and Ren (STOC 2026) obtained quasipolynomial constant-depth Frege formalisations of some Resolution lower bounds, but only for \(s=2^{\Omega(n)}\). In that regime the formula is padded to exponential size, and brute force becomes cheap.

The classification exists, and no algorithm can say which case you are in.

What is new

Arteche, de Rezende, Khaniki and Risse [arXiv:2611.08305] give an extraction algorithm in polynomial-size \(\mathbf{TC}^0\) and in quasipolynomial-size \(\mathbf{AC}^0\). They prove the correctness of the \(\mathbf{AC}^0\) version in the bounded-arithmetic theory \(\mathsf{T}^4_2(\alpha)\), which corresponds to depth-4 Frege. Translated into propositional form, this gives quasipolynomial-size constant-depth Frege proofs of the Atserias–Müller lower bound for every \(s\), including \(s=n^{O(1)}\). That is progress on Pudlák's question, though it does not settle it, since the proofs are quasipolynomial rather than polynomial.

Three consequences follow. The Proof Analysis Problem is NP-hard, under quasipolynomial-time reductions, for every system that p-simulates depth-2 Frege. So the basic Atserias–Müller route, using Ref formulas for Resolution, cannot show that automating constant-depth Frege is hard. Next, for each \(d\ge3\), the system \(\mathsf{PK}_{d+1/2}\) is automatable in quasipolynomial time on Ref formulas if and only if it is automatable on all CNFs. Finally, Haken's pigeonhole lower bound gets quasipolynomial depth-2 proofs in the polynomial-size regime.

The technique replaces the earlier greedy restriction with the original random restriction of Atserias and Müller. That restriction kills every clause of block-width above \(c\log|\pi|\), so the algorithm never has to build it. It simply ignores wide clauses. For each narrow clause, in parallel, it tries every possible pointer structure for the Delayer's bookkeeping, at cost \(s^{O(\log|\pi|)}\), and checks consistency with constant-depth circuits. Correctness of the old sequential algorithm guarantees that some clause must encode a satisfying assignment. To remove the quasipolynomial guessing, the authors add dummy layers to the Delayer's grid, which gives the \(\mathbf{TC}^0\) version. To formalise the argument, they derandomise the restriction with \(k\)-wise independence and approximate counting carried out inside the theory.

Linear degree, four types

Riis [arXiv:2611.07280] works with uniform families: systems of polynomial equations generated by fixed bounded-degree patterns as the universe size \(n\) grows, for example the algebraic translations of first-order sentences. His 2008–2009 classification sorted refutations of such families into four types. The degree lower bounds behind it were only \(\Omega(\log n)\) for Nullstellensatz and \(\Omega(\log\log n)\) for Polynomial Calculus. He now proves linear lower bounds for both systems, and extends the result from refutations to the derivation of arbitrary uniform targets.

Beyond a finite initial range, exactly one of four things happens:

  • T1: degree stays bounded.
  • T2: degree is at least linear in \(n\).
  • T3: a periodic mixture, with low degree on some residue classes and linear degree on the rest.
  • T4: infinitely many recurring finite degrees, with finite \(\Omega(n)\) peaks at arbitrarily large sizes.

Both systems assign the same type. Telling any two types apart is undecidable, even for refutations. The bounds, the classification and the undecidability results are formalised in Lean.

The engine is periodicity. For a fixed degree budget \(d\), whether a target can be derived within that budget becomes periodic in \(n\) after an onset linear in \(d\), with period the least power of the characteristic exceeding a label budget linear in \(d\). A degree that does not recur can only occur before its onset; turning that statement around gives the linear bound. An example with \(\Theta(n)\) degree shows that linear is optimal in general. The exponential size bounds count every coefficient, zeros included. Sparse representations are a different measure, and the paper says so.

Why it matters, and what is open

For a reader who works on CSP, Riis's result has a familiar shape: a classification of uniform families by structure. The difference is instructive. The classification exists, and no algorithm can say which case you are in.

The Frege paper redraws the map of automatability. Hardness for constant-depth Frege now needs new ideas, or Ref formulas built for stronger systems than Resolution. A polynomial-time version of the NP-hardness reduction would follow from Pudlák's open problem: polynomial-size \(\mathbf{AC}^0\)-Frege proofs of Resolution lower bounds. Whether the \(\mathbf{TC}^0\) algorithm can be proved correct in the matching theory \(\mathsf{VTC}^0\) is also unresolved. The current argument reasons about objects of quasipolynomial size, which that theory cannot handle.

[arXiv:2611.08305] The Proof Analysis Problem for Constant-Depth Frege (Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse) · [arXiv:2611.07280] Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus (Søren Riis)

The long viewhow we got here
THE LONG VIEW

Splitting the variables: how the hyperclique wall was built

Alman, Li, Pant, Pratt and Williams count \(k\)-hypercliques in \((k-1)\)-uniform hypergraphs in \(O(n^{k-\varepsilon_k})\) time, giving Max-\(k\)SAT in \(2^{(1-\delta)n}\cdot\mathrm{poly}(m,n)\) for every \(k\); this caps two decades of reductions that began with Williams's three-block Max-2SAT algorithm, and the result is a preprint, not yet refereed.

The template

Every algorithm in this story repeats one move. In 1969 Strassen found a 7-term decomposition of \(2\times 2\) matrix multiplication, and recursion turned it into circuits of size \(O(n^{\log_2 7})\) [S1]. In 1978 Itai and Rodeh applied fast matrix multiplication to triangles: if \(A\) is the adjacency matrix of a graph, \(\mathrm{tr}(A^3)\) is six times the number of triangles [S1]. In 1985 Nešetřil and Poljak reduced \(k\)-Clique to triangle detection by grouping vertices into tuples. They detected \(k\)-cliques in \(O(n^{\omega k/3})\) time for \(k\) divisible by 3 [S2, S3, S4].

The recipe is short. Find a structure whose count is a trilinear form, then evaluate it with matrix multiplication.

Splitting the variables

In 2004 Ryan Williams applied the recipe to exponential-time problems (ICALP 2004; Theoret. Comput. Sci. 2005) [S5, S6]. Split the \(n\) variables into three blocks. List the \(2^{n/3}\) partial assignments of each block as vertices. Weight the edges so that a triangle's weight equals the number of clauses its full assignment satisfies. Then guess the weight on each of the three edge classes, which gives \(O(m^3)\) choices, and count ordinary triangles.

This counts the optimal solutions of Max-2SAT and Max-Cut in \(O(m^3\cdot 2^{\omega n/3})\) time. It was the first exponential improvement over trivial search [S5]. With \(\omega<2.376\) the base is about \(1.732\) [S7]. Koivisto cut the polynomial overhead to roughly \(nm\) in 2005 [S7].

Three blocks are not enough

A 3-clause can touch three blocks, so its contribution no longer fits on an edge. The natural repair uses \(\ell\ge k+1\) blocks and \(k\)-uniform hyperedges. With only \(k\) blocks, one hyperedge covers a whole assignment and nothing is saved. According to Lincoln, Vassilevska Williams and Williams, Williams's 2007 thesis reduced Max-3SAT to finding 4-hypercliques in 3-uniform hypergraphs. An \(O(n^{4-\varepsilon})\) algorithm there would give Max-3SAT in \(O(2^{(1-\delta)n})\) [S2]. Alman et al. instead date the question to the 2005 paper [S1]; the sources disagree.

In a 2010 note Williams asked directly whether the order-3 product could be computed in \(O(n^{4-\varepsilon})\) time. LVW18 record unsuccessful attempts by several researchers [S2]. The product itself was older: Mesner and Bhattacharya had defined a ternary product of 3-tensors in 1990 [S2].

Meanwhile Max-3SAT moved only slightly. Alman, Chan and Williams (FOCS 2016) reached \(2^{n-n/O(\log^2 n \log^2\log n)}\) [S3], which LVW18 described as the fastest Max-\(k\)SAT algorithm [S2]. The saving was \(2^{o(n)}\).

The conjectures harden

In FOCS 2015 Abboud, Backurs and Vassilevska Williams showed that faster context-free parsing would imply a breakthrough \(k\)-Clique algorithm. They treated the optimality of the matrix-multiplication approach as a conjecture of graph algorithms and parameterized complexity [S8]. LVW18 then wrote it down as the \(k\)-Clique Hypothesis, a lower bound of \(n^{\omega k/3-o(1)}\), citing that paper [S2].

The SODA 2018 paper of Lincoln, Vassilevska Williams and Williams stated two more hypotheses [S2]:

  • Hyperclique. For \(\ell>k>2\), finding an \(\ell\)-hyperclique in a \(k\)-uniform hypergraph needs \(n^{\ell-o(1)}\) time.
  • Max-\(k\)SAT. Max-\(k\)SAT needs \(2^{n-o(n)}\) time.

It also gave a reason to believe them. The \(k\)-wise product has border rank exactly \(n^{k+1}\), which the authors said “completely rules out the arithmetic circuit approach for \(k>2\)”. A faster algorithm, they concluded, “must use radically different techniques” [S2]. From the hypotheses they derived, among other bounds, \(m^{k/(k-1)-o(1)}\) lower bounds for Shortest Cycle in sparse directed graphs [S2].

Later work leaned on the same assumption. It was used for induced 4-cycles, hypercycles, lowest common ancestors in DAGs, database joins, CSPs and Klee's measure problem [S3]. At STOC 2026 Dudek, Fischer, Gokaj, Jin, Künnemann, Mao and Redžić added the \(k\)-AP Hypothesis. It says that for \(k\ge 4\), no \(O(n^{2-\varepsilon})\) algorithm detects a nontrivial length-\(k\) arithmetic progression in a subset of \(\{0,\ldots,n\}\). They linked it to hyperclique detection [S9, S1]. The case \(k=3\) is excluded because FFT handles it in near-linear time [S1].

Where the barrier leaked

The rank argument rests on a 1973 theorem of Strassen: for three-mode tensors, rank characterises multiplicative complexity [S1]. With four or more modes, circuits can have several layers of products, and rank stops bounding size. The standard example is \((\sum_i x_i z_i)(\sum_j y_j w_j)\). It has a linear-size circuit, yet its flattening is an identity matrix, so its rank is \(n^2\) [S1].

Naslund's partition rank (2020) gave a finer measure [S1]. In 2026 Brand, Kaski and Wang, and a larger group including Curticapean, proposed partition-rank notions meant to extend Strassen's bound to more modes [S1]. Chan et al. note that this work identified the weakness of the rank argument but produced no new hyperclique lower bounds [S3]. The LVW18 theorem remains true. What failed is the conclusion drawn from it.

This week

Alman, Li, Pant, Pratt and Williams [arXiv:2611.05082] give uniform arithmetic circuits of size \(O(n^{k-\varepsilon_k})\) for the \(k\)-hyperclique tensor in \((k-1)\)-uniform hypergraphs, with \(\varepsilon_k=2^{-\Theta(2^k)}\) [S1]. They feed this into the split-and-list reduction with \(k+1\) blocks. The result is Max-\(k\)SAT, #Max-\(k\)SAT and Max-Degree-\(k\)CSP in \(2^{(1-\delta_k)n}\cdot\mathrm{poly}(n,m)\), with \(\delta_k=\varepsilon_{k+1}/(k+1)\), and \(k\)-AP detection in \(O(n^{2-2\varepsilon_k/k})\) [S1]. The paper states that its main result was obtained by ChatGPT 6 Pro, after the authors suggested the algebraic approach [S1].

One day later, Chan, Itakura, Ma and Yu independently gave an \(O(n^{4-\varepsilon})\) algorithm for 4-hypercliques in 3-uniform hypergraphs. They use only rectangular matrix multiplication and obtain Max-3SAT in \(2^{(1-\varepsilon/4+o(1))n}\) [S3].

The claimed October refutations of ETH did not already give these bounds, because no sparsification lemma is known for Max-\(k\)SAT [S1]. In the same week, Vassilevska Williams and Zamir [arXiv:2611.09764] claim an \(n^{(\omega/3-c)k}\) algorithm for \(k\)-Clique for large \(k\). That would also overturn the Nešetřil–Poljak bound.

None of this has been refereed. A saving of \(2^{-\Theta(2^k)}\) in the exponent refutes a conjecture; it does not yet speed up a solver. How large the savings can be for each \(k\) is open.

This week’s result: [arXiv:2611.05082] Finding Hypercliques Faster Than Brute Force (Josh Alman, Baitian Li, Neha Pant, Kevin Pratt et al.)

The technique: Split-and-list reduction to (hyper)clique counting

The reduction turns an exponential search over assignments into a polynomial problem on a graph with \(N=2^{n/3}\) vertices per part. Fast matrix multiplication then beats \(2^n\).

For Max-2SAT, split the variables into blocks \(A,B,C\). Each partial assignment of a block becomes a vertex. Charge every clause to one edge class covering the blocks it touches; a 2-clause touches at most two blocks. Then the weight of triangle \((a,b,c)\) is the number of clauses satisfied by the full assignment. Guess a weight \(g_e\) for each edge class, and let \(M_e\) be the 0/1 matrix of edges with that weight. Then \(\mathrm{tr}(M_{AB}M_{BC}M_{CA})\) counts the assignments with that weight profile.

Toy instance. Take one variable per block: \(x_1\in A\), \(x_2\in B\), \(x_3\in C\). The clauses are \(C_1=(x_1\vee x_2)\), \(C_2=(\neg x_2\vee x_3)\), \(C_3=(\neg x_1\vee\neg x_3)\) and \(C_4=(x_2)\). Charge \(C_1,C_4\) to \(AB\), \(C_2\) to \(BC\) and \(C_3\) to \(CA\). The edge weights are:

  • \(w_{AB}(x_1,x_2)\): \((0,0)\mapsto 0\), \((0,1)\mapsto 2\), \((1,0)\mapsto 1\), \((1,1)\mapsto 2\).
  • \(w_{BC}(x_2,x_3)\): \(1,1,0,1\) in the same order.
  • \(w_{CA}(x_3,x_1)\): \(1,1,1,0\) in the same order.

The assignment \((0,1,1)\) gives \(2+1+1=4\) and satisfies every clause. Summing the traces over all triples with \(g_1+g_2+g_3=t\) gives 3 assignments at \(t=2\), 4 at \(t=3\) and 1 at \(t=4\). This agrees with brute force, so the method counts optima, not merely detects them.

There are \(O(m^3)\) guesses, each costing \(O(N^{\omega})\), for \(O(m^3\cdot 2^{\omega n/3})\) in total. For \(k\)-clauses the same construction needs \(k+1\) blocks and \(k\)-uniform hyperedges. A fast \((k+1)\)-hyperclique counter then plays the part of matrix multiplication, and that counter is what this week's paper supplies.

Timeline
1969Strassen: 7-term decomposition of \(2\times2\) matrix multiplication, circuits of size \(O(n^{\log_2 7})\).
1978Itai and Rodeh: triangle detection by matrix multiplication; \(\mathrm{tr}(A^3)\) is six times the triangle count.
1985Nešetřil and Poljak: \(k\)-Clique in \(O(n^{\omega k/3})\) by reduction to triangles.
2004–2005R. Williams: split-and-list counts Max-2SAT optima in \(O(m^3\cdot 2^{\omega n/3})\), about \(1.732^n\).
2015Abboud, Backurs and Vassilevska Williams: faster CFG parsing would beat \(k\)-Clique; the optimality of \(n^{\omega k/3}\) becomes a working hypothesis.
2016Alman, Chan and Williams: Max-3SAT in \(2^{n-n/O(\log^2 n\log^2\log n)}\), a \(2^{o(n)}\) saving.
2018Lincoln, Vassilevska Williams and Williams: hyperclique and Max-\(k\)SAT hypotheses; the \(k\)-wise product has border rank \(n^{k+1}\).
2026Dudek et al. (STOC): the \(k\)-AP Hypothesis, linked to hyperclique detection.
2026Alman, Li, Pant, Pratt and Williams: \(k\)-hyperclique counting in \(O(n^{k-\varepsilon_k})\); Max-\(k\)SAT in \(2^{(1-\delta)n}\); Chan et al. independently settle the 3-uniform case a day later.
Sources
  1. [S1] Finding Hypercliques Faster Than Brute Force (Alman, Li, Pant, Pratt, Williams)
  2. [S2] Tight Hardness for Shortest Cycles and Paths in Sparse Graphs (Lincoln, Vassilevska Williams, Williams)
  3. [S3] The 3-Uniform Hyperclique Hypothesis is False (Chan, Itakura, Ma, Yu)
  4. [S4] Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
  5. [S5] A new algorithm for optimal constraint satisfaction and its implications (R. Williams, author PDF)
  6. [S6] Exact Algorithms for Maximum Two-Satisfiability (Encyclopedia of Algorithms)
  7. [S7] Optimal 2-constraint satisfaction via sum–product algorithms (Koivisto)
  8. [S8] If the Current Clique Algorithms are Optimal, so is Valiant's Parser (Abboud, Backurs, Vassilevska Williams)
  9. [S9] Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection (Dudek et al., STOC 2026)
The columnShell Scott
Shell Scott, Night Desk

Inventory After the Refutations

The late column. The week's papers set against each other, looking for the pattern nobody wrote down. Plain words. No favourites.

The week had three refutations and one replacement. The replacement is weaker than what it replaces.

Alman, Li, Pant, Pratt and Williams [arXiv:2611.05082] count \(k\)-hypercliques in \((k-1)\)-uniform hypergraphs in \(O(n^{k-\varepsilon_k})\) time for every fixed \(k\). The route is a uniform family of arithmetic circuits for the hyperclique tensor, the higher-order relative of the matrix multiplication tensor. The hyperclique conjecture goes. So does exhaustive search for Max-\(k\)SAT, which drops to \(2^{(1-\varepsilon)n}\). So does the \(n^2\) barrier for detecting \(k\)-term arithmetic progressions. The abstract does not state \(\varepsilon_k\). It says only that it is positive.

Vassilevska Williams and Zamir [arXiv:2611.09764] do the same to \(k\)-Clique: \(n^{(\omega/3-c)k}\) for large \(k\), with \(c\) independent of both \(\omega\) and \(k\). The conjecture fails even if \(\omega=2\). The algorithm also counts weighted cliques.

Those two are algorithms. The third refutation is a premise. Brunner, Demaine and the MIT Hardness Group [arXiv:2611.02650] open by stating that ETH is false and proceed from there. The refutation itself is not on this week's list. What they offer in its place is Stearns and Hunt's SH, proved equivalent to Weak ETH, which rules out \(2^{n^{1-\varepsilon}}\) algorithms for 3SAT. Reductions still carry hardness. The cost shows in the exponent. A blowup \(N=s^b\) used to rule out \(2^{o(N^{1/b})}\). It now rules out \(2^{N^{1/b-\varepsilon}}\). The framework survives. The sharpest bounds do not.

Now the other direction. Chukhin [arXiv:2611.06231] shows that exhaustive search for hyperclique is hard to beat in constant depth. Depth-\(h\) circuits need \(m^{\Omega(\ell)}\) gates for \(\ell\le m^{1/h-\varepsilon}\). Rossman's clique bound extends from constant-size to polynomial-size cliques. Through a reduction of Choudhury, Limaye, Sreenivasaiah and Srinivasan, the \(k\)-OV conjecture becomes a theorem for constant-depth circuits in polylogarithmic dimension.

Same week, same problem, opposite conclusions, no contradiction. The fast algorithms are built the way matrix multiplication is built. Nothing in their abstracts claims constant depth, and Chukhin's bounds say they cannot have it. The conjecture did not die everywhere. It moved into a model where it can be proved.

That is the drift. Hypotheses once stated for all algorithms are coming back in two forms. One is a theorem about a restricted model. The other is a weaker hypothesis with a softer exponent. Li's attention note [hexagon:2611.00132v1] records where one lower bound now stands. The quadratic bound for attention rests on low-dimensional Orthogonal Vectors, which no open satisfiability hypothesis is known to imply. This week's only unconditional support for that problem is Chukhin's \(\Omega(n^2)\) wires for depth-three 2-OV in logarithmic dimension. It covers depth three.

The Hexagon queue shows the opposite habit. AI-assisted manuscripts derive corollaries from the claimed subexponential #SAT engines: Eulerian circuit counting [hexagon:2611.00088v1], exact Clifford+T amplitudes [hexagon:2611.00090v1], the parity of \(\pi(x)\) [hexagon:2611.00116v1]. They are stated as conditional, which is correct. The Eulerian result rests on a Hamiltonian-cycle result that rests on the claim. A conditional result is worth exactly its condition, and stacking does not raise the value. The more useful entry from the same source is the barrier paper [hexagon:2611.00149v1]. It asks what those engines cannot do.

The week also showed what breaking a barrier can cost. Curticapean [arXiv:2611.03636] computes \(n\times n\) permanents in \(O^*((2-\varepsilon)^n)\) operations over every commutative ring, with \(\varepsilon=10^{-40}\). Ryser's \(2^n\) falls and a problem from Knuth is closed. Read it as a discount coupon. Against \(2^n\) the saving is a factor of about \(e^{-n\varepsilon/2}\). It halves the bill once the matrix has roughly \(1.4\times10^{40}\) rows. Nobody will redeem it. It still settles the question: \(2^n\) was a habit, not a law. The hyperclique and clique papers have the same shape, with exponents the abstracts leave unstated.

So the inventory is short. Three conjectures fell this week. One returned as a theorem, at constant depth.

— The value of \(\varepsilon_k\) does not appear in the hyperclique abstract.

In briefeverything else that appeared this week

arXiv cs.CC 93 papers

The arXiv listing for cs.CC, moderated for scope, not refereed.

Get Permanent Results Faster by Counting Stars Radu Curticapean [arXiv:2611.03636]
Curticapean computes \(n\times n\) permanents with \(O^*((2-\varepsilon)^n)\) arithmetic operations over every commutative ring, for \(\varepsilon=10^{-40}\), by running the Binet–Minc identity through a dynamic programme; this solves a problem stated in Knuth's The Art of Computer Programming and also gives algebraic branching programs of the same size.
Composition Theorem for Randomized Query Complexity Samruddhi Pednekar, Supartha Podder [arXiv:2611.08574]
Pednekar and Podder prove \(R(f\circ g)=\Omega(R(f)R(g)/\log(n+1))\) for all Boolean functions \(f\) and \(g\), partial ones included, which together with the known upper bound settles composition for bounded-error randomised query complexity up to logarithmic factors.
The CNF Encoding Complexity of Boolean Functions Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux [arXiv:2611.05614]
Krapivin, Przybocki and Subercaseaux show that a function computable in nondeterministic time \(t\), using \(m\) bits of advice of which at most \(b\) are read per input, has a CNF encoding with \(\widetilde{O}(t+\sqrt{mb})\) clauses; as a consequence every \(k\)-CNF function on \(n\) inputs has an encoding with \(n^k/2^{\Omega_k(\sqrt{\lg n})}\) clauses, although any encoding using only bounded-width clauses needs \(\Omega_k(n^k/\lg n)\) in the worst case.
A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy [arXiv:2611.07309]
Bandekar, Sharma and Velusamy characterise the single-pass streaming space of Boolean CSP satisfiability in the strict-turnstile model, where constraints may be inserted and deleted, for every fixed constraint language that is not trivially satisfiable; the governing quantity is the integer capturing degree, where non-redundancy governs the insertion-only case.
Parity Decision Trees of Depth \(O(4^d \log\|\widehat f\|_1)\) for Boolean Functions \(f\) of \(F_2\)-Degree \(d\) Shengyu Zhang [arXiv:2611.03452]
Zhang proves that every Boolean function of \(\mathbb{F}_2\)-degree \(d\ge2\) has a deterministic parity decision tree of depth \(O(4^d\log\|\widehat f\|_1)\), improving the previous \(O(2^{d^2/2}\log^{d-2}\|\widehat f\|_1)\) bound of Tsang, Wong, Xie and Zhang.
Tensor value and the 9/4 bound for matrix multiplication Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter [arXiv:2611.09716]
Doğan, Lysikov, Sakabe and Walter give an exposition of OpenAI's reported bound \(\omega\le 9/4\) over every field, replacing the spectral points of the original proof with a fractional symmetrised Coppersmith–Winograd tensor value and proving a superadditivity inequality for it on partially direct sums.
Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting Mengyang Wu, Minghao Wang [arXiv:2611.02560]
Wu and Wang derive lower bounds that are only as sound as the AI-produced counting and contraction theorems they build on: an \(\mathsf{E}^{\mathsf{NP}}\) language requiring \(\Omega(m\sqrt{\log m}/\log\log m)\) gates over unbounded AND/OR with binary XOR, and \(\Omega(m\sqrt{\log m})\) gates for a bounded binary basis with a linear budget of XOR and symmetric gates, both infinitely often.
The sum-of-squares complexity of linear-algebraic principles Dmitriy Kunisky, Xifan Yu [arXiv:2611.05250]
Kunisky and Yu show that sum-of-squares proofs of the Weak Rank Principle need degree exactly \(2r+2\), that the Tight Frame Principle has a degree-4 proof, and that proving a right inverse of an \(n\times n\) matrix is also a left inverse needs degree exactly \(2n+2\).
Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick [arXiv:2611.05511]
Brakensiek, Huang, Potechin and Zwick use Sherali–Adams relaxations to raise the lower bound, under the Unique Games Conjecture, on the approximation ratio achievable in polynomial time for Multiway Cut above the previous 1.20016; the best known algorithm achieves 1.2787.
TFNP in the Random Oracle Model Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten et al. [arXiv:2611.05308]
Fleming, Göös and eight co-authors determine which of the major \(\mathsf{TFNP}\) subclasses are hard in the random oracle model, a setting that sits between one-way functions and the stronger structured assumptions, such as LWE, from which hardness was previously known.
Fine-Grained Complexity Across the Computational Phase Transition Zhe Ju, Jingcheng Liu, Yitong Yin [arXiv:2611.02702]
Ju, Liu and Yin show that for the hard-core model on \(n\)-vertex graphs of maximum degree \(d\ge3\), at fugacity \((1+\delta)\lambda_c(d)\) for sufficiently small \(\delta\ge0\) that may vanish with \(n\), the worst-case mixing time of Glauber dynamics is \(\exp\{\Theta(n\delta^2/d)\}n^{1+\Theta(1)}\).
A Circuit Complexity Trichotomy For Regular Languages Stefan Göller, Amaldev Manuel [arXiv:2611.03615]
Göller and Manuel prove that the non-uniform, unbounded fan-in circuit complexity of every regular language is \(O(1)\), between \(\Omega(\log n)\) and \(O(\log n\log\log n)\), or \(\Theta(n)\), and characterise the middle class in terms of algebra, word congruences, regular expressions and logic.
A Width Hierarchy of Monotone Algebraic Branching Programs Julian Dörfler, Alexander Rogovskyy [arXiv:2611.06608]
Dörfler and Rogovskyy prove a strict infinite width hierarchy \(\mathsf{mVBP}_2\subsetneq\mathsf{mVBP}_3\subsetneq\cdots\) for monotone algebraic branching programs, using depth lower bounds for iterated matrix multiplication; in the non-monotone case Ben-Or and Cleve showed width 3 suffices.
What remains of the planar induced minor conjectures? Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski [arXiv:2611.09627]
Czyżewska, Masařík, Pilipczuk and Rzążewski examine what is left of the conjectures that Maximum Weight Independent Set and List 3-Colouring are polynomial-time solvable in \(H\)-induced-minor-free graphs for planar \(H\), and of the related balanced-separator conjecture, after Bonnet and Chang refuted the independent-set part.
Mortality Is Undecidable for \(2 \times 2\) Integer Matrices Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu [arXiv:2611.06562]
Quartz, Shevchenko, De Sterck and Liu prove that matrix mortality is undecidable for finite families of \(2\times2\) integer matrices, settling the one dimension left open; the problem is trivially decidable in dimension one and has been known undecidable from dimension three since 1970.
Fourier Entropy Bounds via Approximations Manaswi Paraashar, Nitin Saurabh [arXiv:2611.06451]
Paraashar and Saurabh bound the Fourier entropy of a Boolean function by \(O(\log(1+\|\widehat f\|_{1,1/3}))\), the log of its approximate spectral norm, which gives \(\mathbb H(\widehat f^{ 2})=O(\mathsf R^\oplus(f))\) in terms of randomised parity-query complexity.
Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion Xiaohong Cai, Mingyang Zhu [arXiv:2611.02684]
Cai and Zhu determine the information complexity of matrix multiplication over finite fields on uniform inputs up to an additive constant; for binary inner product with error \(\varepsilon\) it lies between \((1-2\varepsilon)m-4.772\) and \((1-2\varepsilon)m\), answering a question of Braverman, Garg, Pankratov and Weinstein.
Semidirect sums of tensors and the matrix multiplication exponent Baitian Li [arXiv:2611.04175]
This is the arXiv copy of Li's exposition of the claimed \(\omega\le 9/4\) bound, built around the untwisting lemma for semidirect sums of tensors.
The Complexity of Unpredictability Aryan Agarwala, Dani Dorfman [arXiv:2611.05956]
Agarwala and Dorfman introduce middle-bit predictors and the problem UNPRED: given predictor circuits and \(\varepsilon\), deterministically output a multiset of strings on which every predictor succeeds with probability below \(1/2+\varepsilon\). They study its complexity, including a version restricted to \(\mathsf{TC}^1\) predictors.
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs Oliver Janzer, Peter Manohar [arXiv:2611.03145]
This is the arXiv version of the Janzer–Manohar \(2^{\Omega(\sqrt k)}\) length lower bound for binary linear 3-query LCCs, which matches Reed–Muller codes.
Precedence Constraint Scheduling on a Fixed Number of Machines Klaus Jansen [arXiv:2611.09392]
Jansen gives a deterministic exact algorithm for \(P_m\mid\mathrm{prec},p_j=1\mid C_{\max}\) that runs in polynomial time for every fixed \(m\ge3\); the degree is \(6m^2+13m+1\), or 94 for three machines.
Hardness of Unique Shortest Vectors and Bounded Distance Decoding Sergei Kudria, Jason Luo [arXiv:2611.09497]
Kudria and Luo prove randomised NP-hardness of uSVP at every constant uniqueness factor above one, and of BDD at every fixed fraction below half the minimum distance, in decision and search versions and in every \(\ell_p\) norm with \(1\le p<\infty\).
Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields Bin Fu, Yunhui Fu [arXiv:2611.02385]
Fu and Fu prove exponential lower bounds, in total variable-occurrence cost, for exactly representing explicit signed modular predicates on \(\{-1,1\}^n\) as products of cubic polynomials over prime fields, with a self-contained proof over \(\mathbb F_3\).
The determinantal complexity of the 4*4 permanent is 15 Karthik Sheshadri [arXiv:2611.06658]
A single-author note claims that the determinantal complexity of the \(4\times4\) permanent is exactly 15, raising the lower bound from 10 and showing Grenet's \(2^n-1\) construction optimal at \(n=4\).
Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy Mrinalkanti Ghosh [arXiv:2611.08836]
Ghosh proves integrality-gap lower bounds for linear-programming relaxation hierarchies, which are weaker than sum-of-squares, for maximising degree-\(d\) homogeneous polynomials over the unit sphere.
Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz [arXiv:2611.09733]
Chakraborty, Ordyniak and Siebertz show that Metric Dimension is NP-complete on planar graphs of treewidth and bag-connected treewidth three. There is therefore no XP algorithm by bag-connected treewidth unless \(\mathrm P=\mathrm{NP}\), which answers questions of Bonnet and Purohit and of Bousquet, Deschamps and Parreau.
Worst-Case to Average-Case Reductions for Basic Linear Algebra Or Zamir [arXiv:2611.03058]
Zamir carries the Blum–Luby–Rubinfeld style of worst-case to average-case reduction from matrix multiplication to other basic linear algebra over finite fields, giving an unconditional time-preserving reduction for matrix inversion and improved conditional reductions for rank and determinant.
Deterministic factorization of constant depth circuits from whitebox PIT Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan et al. [arXiv:2611.09035]
The arXiv version of the result that deterministic factorisation of constant-depth circuits over the rationals reduces in polynomial time to whitebox PIT, with the same reduction working for formulas and algebraic branching programs.
Quadratic Extractors Gautam Chandrasekaran, Jesse Goodman, David Zuckerman [arXiv:2611.07266]
The arXiv version of the explicit extractor for quadratic sources at min-entropy \(\mathrm{polylog}(n)\), improving the previous requirement of roughly \(n-\sqrt{\log n}\).
Determinant boundaries and gaps in determinantal complexity Karthik Sheshadri [arXiv:2611.03554]
For every \(n\ge 10\), Sheshadri constructs an explicit degree-\(n\) form, concise in \(n^2\) variables, whose orbit closure is a determinant-boundary component, whose border determinantal complexity is \(n\) and whose exact determinantal complexity is at least \(2n-1\), so the gap between the two can grow linearly.
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs Andrew D. Lin [arXiv:2611.05034]
Lin gives a short proof that a properly edge-coloured \(n\)-vertex graph of average degree \(\Omega(\log n\log\log n)\) contains a rainbow cycle, extends it to weighted list-coloured graphs, and uses the extension to improve bounds for binary linear locally correctable codes with an even number of queries.
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete L. Sunil Chandran, Rishikesh Gajjala [arXiv:2611.04444]
Chandran and Gajjala prove that binary prefix coding with unequal letter costs is NP-complete, settling the exact complexity of a problem that has had only exact algorithms for fixed costs and a PTAS since Karp's 1961 integer-programming formulation.
Some algebraic and geometric computations in CH via Chow forms Robert Andrews, Abhibhav Garg, Rafael Oliveira, Éric Schost [arXiv:2611.05289]
For algebraic varieties represented by Chow forms, several problems about equidimensional decomposition move from PSPACE down to the counting hierarchy CH.
Competitive Equilibrium for Linear Chores is CLS-complete Qian Liu, Shinuo Ma, Yixin Tao, Minji Yang et al. [arXiv:2611.06589]
Computing an exact competitive equilibrium in a linear Fisher market with divisible chores is CLS-complete; the problem was known to lie in CLS, but no hardness was known.
Asymptotic advantage of quantum one-way and SMP communication for total functions Dmytro Gavinsky [arXiv:2611.07318]
Gavinsky exhibits a total Boolean function on \(n\) bits with bounded-error quantum simultaneous-message cost \(O(\sqrt n)\) but randomised one-way cost \(\Omega(n)\), which also has a classical simultaneous-message protocol of cost \(O(\sqrt n)\) when the players share \(O(\sqrt n)\) EPR pairs.
On computing the determinant over a ring Gilles Villard [arXiv:2611.07786]
Villard computes the determinant and characteristic polynomial over any commutative ring with \(O(n^\omega)\) ring operations, using no divisions and no zero tests, as a straight-line program for each \(n\).
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between \(\mathsf{StoqMA}\) and \(\mathsf{MA}\) Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara [arXiv:2611.08180]
Relative to a classical oracle, \(\mathsf{MA}\subsetneq\mathsf{StoqMA}\), so verification with sign-free quantum resources already beats every classical verifier, without the coherent computation used in earlier separations along \(\mathsf{MA}\subseteq\mathsf{QCMA}\subseteq\mathsf{QMA}\).
Beyond the \(n/2\) Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu et al. [arXiv:2611.09809]
An explicit family of symmetric Boolean functions needs \(n/2+\Omega(n^{1/3})\) quantum queries at a fixed constant error, and a matching algorithm recovers the exact Hamming weight with \(n/2+O(n^{1/3})\) queries, so a single-output function can require overhead beyond \(n/2\).
Entropy-Weighted Soundness for Multi-Answer Birthday Graphs Alexandru Popa [arXiv:2611.04457]
For bounded-occurrence, constant-gap Boolean ternary CSPs, Popa bounds the maximum induced \(K\)-vertex density of the associated birthday graph even when the selected vertices may repeat or omit views; the result is a soundness bound and is not turned into a new fine-grained lower bound.
Online Algorithms Cannot Find Isolated Perceptron Solutions Shuangping Li, Gabe Schoenbach [arXiv:2611.03397]
Li and Schoenbach [arXiv:2611.03397] prove that online algorithms find an isolated solution of the random binary perceptron, where all but a vanishing fraction of solutions are isolated, only with probability \(o(1)\).
A King for Almost Everyone Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande [arXiv:2611.03838]
Ismaili Alaoui, Lachish and Mande [arXiv:2611.03838] give a deterministic \(O(n^{4/3})\)-query algorithm that finds a \((1-\varepsilon)\)-king in a tournament for every fixed \(\varepsilon\); the \(\Omega(n^{4/3})\) lower bound and \(O(n^{3/2})\) upper bound for exact \(1\)-kings, unimproved for two decades, are untouched.
The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis [arXiv:2611.03945]
Deligkas, Fasoulakis and Ioannidis [arXiv:2611.03945] show that finding a KKT point of a quadratic polynomial over the unit hypercube stays \(\mathrm{CLS}\)-complete when the coefficients are written in unary, the first problem shown \(\mathrm{CLS}\)-hard with unary input.
Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith [arXiv:2611.04680]
Couteau, Melissaris and Sajith [arXiv:2611.04680] use random low-rank updates to turn an algorithm solving an inverse-polynomial fraction of random linear systems into one that succeeds on every right-hand side for almost every matrix, at a runtime cost linear in the inverse success probability, and derive fine-grained one-way functions from it.
Universal Hardness From Masking Channels Parikshit Gopalan, Manoj Prabhakaran, Pranay Tankala [arXiv:2611.05296]
Gopalan, Prabhakaran and Tankala [arXiv:2611.05296] recast Impagliazzo's hardcore measures as input-dependent masking channels on a function's output and use this view to extend the hardcore lemma to a general learning-theoretic framework.
PIT and Reconstruction for Sums of Powers Nimrod Kaplan, Amir Shpilka, Yann Tal [arXiv:2611.07106]
Kaplan, Shpilka and Tal [arXiv:2611.07106] prove lifting theorems showing that, when the outer power \(d\) is large enough, deterministic black-box PIT and reconstruction for an inner polynomial class carry over to sums \(\sum_i \alpha_i f_i^d\).
On derandomizing the line-point low-degree test Prahladh Harsha, Swastik Kopparty, Mrinal Kumar, Ramprasad Saptharishi et al. [arXiv:2611.09183]
Harsha, Kopparty, Kumar, Saptharishi and Sudan [arXiv:2611.09183] find unexpected behaviour in the derandomized bivariate line-point low-degree test at high error: a counterexample with roughly \(q^{3/2}\) lines, and a positive result once \(q \ge k^2/\varepsilon^{O(1)}\).
Efficient Proper Agnostic Learning of Halfspaces Anindya De, Elchanan Mossel, Shivam Nadimpalli, Joe Neeman [arXiv:2611.02344]
De, Mossel, Nadimpalli and Neeman [arXiv:2611.02344] give a proper membership-query algorithm that agnostically learns halfspaces under the uniform distribution on \(\{\pm1\}^n\) to error \(\mathrm{OPT}+\varepsilon\) in time \(\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}\), against the previous \(n^{\mathrm{poly}(1/\varepsilon)}\).
Breaking the quantum barriers for Graph Collision Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall et al. [arXiv:2611.05356]
Cornelissen, Gilani, Kintali, Le Gall, Patro and Zhou [arXiv:2611.05356] refute the conjectured \(\Omega(n^{2/3})\) quantum query lower bound for graph collision with an \(\widetilde O(n^{11/17})\)-query bounded-error algorithm.
Structured Quantum Hardness from Unstructured Assumptions Xiao Liang, Takashi Yamakawa, Chak Fai Yung [arXiv:2611.07413]
Liang, Yamakawa and Yung [arXiv:2611.07413] prove a quantum analogue of the conditional Bennett-Gill result: if \(\mathrm{UP}\not\subseteq\mathrm{BQP}\), then \(\mathrm{NP}^O\cap\mathrm{coNP}^O\not\subseteq\mathrm{BQP}^O\) with probability \(1\) over a random oracle \(O\).
Combinatorial limitations of list-decoding Reed-Solomon codes Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami [arXiv:2611.07607]
The arXiv version [arXiv:2611.07607] of Alrabiah, Goyal and Guruswami's result that Reed-Solomon codes can have super-polynomial lists just beyond the Johnson radius, refuting a constant-list conjecture over prime fields.
A Universal Threshold Theory for Local Properties of Random Linear Codes Vinayak M. Kumar, Ray Li, Jonathan Mosheiff, Gilad Shavit [arXiv:2611.07661]
Kumar, Li, Mosheiff and Shavit [arXiv:2611.07661] show that the threshold dimension of any \(b\)-local monotone property of random linear codes, such as list decoding or list recovery, lies within \(O(b)\) of its expectation threshold.
Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel et al. [arXiv:2611.07829]
The arXiv version [arXiv:2611.07829] of Ball, Chattopadhyay, Gurumukhani, Shaltiel and Zhao's extractors for low-entropy samplable sources under reduced hardness assumptions.
On Positive Computation Eduardo Skapinakis [arXiv:2611.09622]
Skapinakis introduces positive reductions for monotone classes, shows that monotone Circuit Satisfiability and Hamiltonian Cycle are \(\mathrm{mNP}\)-complete under them, and proves that the separation \(\mathrm{posP} \subsetneq \mathrm{mNP}\) does not relativise; if every \(\mathrm{mNP}\)-complete problem were complete in this stronger sense, \(\mathrm{P} \neq \mathrm{NP}\) would follow.
On the optimality of truncation among binary linear sketches Robinson D. H. Cung, Adway Girish, Emre Telatar [arXiv:2611.03979]
Cung, Girish and Telatar prove that, under a monotonicity condition, simply keeping a subset of the input coordinates is optimal among all binary linear sketches of the same size, with applications to distributed correlation testing and to evaluating unate Boolean functions on uniformly random inputs.
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron Jianan Zhang, Shuangping Li [arXiv:2611.04294]
Zhang and Li give a state-evolution and universality analysis of iterated linear programming for the random binary perceptron, extending earlier analyses that covered only a single round of LP.
Improved Approximation and Hardness Bounds for \(β\)-TSP Paul Liu, Jack Spalding-Jamieson, Da Wei Zheng [arXiv:2611.09421]
Liu, Spalding-Jamieson and Zheng improve both the approximation ratios and the hardness bounds for \(\beta\)-TSP, where edge lengths satisfy \(\ell_{uw} \le \beta(\ell_{uv}+\ell_{vw})\) for \(\beta \in [1/2,1]\).
A Tight Hierarchy for Chain of Thought Thanh Le, A. Pavan, N. V. Vinodchandran [arXiv:2611.09759]
Le, Pavan and Vinodchandran prove the first hierarchy theorem for chain-of-thought transformers: \(\mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon})\) for every reasonable resource bound \(r(n) \ge n\) and every \(\varepsilon > 0\).
On the Role of Geometry in Solving Variational Inequalities Ioannis Anagnostides, Ioannis Panageas, Jingming Yan [arXiv:2611.04151]
Anagnostides, Panageas and Yan classify variational inequalities over \(\ell_p\) balls, a family that contains symmetric bimatrix games (\(p=1\)) and polymatrix games (\(p=\infty\)): the problem is PPAD-complete for affine operators when \(p \neq 2\), polynomial-time for affine operators when \(p=2\), and PPAD-complete for quadratic operators.
Quantum Advantage has Few Complexity Implications Eli Goldin, Alex Lombardi, Tomoyuki Morimae [arXiv:2611.05303]
Goldin, Lombardi and Morimae give a classical oracle relative to which \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{BQP}=\mathrm{PSPACE}\) while proofs of quantumness still exist, which is evidence that such proofs, and oblivious state preparation when \(\mathrm{BQP}=\mathrm{QCMA}\), carry few complexity-theoretic consequences.
Quantum Interactive Proofs of Proximity Kenan Wood [arXiv:2611.08858]
Wood initiates the study of quantum interactive proofs of proximity and shows that every logspace-uniform \(\mathrm{NC}\) property has one with query, communication and time complexity \(\widetilde{O}(n^{2/5})\), below the best known classical \(\widetilde{O}(\sqrt{n})\).
State Synthesis with an NP oracle Aniruddha Sen [arXiv:2611.02370]
Sen gives a polynomial-time quantum algorithm that, with an \(\mathrm{NP}\) oracle and query access to the state vector's entries, prepares any state to inverse-exponential precision, improving the previous \(\mathrm{PP}\) oracle bound; with a \(\mathrm{P}\) or even \(\mathrm{P/poly}\) oracle, exponentially many queries are needed.
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang [arXiv:2611.04365]
Chao, Cen, Ma and Wang determine the optimal space for one-pass spanning-forest computation in dynamic graph streams at every failure probability \(\delta \le 1/4\), giving matching upper and lower bounds of \(\Theta(\min\{v^2, v\log(v/\delta)\log^2(2+v/\log(v/\delta))\})\) bits, and also treat streams with bounded deletions.
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds Zixuan Huang, Guozhang Chen [arXiv:2611.06055]
Huang and Chen approximate softmax attention at any temperature in fixed dimension \(d\), to additive error \(\varepsilon\), in expected time \(\widetilde{O}((mn)^{k/(k+1)}+m+n)\) with \(k=\lfloor d/2\rfloor\), matching the best known bounds for batch maximum inner product.
Improved Exact and Approximate Quantum Fourier Transforms from Multiplication Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh [arXiv:2611.06341]
Kayal, Mittal, Paraashar and Saurabh sharpen the reduction from the quantum Fourier transform to integer multiplication, obtaining exact QFT circuits over \(\mathbb{F}_{2^q}\) with \(O(q\log q)\) gates instead of \(O(q^2)\), together with improved approximate versions.
Reconfiguration of Time-Bounded Descriptions Dimitrios Myrisiotis [arXiv:2611.09020]
Myrisiotis studies the graph of all time-bounded programs that print a given string under an adjunction-universal machine, and proves results on its connectivity, including that deciding whether two programs are connected is PSPACE-complete.
Path Isolation and Reachability in Surface-Embedded Graphs with Restricted Cycle and Cut Structure Neelabjo Shubhashis Choudhury, Chetan Gupta, Raghunath Tewari [arXiv:2611.09262]
Choudhury, Gupta and Tewari construct logspace-computable isolating weight assignments for directed surface-embedded graphs with polynomially many simple non-separating cycles, which places reachability in these graphs in \(\mathrm{UL}\) and bipartite perfect matching on the corresponding graphs in \(\mathrm{SPL}\).
Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs Yali Aharon-Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma [arXiv:2611.02963]
Aharon-Holzman, Ilan, Reiner and Ta-Shma construct explicit two-sided lossless expanders whose adjacency matrices have full rank, and use them to build explicit asymptotically good quantum LDPC codes with full-row-rank check matrices and small-set soundness on a linear range.
Polynomial-time classical simulation of boson and fermion sampling under thermal loss Armando Angrisani, Hela Mhiri [arXiv:2611.08444]
Angrisani and Mhiri give polynomial-time classical simulation, at inverse-polynomial total variation error, of Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing and fermion sampling with magic inputs, under any fixed nonzero thermal or pure loss rate and with high probability over Haar-random interferometers.
Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification Olivier Bournez, Johanne Cohen, Adrian Wurm [arXiv:2611.02840]
Bournez, Cohen and Wurm [arXiv:2611.02840] show that every deterministic Turing machine is simulated exactly by the iterates of a fixed width-4 ReLU network on \([0,1]^4\), built in polynomial time and with iteration count proportional to the machine's running time, and they draw consequences for the complexity of verifying such networks.
Tilted Convexity and an Exact Offline-Online Separation Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal [arXiv:2611.03472]
Pedramfar, Khanna, Quinn and Aggarwal [arXiv:2611.03472] introduce \(\gamma\)-tilted convexity, a one-parameter weakening of convexity giving distinct nested classes in which local minimisers are still global, and prove an exact separation between offline and online optimisation over these classes.
Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead Qin Xin [arXiv:2611.08705]
Xin [arXiv:2611.08705] turns ordinary universal exploration sequences of length \(O(n^c)\) into a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2 n)\), with sharper refinements, which speeds up delayed-activation treasure hunt in anonymous port-labelled graphs.
On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle Alexander Hoover, Giuseppe Persiano, Kevin Yeo [arXiv:2611.04052]
Hoover, Persiano and Yeo [arXiv:2611.04052] study how much communication secure multiparty computation needs when only a random oracle is available, proving lower bounds for both classical and quantum communication against the information-theoretic bounds known to be tight for inner products.
On the Hardness of Approximate Quantum Circuit Membership and Optimization Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis [arXiv:2611.04381]
Kjelstrøm, van de Pol and Pavlogiannis [arXiv:2611.04381] prove that deciding, without a promise, whether a quantum circuit is close to a unitary in a fixed target set is \(\mathrm{PP}\)-hard under several metrics, and the same holds for the corresponding circuit optimisation problems.
Agnostic Learning by Imitating Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold et al. [arXiv:2611.05346]
Casacuberta, Gopalan, Kanade, Reingold, Stavropoulos and Tankala [arXiv:2611.05346] prove that agnostically learning a class and training a generative model that no member of the class can distinguish from the data are equivalent in complexity; only one direction was known before.
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities Huanjian Zhou, Taiji Suzuki [arXiv:2611.05813]
Zhou and Suzuki [arXiv:2611.05813] prove that any randomised first-order sampler for \(d\)-dimensional strongly log-concave targets with condition number 2 needs \(\exp(\Omega(\log^{1/3} d))\) queries, even from a constant warm start, and that targets satisfying a log-Sobolev inequality need \(\Omega(\kappa)\) queries once \(d\gtrsim\log^2\kappa\).
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures Yinzhen Lv [arXiv:2611.02346]
Lv [arXiv:2611.02346] constructs a succinctly specified, uniformly strongly log-concave Gaussian mixture with rational means whose score at a fixed point encodes whether a Boolean formula is satisfiable, so smoothness and log-concavity do not make score evaluation easier than SAT.
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity Wei Guo, Bo Yuan, Ye He, Jiaming Liang et al. [arXiv:2611.03442]
Guo, Yuan, He, Liang, Tao and Chen [arXiv:2611.03442] run the proximal sampler with a high-order noisy conditional sampler from a 2026 OpenAI work to sample from non-convex potentials with Lipschitz gradient, obtaining subpolynomial gradient-query dimension dependence under a log-Sobolev inequality.
On the Complexity of Exact Autobidding Equilibria Yiyang Huang, Zhengyang Liu, Yonglei Yan [arXiv:2611.04475]
Huang, Liu and Yan [arXiv:2611.04475] prove that computing exact autobidding equilibria is \(\mathrm{FIXP}\)-complete for second-price ROI pacing, for budget- or ROI-constrained generalised second-price sponsored shopping and for second-price throttling, and that approximating the equilibrium in distance is \(\mathrm{FIXP}_a\)-complete in some of these settings.
Differentially Oblivious Priority Queues with Sublogarithmic Cost Zimai Guo, Cheng Hong, Zhechen Li [arXiv:2611.04776]
Guo, Hong and Li [arXiv:2611.04776] build a differentially oblivious integer priority queue with \(\mathrm{polylog}(T)\) private memory and \(O(\log T/\log\log T)\) expected amortised work per operation for constant \(\varepsilon\) and \(\delta=\exp(-\Theta(\log^2 T))\), below the \(\Omega(\log T)\) barrier for fully oblivious queues.
Randomized Parallel Complexity of Weakly Convex Optimization Kang Liu [arXiv:2611.07675]
Liu [arXiv:2611.07675] shows that, in high dimension, the standard subgradient rate is optimal in round complexity for finding approximate stationary points of nonsmooth weakly convex functions, even for randomised algorithms making polynomially many parallel queries per round, while on the real line a deterministic algorithm using only function values needs only logarithmically many rounds.
Monodromy Computation Model Xiaoyang Liu [arXiv:2611.04377]
Liu [arXiv:2611.04377] defines a model of computation in which retained logarithmic branches of analytic continuation serve as memory, and shows that three branch coordinates suffice to simulate every finite-alphabet, finite-control Post–Turing machine.
Community Search under Member-Specific Tolerances Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng [arXiv:2611.05951]
Liu, Guo, Zhang and Cheng [arXiv:2611.05951] define latitude-consistent communities: connected subgraphs containing the query vertex, with minimum degree at least \(k\) and diameter bounded by the smallest member tolerance; they motivate the model by social judgement theory and study its complexity and practical algorithms.
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine Sergey Salishev [arXiv:2611.06303]
Salishev [arXiv:2611.06303] defines an exact finite-budget version of the bounded halting problem in which the checker and the simulated program run on the same unit-cost timescale, and uses a diagonal argument with explicit additive overhead to show that no fixed deterministic checker decides every instance within the stated budget.
Dissecting Geometric Constraints in Grokking: Interaction-Dependent Acceleration in Modular Arithmetic Zachary A. Hampton, Wasiq Khan, Bilal Khan [arXiv:2611.03156]
A factorial study of 960 modular-arithmetic training runs finds that residual projection accounts for much of the faster grokking in the Sphere+Fourier transformer configuration, but is not sufficient on its own; this is empirical machine learning, not complexity theory.

ECCC 21 papers

The Electronic Colloquium on Computational Complexity, the field's own report series. Screened for scope, not refereed.

New Gate, Weight and Wire Complexity Bounds for Sigmoid Neural Networks Jiatu Li, Daniel Reichman, Ryan Williams, Tony Wu [ECCC:TR26-311]
Li, Reichman, Williams and Wu prove new upper and lower bounds on the gate, weight and wire complexity of sigmoid neural networks computing Boolean functions, including nearly tight bounds on the wire complexity of computing PARITY.
Tight Depth Lower Bounds for Stretch Amplification Oliver Korten [ECCC:TR26-302]
Korten shows that any black-box construction of a PRG \(H:\{0,1\}^m\to\{0,1\}^M\) that makes \(\mathrm{poly}(n)\) queries to a PRG \(G:\{0,1\}^n\to\{0,1\}^N\) in \(d\) adaptive phases must satisfy \(M\le(m+O(\log n))(N/(n-O(\log n)))^d\), so the standard amplification by repeated composition is essentially optimal.
Exponential Separation of Sign-Rank and Margin Complexity Gabriel Hart, Kaave Hosseini [ECCC:TR26-306]
Hart and Hosseini construct an explicit family of total sign matrices whose sign-rank is exponentially larger than their margin complexity, the first superpolynomial separation for total matrices, which answers quantitatively a question of Linial, Mendelson, Schechtman and Shraibman.
An Exponential Top Fan-In Hierarchy for Border Depth-4 Circuits Anakin Dey, Pranjal Dutta, Zeyu Guo [ECCC:TR26-297]
Dey, Dutta and Guo prove an exponential top fan-in hierarchy for border depth-4 circuits \(\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}\) over fields of characteristic 0, with a sum of \(k+1\) degree-\(n\) monomials on disjoint variable sets as the hard polynomial, even though a depth-3 circuit of top fan-in \(k+1\) and size \(O(kn)\) computes it.
Factor Closure in Noncommutative Algebraic Complexity Vikraman Arvind, Pushkar Joglekar [ECCC:TR26-300]
Arvind and Joglekar prove that \(\mathrm{VP}_{nc}\) is closed under factors over every field: left and right factors of a size-\(s\), degree-\(D\) noncommutative circuit have circuits of size \(O(sD^3)\), and central factors of size \(O(sD^6)\), by a weighted-automaton construction.
Semidirect sums of tensors and the matrix multiplication exponent Baitian Li [ECCC:TR26-298]
Li's exposition of the OpenAI preprints claiming \(\omega\le 9/4\) isolates their new ingredient as an 'untwisting lemma' for semidirect sums of tensors, and discusses its further uses and its relation to earlier work.
Asymptotic non-negative rank can be exponentially smaller than non-negative rank Pavel Hrubes [ECCC:TR26-301]
Hrubeš constructs a matrix \(M\) with \(\mathrm{rk}_+(M\times M)\le O(\mathrm{rk}_+(M)\log\mathrm{rk}_+(M))\) and shows that asymptotic non-negative rank under Kronecker powers can be exponentially smaller than non-negative rank.
Reed–Muller Codes are Optimal Binary Linear 3-Query LCCs Oliver Janzer, Peter Manohar [ECCC:TR26-291]
Janzer and Manohar prove that every binary linear 3-query locally correctable code with constant correction radius has length \(2^{\Omega(\sqrt k)}\), so Reed–Muller codes are optimal up to the constant in the exponent.
The Space Complexity of Property Testing Clement Canonne, Xi Chen, William Pires, Toniann Pitassi et al. [ECCC:TR26-312]
Canonne, Chen, Pires, Pitassi and Servedio begin the study of space-bounded property testing. For monotonicity, symmetry, linearity, juntas and linear threshold functions they give testers using far less space than the query-optimal ones, together with space lower bounds.
The determinantal complexity of the 4*4 permanent is 15: A short proof Karthik Sheshadri [ECCC:TR26-309]
This is the ECCC version of Sheshadri's claim that the \(4\times4\) permanent has determinantal complexity exactly 15.
Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla [ECCC:TR26-299]
Agarwal, Hari, Pandey and Shukla place approximate polynomial satisfiability, previously known only to be NP-hard and in PSPACE, together with integral closure membership, in the counting hierarchy, following the recent CH bound for Hilbert's Nullstellensatz.
Deterministic factorization of constant depth circuits from whitebox PIT Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan et al. [ECCC:TR26-310]
Over the rationals, constant-depth algebraic circuits can be factored deterministically in time polynomial in their size and degree, given a whitebox or blackbox PIT algorithm for the class; the same simple reduction applies to formulas and algebraic branching programs.
Testing Implies Distance Estimation with Polynomial Loss Gaia Carenini, Cameron Seth [ECCC:TR26-292]
In the dense graph model, where Fischer and Newman showed that every testable property is also estimable, Carenini and Seth show that the step from testing to distance estimation costs only a polynomial loss in query complexity.
Quadratic Extractors Gautam Chandrasekaran, Jesse Goodman, David Zuckerman [ECCC:TR26-303]
Chandrasekaran, Goodman and Zuckerman construct explicit extractors for quadratic sources over \(\mathbb{F}_2^n\) at min-entropy \(\mathrm{polylog}(n)\), down from roughly \(n-\sqrt{\log n}\), and so go below \(\sqrt{n}\) even for 2-local sources, which provably cannot be handled by black-box reduction to sumset extraction.
Fast Algorithms for Low Rank Tensor Decomposition Shubhangi Saraf, Devansh Shringi [ECCC:TR26-295]
Over \(\mathbb{R}\) and \(\mathbb{C}\), Saraf and Shringi find a minimal decomposition of an order-\(d\), width-\(n\), rank-\(k\) tensor deterministically in time \(k^{O(k^2)}\cdot\mathrm{poly}(n,d)\) from measurement access, improving the previous \(k^{O(k^{16})}\) and giving tensor rank computation in similar time.
Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz-Thompson Estimator Guy Goldberg, Tom Gur, Sidhant Saraogi [ECCC:TR26-293]
Any \(q\)-query relaxed locally decodable code \(\{0,1\}^k\to\{0,1\}^n\), including nonlinear codes and adaptive decoders with two-sided error, must have \(n=k^{1+\Omega(1/q)}\), nearly matching the \(k^{1+O(1/q)}\) construction of Ben-Sasson et al.; the proof uses a capped Horvitz–Thompson estimator.
Some algebraic and geometric computations in CH via Chow forms Robert Andrews, Abhibhav Garg, Rafael Mendes de Oliveira, Éric Schost [ECCC:TR26-294]
Andrews, Garg, Oliveira and Schost [ECCC:TR26-294] move several problems on the equidimensional decomposition of algebraic varieties, represented by Chow forms, from \(\mathrm{PSPACE}\) down to the counting hierarchy \(\mathrm{CH}\).
Exponential Quantum Advantage in Testing Fourier Dimensionality Kenny Chen [ECCC:TR26-296]
Chen [ECCC:TR26-296] gives an almost optimal \(O(k/\sqrt{\epsilon})\)-query quantum tester for whether a Boolean function has Fourier dimension at most \(k\), an exponential advantage over the known \(\Omega(2^{k/2})\) classical lower bound.
Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel et al. [ECCC:TR26-308]
Ball, Chattopadhyay, Gurumukhani, Shaltiel and Zhao [ECCC:TR26-308] construct explicit extractors for sources samplable by polynomial-size circuits, including a one-bit extractor at min-entropy \(O(\log n)\), under hardness assumptions much weaker than the \(\Sigma_6^{\mathrm{P}}\)-oracle assumption of Trevisan and Vadhan.
Combinatorial limitations of list-decoding Reed-Solomon codes Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami [ECCC:TR26-304]
Alrabiah, Goyal and Guruswami [ECCC:TR26-304] show that full-length Reed-Solomon codes over low-characteristic fields can have super-polynomially many codewords just beyond the Johnson radius, and over prime fields polynomially many strictly below \(1-R\), refuting a conjecture of constant list size below capacity.
The Information Bottleneck and the Privacy Funnel are NP-hard Roberto Bruno, Ugo Vaccaro [ECCC:TR26-307]
Bruno and Vaccaro [ECCC:TR26-307] prove that computing the optimal value of the information bottleneck problem, of its Lagrangian relaxation, and of the privacy funnel is \(\mathrm{NP}\)-hard.
From the AI-assisted repositoriesunrefereed; read with care

Hexagon 17 papers

An AI-assisted repository: AI-written and AI-co-written work with mandatory provenance labels. Nothing here is refereed. Read with care.

17
preprints this week
Anthropic Claude Opus
most credited system (8 of 17)
eth
most common topic (5 papers)

Seventeen AI-assisted submissions came in, none refereed. The claimed ETH refutations, already treated in this issue's feature, sit under much of the batch. Several papers derive conditional corollaries from the unverified #SAT engines [hexagon:2611.00088v1] [hexagon:2611.00090v1] [hexagon:2611.00133v1], and one asks what those engines cannot do [hexagon:2611.00149v1]. For this reader the paper to check is [hexagon:2611.00004v1]. It claims a Lean-formalised binary CSP algorithm whose exponent is sublinear in treewidth on a class of bounded-degree graphs, which would contradict the literal form of a conjecture of Marx. [hexagon:2611.00178v1] reports a Subset Sum exponent of 0.48758, resting on others' proofs. Two heuristic papers offer only conjectured ratios. A corollary is no stronger than the claim beneath it.

Themes corollaries of the claimed ETH refutations · Lean-checked lemmas · exact exponential algorithms

Claim of the week The paper claims that binary CSP can be decided deterministically in time \(f(G)\cdot\|I\|^{c\cdot\mathrm{tw}(G)/\sqrt{\log \mathrm{tw}(G)}}\) on a class of bounded-degree graphs of unbounded treewidth, which would contradict the literal form of Conjecture 1.4 of Marx (2010). [hexagon:2611.00004v1]

A Sublinear Treewidth Exponent for Binary Constraint Satisfaction Troy Tri Nguyen [hexagon:2611.00004v1]
An AI-assisted and unverified submission claims a deterministic algorithm for binary CSP that runs in time \(f(G)\cdot\|I\|^{c\cdot \mathrm{tw}(G)/\sqrt{\log \mathrm{tw}(G)}}\) on a class of bounded-degree graphs of unbounded treewidth; this would contradict the literal form of Conjecture 1.4 of Marx (2010), and the authors state the result is formalised in Lean 4.
What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas Vaibhav Tulsyan · with Anthropic Claude Fable, Lean Lean [hexagon:2611.00149v1]
An AI-assisted, unrefereed paper poses the 'engine barrier problem', bounding from below the shared bits of the sum-of-products networks behind the claimed deterministic subexponential \(k\)-CNF counting algorithms, with some lemmas checked in Lean.
A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis Jennifer Voitle [hexagon:2611.00178v1]
An AI-assisted, unrefereed paper reports a certified exponent of \(0.48758\) for worst-case Subset Sum, extending a run of recent preprints below the meet-in-the-middle bound of \(1/2\) on whose proofs it depends, and examines the limits of the alias–checksum analysis.
Fast Attention after SETH: The Exact Exponent and the Hypotheses Behind It Xiaoyu Li · with Anthropic Claude Opus, OpenAI ChatGPT, Python Python 3 (checks in anc/) [hexagon:2611.00132v1]
An AI-assisted and unverified paper, which takes the claimed refutation of ETH and SETH as given, rests the quadratic lower bound for attention on Orthogonal Vectors in dimension \(c\log n\), and claims an exact time exponent of \(1+\min\{W/\ln n,1\}\) in terms of the largest logit gap \(W\).
An Improved Subexponential Bound for Deterministic Integer Factorization Joseph Shunia · with OpenAI ChatGPT [hexagon:2610.00711v1]
An AI-assisted and unverified paper claims deterministic prime factorisation of \(n\)-bit integers in time \(2^{O(n/\sqrt{\log n})}\) and polynomial space, by combining a claimed OpenAI tensor-contraction theorem with a linear-size multiplication encoding to count divisors with given binary prefixes.
Counting Eulerian circuits in subexponential time, assuming the new #SAT algorithms Vaibhav Tulsyan · with Anthropic Claude Fable, Anthropic Claude Opus, Lean Lean [hexagon:2611.00088v1]
An AI-assisted, unverified note by Tulsyan [hexagon:2611.00088v1] derives a \(2^{o(m)}\) algorithm for counting Eulerian circuits in bounded-degree undirected graphs via Kotzig's correspondence with Hamiltonian cycles, conditional on Anthropic's claimed, unverified #SAT algorithm.
Universal-Clique Amplification and Hardness of Assignment-Optimal Edge Clique Covers Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář et al. · with Bolzano team Bolzano [hexagon:2611.00053v1]
An AI-assisted, unverified paper by Kripner, Rozhoň, Šámal, Šindelář and Zámečník [hexagon:2611.00053v1] claims that, unless \(\mathrm{P}=\mathrm{NP}\), the assignment cost of edge clique covers has no polynomial-time \(O(N^{1/2-\eta})\)-approximation even on connected graphs, using a universal-clique join that transfers colouring hardness.
Ulam Metric \(k\)-Center in Parameterized Linear Time Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář et al. · with Bolzano team Bolzano [hexagon:2611.00055v1]
An AI-assisted, unverified paper by Kripner, Rozhoň, Šámal, Šindelář and Zámečník [hexagon:2611.00055v1] claims a deterministic \(2^{O(kd\log(k+d+2))}mn\) algorithm for continuous Ulam-metric \(k\)-Center, answering a question of Bai, Fomin, Golovach, More and Wietheger for one centre, with a matching \(2^{o(d\log d)}\) exclusion.
The parity of the prime-counting function in time \(x^{o(1)}\) Vaibhav Tulsyan · with Anthropic Claude Opus, Lean Lean [hexagon:2611.00116v1]
An AI-assisted, unverified preprint claims deterministic algorithms that output the parity of the prime-counting function \(\pi(x)\) in time \(x^{o(1)}\); exact computation of \(\pi(x)\) itself takes \(x^{1/2+o(1)}\) steps by the Lagarias–Odlyzko method.
Exact amplitudes of sparse quantum circuits in subexponential time, assuming the new #SAT algorithms Vaibhav Tulsyan · with Anthropic Claude Fable, Anthropic Claude Opus, Lean Lean [hexagon:2611.00090v1]
An AI-assisted preprint records that, if three internal results of Anthropic's unverified subexponential #\(k\)-SAT manuscript hold, exact amplitudes of Clifford+T circuits with \(G\) two-qubit gates can be computed deterministically in subexponential time, about \(2^{O(G/\sqrt{\log G})}\).
The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář et al. · with Bolzano team Bolzano [hexagon:2611.00054v1]
An AI-assisted preprint claims a \(1/2\)-approximation for bottleneck multiple subset sum with arbitrary capacities using \(O(n\log(n+1)+m\log(m+1))\) operations, and claims that no fixed ratio above \(1/2\) is achievable unless \(\mathrm{P}=\mathrm{NP}\); this would give a negative answer to Chen et al.'s question about whether \(2/3\) is achievable.
The Price of Bayes-Optimal In-Context Learning Xiaoyu Li · with Anthropic Claude Opus, Python Python 3 with NumPy and SciPy (checks in anc/) [hexagon:2611.00133v1]
An AI-assisted, unverified preprint treats Bayes-optimal in-context learning for \(\kappa\)-local task families as a counting problem, and compares its cost with that of plain learning using the claimed ETH refutations by OpenAI and Anthropic.
Class Numbers of Imaginary Quadratic Orders in the Polynomial Hierarchy Frank Vega · with Anthropic Claude Opus [hexagon:2611.00086v1]
An AI-assisted, unverified manuscript [hexagon:2611.00086v1] claims that the class number \(h(-d)\) of imaginary quadratic orders can be computed in deterministic polynomial time with a \(\Sigma_2^{\mathrm{P}}\) oracle, without assuming the generalised Riemann hypothesis and without randomness.
Undecidability of Quiver Mutation Equivalence Qiyue Tang [hexagon:2611.00158v1]
An AI-assisted, unverified note [hexagon:2611.00158v1] claims that quiver mutation equivalence up to relabelling is undecidable even for one fixed source quiver, and strongly \(\mathrm{NP}\)-hard; the abstract gives no further detail.
Complexity of Mutation-Acyclicity and Matrix Mutation Equivalence Qiyue Tang [hexagon:2611.00180v1]
An AI-assisted, unverified note [hexagon:2611.00180v1] claims that mutation-acyclicity of integral skew-symmetrisable matrices is in \(\mathrm{NP}\), that mutation equivalence is in promise-\(\mathrm{NP}\) when one input is mutation-acyclic, and that for pairs of mutation-cyclic matrices it is RE-complete and strongly \(\mathrm{NP}\)-hard.
The Esperanza Algorithm for Maximum Independent Set Frank Vega · with Anthropic Claude Opus [hexagon:2610.00703v1]
An AI-assisted manuscript [hexagon:2610.00703v1] describes version 0.1.6 of Esperanza, a heuristic for maximum independent set whose approximation ratios are conjectured rather than proved and are supported only by experiments.
The Siriaisa Algorithm for Minimum Independent Dominating Set Frank Vega · with Anthropic Claude Opus [hexagon:2611.00043v1]
An AI-assisted submission presents Siriaisa, an ensemble of eighteen heuristic strategies for Minimum Independent Dominating Set, proves that its output is always an independent dominating set computed in near-linear time, and offers no proven approximation ratio; since the problem cannot be approximated within \(n^{1-\varepsilon}\) unless \(\mathrm{P}=\mathrm{NP}\), any strong ratio claimed for it should be treated with caution.

Diderot 1 paper

An AI-assisted preprint server on which AI systems may be listed as co-authors. Nothing here is refereed. Read with care.

1
preprint this week

One paper came in from Diderot this week, and it is number theory, not complexity. [diderot:adc1b4a4e5fe], with three AI systems listed as authors, studies the set of distinct coefficient values of products \(\prod_{j=2}^{m+1}(1+x^{P_j}+x^{2P_j})\) over the Pell numbers. It claims an exact description of these values by blocks taken from levels of the Calkin–Wilf tree, and a growth bound that it says implies density zero. Nothing in it touches constraint satisfaction, satisfiability, circuits or proofs, so the reader can pass over it. The mathematics may be sound, but it is unrefereed and outside the paper's remit.

Sparse Coefficient Spectra of Pell Representation Polynomials: Growth, Block Structure, and Failure of Halving Laws with openai/gpt-6-astra, anthropic/claude-opus-5.5, openai/gpt-6.1-sol [diderot:adc1b4a4e5fe]
An AI-assisted number-theory paper studies the distinct coefficient values of products \(\prod_{j=2}^{m+1}(1+x^{P_j}+x^{2P_j})\) over the Pell numbers, represents them by blocks from the Calkin–Wilf tree, and bounds their number by \(1+A(5/3)^k\), which gives density zero.
Odds and endsComplexity Chronicles
Numbers of the week
\(10^{-40}\)
the \(\varepsilon\) in the new \(O^*((2-\varepsilon)^n)\) permanent algorithm
5,799
\(2\times 2\) integer matrices in the undecidable mortality instance
\(9/4\)
bound on \(\omega\) over every field, as set out in two expositions
15
claimed exact determinantal complexity of the \(4\times 4\) permanent
94
polynomial degree of the three-machine precedence scheduling algorithm
\(0.4875755\)
certified worst-case Subset Sum exponent (AI-assisted)
☁ Complexity forecast

Fine-grained, all areas: conjectures falling, hyperclique and \(k\)-Clique gone, Max-\(k\)SAT below \(2^n\). Satisfiability Hypothesis: holding, visibility moderate. Promise CSP: three colours hard, four colours easy, steady. Matrix multiplication: \(9/4\), expositions continuing, becoming more readable later.

Classifieds

★ FOR SALE: Exponential Time Hypothesis, one owner since 1999. Sold as seen. Buyer may prefer the Satisfiability Hypothesis, which is equivalent to Weak ETH.

★ LOST: \(k\)-Clique conjecture, last seen depending on \(\omega\). It no longer does, even at \(\omega=2\). No reward offered.

★ FOR SALE: Ryser's formula, \(2^n\) operations, one careful owner. Offers above \((2-10^{-40})^n\) considered.

★ WANTED: polynomial-time 3-colouring for detrivialised mod-\(p\) equations, \(p>3\). Owner already has four colours and understands it is NP-hard.

★ FOR SALE: 5,799 integer matrices, \(2\times 2\). No buyer can be told in general whether they multiply to zero.

★ SITUATION WANTED: arithmetic circuit for the hyperclique tensor, size \(O(n^{k-\varepsilon_k})\). Uniform construction, references available.

★ NO LONGER WANTED: depth-three circuit for 2-OV in logarithmic dimension with \(o(n^2)\) wires. Shown not to exist.

★ EXCHANGE: one Resolution lower bound, proved in Extended Frege, for the same bound proved in quasipolynomial-size \(\mathbf{AC}^0\)-Frege.