Discrete Mathematics & Computation
40 results · 73 papers · 34 with a Lean formalization
Proves Khot's Unique Games Conjecture. Independent direct reductions also establish NP-hardness, on unweighted graphs, of approximation beyond the Goemans–Williamson ratio for Max-Cut, below factor two for Vertex Cover, and within any fixed constant factor for Min-UnCut and directed feedback vertex set. These direct proofs use established PCP and Label Cover hardness results.
5 papersLeanreasoningProves \(\mathsf L=\mathsf{RL}=\mathsf{BPL}\), resolving derandomization for bounded-error logarithmic-space computation. An effective compiler converts each randomized polynomial-time logarithmic-space machine deciding a language with one-sided or two-sided error into a deterministic logarithmic-space decider with explicit polynomial running-time bounds.
1 paperLeanGives deterministic algorithms using \(2^{O((\log(L+2))^2)}\) bit operations, for complete binary input length L, for ordinary mean-payoff games and two separate extensions. They compute exact values and optimal positional strategies in ordinary games, the nonnegative expectation-of-liminf value set in turn-based stochastic games, and the winning set for nonnegative liminf mean payoff conjoined with parity. Signed rewards, rational chance probabilities, and parity priorities are unrestricted and binary-encoded.
4 papersLeanProves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational \(\delta\in(0,1)\), it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map.
1 paperLeanIt is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed \(0\lt \delta\lt 1/3\), a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size \(\delta n\) otherwise, where n is the number of vertices.
1 paperLeanProves \(\omega\le9/4\) over ℂ, giving \(O_\varepsilon(n^{9/4+\varepsilon})\) arithmetic operations for square matrix multiplication. In characteristic zero, some inner dimension na with a > 0.465 permits \(n^{2+o(1)}\) rectangular multiplication. Further square bounds give ω < 2.258 outside finitely many positive characteristics and ω < 2.371054886006746 over every fixed field.
3 papersLeanProves an \(\Omega(n^3)\) lower bound for the border determinantal complexity of the \(n\times n\) permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least \(cn^3\), for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.
1 paperLeanMultiplies two n-bit integers exactly at every input length in deterministic worst-case time \(O(n(\log n)^{1-\kappa})\), with \(\kappa=2^{-182}\), on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. This disproves the Schönhage–Strassen \(n\log n\) optimality conjecture in the ordinary multitape bit model.
1 paperEstablishes a randomized competitive ratio \(O(\log^2(k+1))\) for k-server on every metric space, matching the worst-case lower-bound order. One policy serves every finite oblivious request sequence, including on infinite unbounded metrics. On finite rational metrics, a uniform implementation has polynomial preprocessing and per-request bit cost in the input length and \(\log(t+1)\) at request t, with a finite instance-dependent additive movement constant.
2 papersLeanFor every finite matroid known in advance, gives a distribution-independent online rule using one independent sample per element and earning a universal constant fraction of the expected offline optimum. Values are independent and nonnegative, with finite expected optimum. The guarantee holds even when the arrival-order adversary sees all samples, values, and the rule's entire random seed; no polynomial-time implementation is asserted.
1 paperLeanConstructs a single language in deterministic polynomial time whose n-bit membership function requires \(2^{\omega(\sqrt n)}\) total gates in unbounded-fan-in OR–AND–OR circuits, at every sufficiently large input length. This crosses the square-root-exponent threshold for explicit depth-three Boolean circuit lower bounds.
1 paperLeanGives a fully polynomial randomized approximation scheme for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts. Also proves the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points.
2 papersLeanGives a fully polynomial randomized approximation scheme for counting common integer bases of two integral polymatroids of equal total rank, supplied by exact rank-value oracles. Capacities are binary-encoded, each integer vector counts once, and oracle calls and bit operations outside the oracles are polynomial on every execution. For matroids presented by independence oracles, the results also cover common independent sets of prescribed, unrestricted, or maximum cardinality, even when the ranks differ.
2 papersLeanFor nonnegative integer matrices with prescribed row and column sums, gives exact uniform sampling in expected polynomial bit time and almost-uniform sampling in worst-case polynomial bit time. The dimensions and binary-encoded margins are unrestricted. Also gives a fully polynomial randomized approximation scheme for counting such tables with arbitrary individual cell bounds, including structural zeros, with polynomial cost on every execution.
2 papersLeanFor each characteristic, constructs in deterministic polynomial bit time a polynomial-dimensional matrix tuple detecting every nonzero division-free noncommutative formula of bounded size over any field of that characteristic. Rational formulas over ℚ also admit polynomial-size hitting lists whenever they have a defined rational-matrix evaluation.
3 papersLeanProves that approximating Uniform Sparsest Cut within any fixed constant factor is NP-hard, even with nonnegative rational capacities and unit demands. The Goemans–Linial semidefinite relaxation also has integrality gaps of order at least \(\sqrt{\log n}/(\log\log n)^3\), approaching the square-root-logarithmic upper bound.
2 papersLeanDisproves the modified integer round-up conjecture of Scheithauer and Terno: the integral bin-packing optimum can exceed its configuration linear-programming value by an arbitrarily large additive constant. Approximating the optimum within any fixed additive constant is also NP-hard, even when every item exceeds 1/6 and each bin holds at most five items.
1 paperLeanProves the Courtade–Kumar conjecture: among Boolean functions of independent uniform bits, a single coordinate retains the most mutual information after independent bit-flip noise. A stronger theorem treats randomized binary summaries at fixed initial information. The Hellinger conjecture is also proved for every Boolean output bias and noise correlation.
2 papersLeanGives a randomized algorithm finding an exact maximum-cardinality matching in any simple undirected graph in \((n+m)^{1+o(1)}\) word time, with success probability at least 2/3. The time bound holds on every computation path. The same guarantees apply to finding a spanning subgraph with prescribed admissible vertex degrees, or deciding that none exists.
1 paperFor every fixed rational \(\varepsilon\in(0,1)\), gives a randomized \((1+\varepsilon)\) approximation to unit-cost edit distance in worst-case expected time \(N^{1+o(1)}\), with success probability at least 2/3. The strings have total length N and polynomially bounded integer symbols. This is an asymptotic guarantee at fixed accuracy.
1 paperLeanAt every fixed deletion probability in \((0,1)\), reconstructing an arbitrary length-n binary string requires \(n^{\Omega(\log\log n)}\) independent traces, ruling out polynomial-sample reconstruction. A uniform decoder achieves quasipolynomial sample and running-time bounds for known fixed rational retention probabilities. When the deletion probability is at most \(n^{-\varepsilon}\) for fixed ε > 0, both bounds become polynomial in the input and parameter encoding.
3 papersLeanResolves the three-processor unit-job scheduling problem of Garey and Johnson: a deterministic polynomial-time algorithm minimizes makespan for nonpreemptive unit-length jobs with arbitrary precedence constraints on three identical parallel machines. For an explicitly given precedence graph, it decides deadline feasibility exactly and constructs a feasible schedule.
1 paperLeanGives a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming \(P\ne NP\), the optimal infimum approximation factor is \(1+2/e\).
2 papersLeanProves that every exact semidefinite lift of the perfect matching polytope has exponential size, answering Rothvoss's polynomial-size lift question negatively. The bound holds even for the positive semidefinite rank of its odd-cut slack matrix after any fixed shift \(0\lt \rho\lt 1\), allowing arbitrary real positive semidefinite factors.
1 paperLeanProves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most \(8d\sqrt n\), uniformly for \(1\le d\le n\). Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with \(\mathop{\mathrm{sign}}\nolimits (0)=1\).
1 paperLeanGives a deterministic polynomial-time algorithm constructing a common superstring of length at most twice the optimum for every finite family of explicitly represented strings. The running time is polynomial in the full encoded input length, including symbol labels.
1 paperLeanProves exponential lower bounds both for complementing two-way nondeterministic finite automata and for simulating one-way nondeterministic automata by two-way deterministic ones. The latter resolves the Sakoda–Sipser state-succinctness conjecture over growing finite alphabets; both results rule out polynomial state bounds independent of alphabet size.
2 papersLeanGives a deterministic length-n discrete Fourier transform algorithm using \(O(n(\log n)^{1-\delta})\) operations for every n, with explicit \(\delta=10^{-13}\). The model uses exact complex arithmetic, unrestricted coefficients and a supplied root of unity, and counts scalar preparation and logarithmic-word indexing.
2 papersLeanResolves the simple-undirected Kannan–Tetali–Vempala conjecture: the lazy edge-switch chain mixes in \(O(n^8)\) time for every graphical labeled degree sequence. The same degree-constrained graphs can also be sampled exactly uniformly by an almost-surely terminating algorithm with expected polynomial bit running time.
1 paperLeanConstructs total Boolean functions with block sensitivity \(\mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha\) for a fixed α > 2, disproving the quadratic strengthening of the Sensitivity Conjecture. Here \(s(f)\) counts influential individual-bit flips, while block sensitivity allows disjoint groups of bits to change together.
1 paperLeanProves unconditional \(n^{\Omega(k)}\) deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix models. With dimension as input, joint equivalence is EXPTIME-complete even on subcubic graphs; deciding whether refinement identifies a graph is also EXPTIME-complete.
4 papersLeanEvery regular language over a finite alphabet has a generalized regular expression with at most three nested Kleene stars, allowing union, concatenation and complement over the same alphabet. This establishes an absolute bound independent of automaton size, resolving the uniform-boundedness version of the generalized star-height problem.
3 papersLeanOver every characteristic-zero field, the \((1,1)\) entry of a product of n independent \(n\times n\) variable matrices requires \(n^{\Theta(\sqrt n)}\) gates in homogeneous depth-five sum–product circuits. This sharp bound allows shared gates and bottom linear forms involving all variables.
1 paperLeanResolves the quasilinear PCP-for-PPAD conjecture. An End-of-Line instance of length N reduces to numerical circuit constraints of total length \(N(\log N)^{O(1)}\) such that any polynomially encoded rational assignment satisfying all but a fixed fraction to fixed accuracy yields an endpoint solution. Such assignments always exist, giving robust local verification with only quasilinear size overhead.
1 paperDetermines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using \(O(T^{2/5}\log^C(T+2))\) space, improving the square-root exponent. Heads move at most one cell per step; finitely many read-only input heads are allowed. Initial contents are independent of T, and contents and input symbols have polylogarithmic-space access. Simulation time is unrestricted.
1 paperLeanGives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary \(O(2^{0.49n})\) word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and success probability is at least 2/3 on every input. Inputs may repeat positive integers; words have \(O(n+b)\) bits for maximum input bit length b.
2 papersFor C2 potentials with a supplied minimizer and \(I\preceq\nabla^2V\preceq2I\), proves that sampling within total variation 1/10 requires only \(C_\varepsilon d^\varepsilon\) exact value-and-gradient queries for every fixed ε > 0. The bound holds on every run, with unrestricted computation between queries. A logarithmic lower bound also holds, so the optimal power-law exponent in this oracle model is zero.
1 paperLeanFor fixed A > 0, a one-pass learner with \(Ad^2\) persistent bits needs \(\Omega_A(d\log(1/\epsilon))\) noiseless Gaussian samples to recover a unit vector to angular error \(0\lt \epsilon\le1/10\) with probability 2/3, uniformly in accuracy for large d. Computation and randomized updates are unrestricted, but output uses only the terminal state, stopping index and fresh randomness.
6 papersLeanProves that the existential theory of the reals lies in the counting hierarchy. More generally, truth of existential–universal real sentences can be decided at one fixed level of that hierarchy, even when their integer polynomials are specified by arithmetic circuits.
1 paperGives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽p, including multiplicities, in bit complexity polynomial in \((n+1)\log p\). The prime is supplied in binary. No randomness, integer-factorization or primitive-root oracle, or GRH assumption is required.
1 paperNo result matches this filter yet.