CS Paper Radar

Limits and Constants of OpenAI's Claimed ETH Refutation

Fabio Dias, Yvens Lima

cs.CC cs.DSmath.CO ·submitted 2026-10-31 01:12 UTC · v1
theory

Abstract

A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a $k$-CNF formula in time $2^{O_k(n\log\log n/\sqrt{\log n})}$, and $2^{O(n/\sqrt{\log n})}$ at bounded clause density, which would refute the Exponential Time Hypothesis. The headline bound is proved by tensor contraction; the body develops an interpolation algorithm with the weaker exponent $n(\log\log n)^2/\sqrt{\log n}$. This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large $n$ must be for the bounds to bite. The preprint states no constants, so we treat the hidden constant $C$ as a parameter: the general bound beats the $2^n$ of brute force only beyond $n\approx 10^{32}$ for $C=2$, $10^{126}$ for $C=3$ and $10^{3517}$ for $C=10$. We then extract the constants from the tensor-contraction proof: for every input with $m$ clauses at bounded density, the running time it certifies stays above $2^n$ unless $\log_2(n+m)>10^9$, and on random 3-CNF at the satisfiability threshold unless $\log_2 n>5\times10^{11}$. So the bounds are subexponential as $n\to\infty$, but the proof certifies no speed-up over brute force for any input of bounded density that could ever be written down. Third, for the clause-product form of the interpolation algorithm we prove limits in a cost model matching the preprint's evaluation. By a short algebraic lemma, polynomial cost needs components of $O(\log^3 n)$ variables with per-point evaluation, or primal treewidth $O(\log^2 n)$ with dynamic programming over the groups. So the scheme costs $2^{Ω(\sqrt{\mathrm{tw}})}$ at treewidth $\mathrm{tw}$, $2^{Ω(\sqrt n)}$ with high probability on random 3-CNF above clause density 3, and $2^{Ω(n^{1/3})}$ even on trivially countable path formulas. We explain why the preprint's sharper routes escape these limits. Fourth, we report experiments.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set

cs.DS cs.CC ·2026-10-26 ·Zhao Song
similarity 0.60
Abstract

We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an $N$-vertex graph contains an independent set of size $2^{-t}N$, where $t$ is an integer with $1\le t\le\sqrt{\log N}/12$, then our algorithm finds an independent set of size $2^t$ in time $N^{O(t)}$. This gives an approximation ratio of $N/2^{Ω(\sqrt{\log N})}$ in time $N^{O(\sqrt{\log N})}$, improving on the approximation ratio $N/2^{Ω((\log N)^{1/3})}$ obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form $\operatorname{Las}_{R(t)}(G)\ge2^{-t}N\Longrightarrowα(G)\ge2^t$, at $2^{o(\sqrt{\log N\log\log N})}$ levels, cannot hold over a range extending beyond $t=O(\sqrt{\log N\log\log N})$. Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of $\sqrt{\log\log N}$.

0.23

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

cs.LG cs.DS ·2026-09-14 ·Weiming Feng, Yixiao Yu, Yiyao Zhang
theory similarity 0.59
Abstract

We revisit Valiant's algorithm (Commun. ACM'84) for learning $n$-variable CNF formulas with clause size $k$ and variable degree $d$ from i.i.d. uniform random solutions in the local lemma regime. For fixed $t\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieves total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)$ sample complexity. For $t>1$, we prove a matching lower bound for Valiant's algorithm. At $t=1$ (covering $0<t<1$), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound $\widetildeΩ(n/\varepsilon)$.

0.34

Improved Bounds for Directed SSSP in Sparse and Intermediate-Density Graphs

cs.DS ·2026-11-19 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.59
Abstract · 69 pages

We give a deterministic algorithm for exact single-source shortest paths (SSSP) in directed graphs with $n$ vertices, $m$ edges and nonnegative real edge weights. In the comparison-addition model, with unit-cost elementary operations on $O(\log(n+m+2))$-bit integer words, its running time for $m=O(n)$ is $O(n\sqrt{\log n}(\log\log n)^{1/4})$. For $m=Θ(n)$, this reduces the exponent of $\log\log n$ in the bound of Duan, Mao, Shu and Yin from $1/2$ to $1/4$ and removes the factor $(\log\log\log n)^{1/4}$ from the sparse bound stated in a public draft. The same algorithm improves on the bound of Duan et al. over a range of intermediate densities. At $m=Θ(n\sqrt{\log\log n})$, the running time is $O(n\sqrt{\log n}(\log\log n)^{5/8})$, reducing their exponent from $3/4$ to $5/8$. This is a consequence of a uniform bound for intermediate densities up to any fixed multiple of $n\log\log n$ edges; its validity range is larger than the range of strict improvement.

