The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources $ν$ satisfying $ν[w]\le DP[w]^s$ for every finite prefix $w$ of the random tape, where $P$ is an independent reference law, $0<s\le1$, and $D\ge1$; individual choices may be predictable, even determined by the past. The worst-case probability of any closed tape event $E$ is exactly $\min\{1,DC_s(E)\}$, where $C_s(E)$ is the infimum cost of covering $E$ by prefixes of varying depth, a tree max-flow/min-cut identity that makes worst-case survival probabilities exact and optimizable over the algorithm's choices. Three applications follow. For $n$ tasks on one machine, each retried until the next random symbol lies in its success set, every schedule has the same makespan distribution under independent randomness, yet under our constraint two fixed orders miss a linear deadline with worst-case probabilities $1$ and $\exp[-Θ(n)]$; a static priority rule is optimal at every deadline. For the standard local walk on a $k$-CNF with an assignment that satisfies a majority of each clause, we determine the sharp source threshold $s_*$. Below $s_*$, on some instances a single admissible source forces nontermination however clauses are selected; at $s_*$, with fixed $D$, the expected number of flips is at most cubic in the initial Hamming distance, against linear under independence, with matching worst-case instances; and any fixed margin above $s_*$ restores linear dependence on the distance. Third, verified backtracking for noisy predecessor search remains correct under a sufficiently strong bound on the comparison errors. In every setting the algorithm may also restart, which supplies no fresh randomness; restarting restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.
In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical verifier and a quantum prover over a classical channel where the verifier can verify that the prover has possessed a specified number of qubits for a specified period of time. PoQM generalize proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021] where a classical verifier can verify that the prover is not classical. Our contributions are summarized as follows: We introduce PoQM. We also introduce a variant of PoQM, which we call inefficient-verifier PoQM (IV-PoQM), where the verifier's final computation to make the decision is not necessarily efficient. We construct PoQM based on the hardness of LWE. Specifically, we give two constructions of PoQM. The first one is of two-round and has negligible soundness error under the subexponential-hardness of LWE. The second one is of polynomial-round and has inverse-polynomial soundness error under the polynomial-hardness of LWE. We show that IV-PoQM imply one-way puzzles. Moreover, we show that a certain restricted version of PoQM implies quantum computation classical communication key exchange, which suggests the difficulty of black-box constructing PoQM from one-way functions. We show that constant-round PoQ imply PoQM or single-round PoQ (with a quantum verifier). Single-round PoQ are ``trivial'' PoQ in the sense that the verifier asks the prover to solve a classical problem which is quantumly easy but classically hard. The result therefore demonstrates that PoQM capture ``genuinely-interactive'' PoQ. We show that if constant-round IV-PoQ that are black-box constructed from quantumly-secure falsifiable assumptions exist then IV-PoQM exist. This result implies that IV-PoQM can be constructed from quantumly-secure constant-round statistically-hiding commitments.
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, the load distribution is still governed by this Poisson distribution, albeit in a (necessarily) weaker manner. This allows us to show that a random linear map behaves like a fully random map in the following ways: 1. $\textbf{Expected loads.}$ We show that the expected value of the $r$th largest bin is governed by the $r$th largest value among $n$ independent Poisson random variables of mean $m/n$. Specializing to the canonical setting of $m=n$ and $r=1$, our bounds show that the expected maximum load when $n$ balls are hashed into $n$ bins by a random $\mathbb{F}_2$-linear map is no more than the corresponding expectation for a fully random map $\textit{plus}$ $\frac{3}2 + o(1)$. Specializing to $m\gg n\log n$, we show that the expected max load is $(1+o(1))m/n$ in this regime. 2. $\textbf{Concentration.}$ When $m\gg n\log (1/ρ)$ balls are tossed into $n$ bins randomly, we expect with $0.99$ probability that $\textit{every}$ density-$ρ$ subset of bins will contain a $(1\pm o(1) )ρ$-fraction of the balls. We show that this remains the case if the $m$ balls are tossed using a random linear map, and our bound matches the $o(1)$-factor produced by the fully random case. This gives a stronger version of the Leftover Hash Lemma for linear maps. An implication of this is that all bins have load $m/n \pm O(\sqrt{(m/n)\log n})$ with probability $0.99$. We obtain these results by showing that the average of a log-potential on the bin loads is upper bounded by the cumulant generating function of a Poisson random variable of mean $m/n$.
Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline. We study its threshold decision form for finite collections of independent sporadic tasks scheduled preemptively on one processor. We prove that this problem is $Σ_2^P$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. The existential choice is the selected task set, while the universal condition requires every processor-demand window to remain feasible. Our hardness reduction already uses constrained-deadline tasks. It represents universal assignments by Chinese Remainder Theorem timestamps and uses polynomial-weight local selector locks to enforce a valid existential assignment. The reduction produces polynomially many tasks, and every generated execution time, deadline, period, task value, and target is polynomially bounded in the source-instance size.
We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer $Δ\ge3$, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than $2\sqrt{Δ-1}$. Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.
The Minimum Equivalent Expression problem (MEE) asks, given a propositional formula $φ$ and an integer $k$, whether $φ$ is equivalent to a formula with at most $k$ occurrences of propositional variables. While the problem is clearly in $Σ_2^p$, its completeness under polynomial-time many-one reductions has remained open since at least 1979. Buchfuhrer and Umans showed in 2008 that it is $Σ_2^p$-complete under polynomial-time Turing reductions. In this note, we present a proof discovered by GPT-Sol-6.1 which establishes that MEE is $Σ_2^p$-complete also under polynomial-time many-one reductions.
We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{Ω(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{Θ(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=Θ(t^2)$; as a function of $N$ this is $N^{Ω(\sqrt{\log N/\log\log N})}$ along an infinite family. In an appendix we show that applying the padding construction directly to Algorithm A gives $Ω(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{Ω(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.
We show that if k-SUM is hard, in the sense that the standard algorithm is essentially optimal, then a variant of the SETH called the Primal Treewidth SETH is true. Formally: if there is an $\varepsilon>0$ and an algorithm which solves SAT in time $(2-\varepsilon)^{tw}|φ|^{O(1)}$, where $tw$ is the width of a given tree decomposition of the primal graph of the input, then there exists a randomized algorithm which solves k-SUM in time $n^{(1-δ)\frac{k}{2}}$ for some $δ>0$ and all sufficiently large $k$. We also establish an analogous result for the k-XOR problem, where integer addition is replaced by component-wise addition modulo $2$. As an application of our reduction we are able to revisit tight lower bounds on the complexity of several fundamental problems parameterized by treewidth (Independent Set, Max Cut, $k$-Coloring). Our results imply that these bounds, which were initially shown under the SETH, also hold if one assumes the k-SUM or k-XOR Hypotheses, arguably increasing our confidence in their validity.
Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano
Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.
We present improved lower bounds for nine classical Ramsey numbers: $\mathbf{R}(3, 13)$ is increased from $60$ to $61$, $\mathbf{R}(3, 18)$ from $99$ to $100$, $\mathbf{R}(4, 13)$ from $138$ to $139$, $\mathbf{R}(4, 14)$ from $147$ to $148$, $\mathbf{R}(4, 15)$ from $158$ to $159$, $\mathbf{R}(4, 16)$ from $170$ to $174$, $\mathbf{R}(4, 18)$ from $205$ to $209$, $\mathbf{R}(4, 19)$ from $213$ to $219$, and $\mathbf{R}(4, 20)$ from $234$ to $237$. These results were achieved using AlphaEvolve, an LLM-based code mutation agent. Beyond these new results, we successfully recovered lower bounds for all Ramsey numbers known to be exact, and matched the best known lower bounds across many other cases. These include bounds for which previous work does not detail the algorithms used. Virtually all known Ramsey lower bounds are derived computationally, with bespoke search algorithms each delivering a handful of results. AlphaEvolve is a single meta-algorithm yielding search algorithms for all of our results.
Can AI based methods help us make advances in complexity theory? We provide evidence towards answering this in the affirmative, using AlphaEvolve (an LLM code mutation agent) to obtain new results in three settings: a) We improve a recent result of Kunisky and Yu to obtain near-optimal upper and (conditional) lower bounds on certification algorithms for MAX-CUT and MAX-Independent Set on random 3- and 4-regular graphs. Our improved lower bounds are obtained by constructing nearly extremal Ramanujan graphs on as many as $163$ vertices, and our upper bounds are obtained via analytical arguments. b) We obtain new inapproximability results for MAX-4-CUT and MAX-3-CUT, proving that it is NP-hard to approximate them within factors of $0.987$ and $0.9649$ respectively, using AlphaEvolve to discover new gadget reductions. Our MAX-4-CUT result improves upon the SOTA of $0.9883$, and our MAX-3-CUT result improves on the current best gadget-based inapproximability result of $0.9853$, but falls short of the SOTA of $16/17$ that relies on a custom PCP (rather than a reduction from ``standard'' Håstad-style PCPs). c) Inapproximability for the metric Traveling Salesman Problem (TSP): We show that it is NP-hard to approximate the minimum cost tour within a factor of $111/110$ using AlphaEvolve to discover a new gadget, thus improving the SOTA of $117/116$. Along the way, we provide new modular soundness and completeness arguments that can be of independent interest. A key technical challenge we faced: verifying a candidate construction produced by AlphaEvolve is costly (sometimes requiring time exponential in the size of the construction). We used AlphaEvolve itself to evolve the verification procedure to be faster (sometimes by $10,000\times$ for our gadgets). Our results suggest that gadget based proofs would benefit from a pass through AI-based tools to obtain stronger results.