By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

The Exponential Time Hypothesis is False

For every fixed k≥2k \ge 2, there exists a deterministic algorithm that counts the satisfying assignments of an arbitrary kk-CNF formula on nn variables and mm clauses in (n+m)Ok(1)2n/(log⁡n)1/2+o(1)(n + m)^{O_k(1)} 2^{n / (\log n)^{1/2 + o(1)}} time and polyk(n,m)\mathrm{poly}_k(n, m) space, which refutes the Exponential Time Hypothesis (ETH).

For each fixed k≥2k \ge 2, there exists a deterministic algorithm that, given a kk-CNF FF on n≥20n \ge 20 declared variables with mm clauses, computes #F\#F in (n+m)Ok(1)2Ok(nlog⁡log⁡n/log⁡n)(n + m)^{O_k(1)} 2^{O_k(n \log \log n / \sqrt{\log n})} bit operations and (n+m)Ok(1)(n + m)^{O_k(1)} bits of space; for each fixed D>0D > 0, its running time on inputs with m≤Dnm \le Dn is (n+m)Ok,D(1)2Ok,D(n/log⁡n)(n + m)^{O_{k,D}(1)} 2^{O_{k,D}(n / \sqrt{\log n})}.

For every fixed k≥2k \ge 2 and ε>0\varepsilon > 0, there exists a randomized algorithm that, given a kk-CNF FF on n≥20n \ge 20 variables with mm clauses, finds an assignment satisfying at least OPT(F)−εm\mathrm{OPT}(F) - \varepsilon m clauses with probability 1−2−Ω(n)1 - 2^{-\Omega(n)}, in (n+m)Ok,ε(1)2Ok,ε(ρ(n))(n + m)^{O_{k,\varepsilon}(1)} 2^{O_{k,\varepsilon}(\rho(n))} time and (n+m)Ok,ε(1)(n + m)^{O_{k,\varepsilon}(1)} space, where ρ(n)=n(log⁡log⁡n)2/log⁡n\rho(n) = n(\log \log n)^2 / \sqrt{\log n}.

On simple graphs with vv vertices and ee edges, the number of independent sets and, for each fixed q≥2q \ge 2, the number of proper qq-colorings can be computed deterministically in 2o(v)2^{o(v)} time and polyq(v,e)\mathrm{poly}_q(v, e) space, and the number of perfect matchings can be computed deterministically in 2o(v+e)2^{o(v+e)} time and poly(v,e)\mathrm{poly}(v, e) space.

There exist a language L∈ENPL \in \mathrm{E}^{\mathrm{NP}} and a constant c>0c > 0 such that the minimum number CL(n)C_L(n) of noninput gates in a fan-in-two Boolean circuit computing LL on {0,1}n\{0, 1\}^n satisfies CL(n)>cnlog⁡nC_L(n) > c n \sqrt{\log n} for infinitely many nn.

For fixed integers k≥2k \ge 2 and c≥1c \ge 1, given mtest≤cnm_{\mathrm{test}} \le cn polynomials P1,…,PmtestP_1, \dots, P_{m_{\mathrm{test}}} over F2\mathbb{F}_2 in n≥20n \ge 20 Boolean variables, each listed as at most (log⁡n)c(\log n)^c monomials of degree at most kk, the exact number of common zeros in {0,1}n\{0, 1\}^n can be computed deterministically in 2Ok,c(n(log⁡log⁡n)2/log⁡n)2^{O_{k,c}(n(\log \log n)^2 / \sqrt{\log n})} bit operations and nOk,c(1)n^{O_{k,c}(1)} space.

For fixed positive constants C,A,bC, A, b, integer s≥2s \ge 2, and a bipartite Boolean tensor network with at most CsCs edges, maximum degree at most ⌈s9/10⌉\lceil s^{9/10} \rceil, vertex count bounded by a fixed polynomial in ss, entries in (Z/2P0Z)[V]/(Vℓ)(\mathbb{Z}/2^{P_0}\mathbb{Z})[V]/(V^\ell) with 1≤P0,ℓ≤Cs1 \le P_0, \ell \le Cs computable in time (s+L)b2As9/10(s+\mathcal{L})^b 2^{A s^{9/10}} and space (s+L)b(s+\mathcal{L})^b, the contraction can be computed deterministically in (s+L)O(1)2O(s/log⁡s)(s+\mathcal{L})^{O(1)} 2^{O(s/\sqrt{\log s})} bit operations and (s+L)O(1)(s+\mathcal{L})^{O(1)} bits of space.