0.14

Running-Time Lower Bounds under FPT $\neq$ W[1]

cs.DS cs.CC ·2026-11-19 ·Hendrik Molter
similarity 0.58
Abstract

We revisit running-time lower bounds historically based on the Exponential Time Hypothesis. Our case study asks how much of their quantitative content can be recovered under the assumption FPT $\neq$ W[1]. The reductions encode the choice of a clique in few bits and control the target parameter in terms of that encoding. This makes a sufficiently fast algorithm for the target problem yield a fixed-parameter algorithm for deciding whether a graph has a clique of the requested size. We obtain twelve lower bounds for deterministic algorithms across graph, string, and integer feasibility problems, including bounds that hold under structural restrictions. In several cases the same function of the parameter appears in the exponent as in the historical bound, with the additional requirement that the cutoff for any prescribed saving in the exponent be computable.

0.14

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.58
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Tarski Fixed Points in Quasi-FPT Queries

cs.CC cs.DS ·2026-10-05 ·Xi Chen, Ruiquan Gao, Yuhao Li, Aviad Rubinstein, Mihalis Yannakakis
publishedtheoryhighly cited similarity 0.57
Abstract

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{Ω(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$, \[ Ω\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le \operatorname{Tarski}(n,k)\le O\left(5^k(\log n)^{\lceil \log k\rceil}\right). \] Succinctly, up to the fixed-parameter factor of $5^k$, the complexity is settled at $(\log n)^{Θ(\log k )}$. In particular, we obtain the first super-polynomial query lower bound for this problem.

0.59

An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting

cs.CR cs.DScs.LG ·2026-09-22 ·Jalaj Upadhyay
theory similarity 0.57
Abstract · This is full proof of GPT generated proof for DP continual counting written in preprint https://arxiv.org/abs/2609.17650v2

The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02) of the proof by Astra on the lower bound for differentially private continual counting. We believe a more natural and easy proof is possible and hope that this note will help in that effort. Prior to the initial preprint by Harrison and Leeman (arXiv:2609.17650v01), Bairaktari and Larsen (arXiv:2607.00876) gave an elegant proof to show a lower bound of $Ω(\log^{3/2}(n))$ for both pure and approximate-DP continual counting, and in personal communication had informed us that they have a proof of optimal $Ω(\log^{2}(n))$ for pure-differential private continual counting as well. They have subsequently published their $Ω(\log^{2}(n))$ bound, which is now a joint work of Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3). Their new result is an elegant extension of their technique for approximate-differential privacy. Although the two proofs are technically different, the Astra argument uses related tree geometry introduced in Bairaktari and Larsen.

0.23

Description Complexity Bounds for Analytic Approximations of Lipschitz Functions

cs.CL math.CA ·2026-10-10 ·Artem Vozmishchev
theory similarity 0.56
Abstract · 19 pages, 6 pages, 2 tables

We study how many bits are needed to write down an elementary analytic expression that uniformly approximates a Lipschitz function. Expressions are finite trees over the basis $\{+,-,\times,÷,\exp\}$ with the variables and rational constants, and their size is $\dc(f)$, the length of the shortest description of $f$ in a fixed binary description language. For functions of one variable we prove that every $L$-Lipschitz $F:[0,1]\to[0,1]$ has an everywhere-defined approximant of accuracy $Δ$ with $\dc(f)\le C\,(L/Δ+\lg(1/Δ+2))$ for all $L,Δ>0$, by a linear spline smoothed with logistic ramps in a description language with one repetition construct. We prove a matching lower bound valid for \emph{every} description language: for $Δ\le 1/36$ and every $L>0$ some $L$-Lipschitz function needs at least $\tfrac1{16}(L/Δ+\lg(1/Δ+2))$ bits. Hence the worst-case description complexity is $Θ(L/Δ+\lg(1/Δ+2))$. For functions on $[0,1]^d$ the same method gives $Θ_d\bigl((L/Δ)^d+\lg(1/Δ+2)\bigr)$, using a tensor-product spline whose coefficients are mixed second differences and cost $O(d)$ bits each. Without the repetition construct the upper bounds carry an additional logarithmic factor, whose necessity for plain expression trees is left open. A reference encoder, decoder and evaluator confirm the constructions numerically, and figures and tables report the checks.

0.27