For every fixed dd and n≥20n \ge 20, for a Boolean map G:{0,1}n→{0,1}mG: \{0, 1\}^n \to \{0, 1\}^m where each output bit depends on at most dd input bits, the number ∣G−1(b⃗)∣|G^{-1}(\vec{b})| can be computed exactly, and a preimage can be found whenever one exists, in deterministic time (n+m)Od(1)2Od(ρ(n))(n+m)^{O_d(1)} 2^{O_d(\rho(n))} and space (n+m)Od(1)(n+m)^{O_d(1)}.

Methods

Constructing low-degree polynomial replacement linear forms with shared linear summaries by interpolating (−1)j(-1)^j on a short interval of commuting permutation matrices Πs\Pi_s, measuring exceptional eigenbasis directions via a matrix CBC^{\mathcal{B}}, and derandomizing variable/factor group schedules via conditional expectations.

Source excerpts

“For an interval I = {A_0, ..., A_0 + R - 1} \subseteq {0, ..., Q}, we can enforce the equalities f_I(j) = (-1)^j for j \in I with a polynomial of degree at most R - 1.” · Show in paper

“One can deterministically choose a_v, d_f \in [r]^Q, with d_f(t) = 1 for factors of empty scope, so that max_{u \in B} #{(f, v) \in A : (a_v, d_f) = u} <= 2M/D, #{v \in [n] : a_v(t) = g} <= 2n/r (t \in [Q], g \in [r]).” · Show in paper

Recovering Taylor coefficients at interpolation points t∈[Q]t \in [Q] by separating shifted inputs ΔP⃗f,v(z)\Delta \vec{P}_{f,v}(z) into a formal vector X⃗\vec{X}, applying inclusion-exclusion (Möbius inversion on subsets) over Boolean substitutions X⃗=1U\vec{X} = \mathbf{1}_U, and reconstructing H(0)H(0) via rational Hermite interpolation.

Source excerpts

“Hermite interpolation recovers H, and hence Z = H(0), from these QJ coefficients in A.” · Show in paper

“Apply Lemma 3.3 to [z^j] G_x over A for each j < J. All coefficients can use the same pairs U \subseteq E, |E| <= q, so compute them together in R = A[z]/(z^J).” · Show in paper

Encoding common-zero indicators of sparse F2\mathbb{F}_2 polynomial equations as integer polynomials using complemented Beigel-Tarui modulus-amplifying polynomials pℓ(Y)=∑j=0ℓ−1ej(Y)h(Y)jp_\ell(Y) = \sum_{j=0}^{\ell-1} e_j(Y) h(Y)^j and truncating the product across all equations in Aℓ=Q[V]/(Vℓ)\mathcal{A}_\ell = \mathbb{Q}[V]/(V^\ell) to keep the total input degree linear in nn.

Source excerpts

“Each factor h(y) contributes a factor of two at integer arguments, so a term containing at least \ell such factors can be discarded modulo 2^\ell. This lets us retain only terms whose total power of h is less than \ell, across all equations together.” · Show in paper

Deterministically reducing #k-SAT on sparse formulas to counting common zeros of O(n)O(n) sparse polynomial equations over F2\mathbb{F}_2 by first constructing an edge-based Tanner code on a bipartite Cayley multigraph with ε\varepsilon-biased shifts to exclude small-support violation vectors, and then greedily appending short parity tests using conditional expectations and exact common-zero counts.

Source excerpts

“We use the standard edge-based Tanner code: bits are assigned to the edges of an expander, and the bits incident to each vertex must form a word of a prescribed local linear code” · Show in paper

“For every candidate, compute N(A; h_\gamma) by counting the common zeros of its polynomial system. Append a candidate attaining the minimum, breaking ties by enumeration order.” · Show in paper

Contracting bipartite Boolean tensor networks recursively by packing edges into packets of LL slots, applying a Cauchy deformation Wxy(T)W_{xy}(T), expanding crossing terms into mode variables modulo 2pt2^{p_t}, and recovering the original contraction via tapered Hermite interpolation.

Source excerpts

“The algorithm in Section D.4 replaces a single global Taylor expansion by recursion on the wires. At each call it deforms the wire identifications so that, at a chosen interpolation node, only ports in the same group interact.” · Show in paper

“Lemma D.5 (Tapered Hermite recovery).” · Show in paper