Papers

For a fixed graph $T$ and a fixed nonempty family $\mathcal{F}$ of graphs, let $\operatorname{ex}(G, T, \mathcal{F})$ denote the maximum number of copies of $T$ in an $\mathcal{F}$-free subgraph of a graph $G$. Alon and Shikhelman~[Algorithmica, 2022] conjectured that if $e(T)> 0$ and no member of $\mathcal{F}$ is a subgraph of a blow-up of $T$, then for every $\varepsilon>0$, approximating $\operatorname{ex}(G, T, \mathcal{F})$ within an additive error $n^{v(T)-\varepsilon}$ is NP-hard for an input graph $G$ on $n$ vertices. The previously established general cases for this conjecture include $\operatorname{ex}(G, K_2, \mathcal{F})$ by Alon, Shapira and Sudakov~[Ann. of Math., 2009], and $\operatorname{ex}(G, K_m, K_k)$ by Alon and Shikhelman. In this paper, we confirm this conjecture for every bipartite graph $T$ and every clique $T$. Our reductions use iterative leaf additions, symmetric rooted extensions and random transversals to encode the maximum number of edges in a $(k-1)$-colorable subgraph of $G$, where $k=\min_{F\in \mathcal{F}}\chi(F)$.

The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $\Omega(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $\Omega(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $\Omega(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $\alpha>0$, there exists a constant $\delta(\alpha)>0$ such that $Q_\epsilon(\text{Tarski}(n,k))=\Omega(kn^{\delta(\alpha)})$ whenever $k>n^\alpha$, and in particular, an $\Omega(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{\Omega(\log k)}$ for exponentially wide grids, where $n=2^{\Theta(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.

The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $\Theta(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

Recent work shows that ordinary Reed–Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed–Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{\Omega_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed–Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed–Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed–Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose–Chaudhuri–Hocquenghem weight-enumerator coefficients into sizes of single Reed–Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.

Hive is a boardless two-player strategy game in which the pieces form the playing surface. We prove that deciding whether White can force a win in single-Queen $n$-Hive, the generalization with exactly one Queen Bee per player, is EXPTIME-complete, even when all pieces are already placed. Our hardness proof reduces from unbounded two-player Constraint Logic: Grasshoppers encode edge orientations, while the One Hive rule enforces the vertex constraints. We obtain the EXPTIME upper bound by considering positions up to translation. The result answers the single-Queen question raised by Andel and Rin. Keeping the same inventory and movement rules, it also gives EXPTIME-completeness for multi-Queen variants. To the best of our knowledge, this is the first use of unbounded two-player Constraint Logic to prove EXPTIME-completeness for a natural problem.

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful as non-deterministic log-space (and more), we do not have unconditional asymptotic separations. In this work, we prove an unconditional separation between a deterministic space complexity class and its catalytic counterpart. More precisely, at the doubly logarithmic scale, we show that catalytic Turing machines can provably compute more languages than standard deterministic doubly-logarithmic space machines. The separation is witnessed by the unary language $\mathrm{POW2} = \{1^n : n \text{ is a power of two}\}$. We construct a catalytic Turing machine that uses $O(\log \log n)$ bits of space and $O(\log n)$ bits of catalytic tape to decide $\mathrm{POW2}$, whereas any standard deterministic Turing machine requires $\Omega(\log n)$ space to decide it.

We study games on finite graphs with labelled or weighted edges in which plays end as soon as the first loop is formed. The resulting play has a lasso shape: a path (head) followed by a cycle (loop). We consider two semantics for determining the winner: the loop semantics, where only the loop matters, and the lasso semantics, where the entire play is taken into account. We show that adopting the lasso semantics may have a dramatic impact on both the complexity of the game and the memory required to play optimally. Mean-payoff games with lasso semantics are no longer positionally determined, and the threshold problem – deciding whether the value of the game is at least 0 – is PSPACE-complete. In contrast, lasso parity games are equivalent to weak parity games, remain positionally determined and are solvable in polynomial time. Furthermore, we show that if a positionally determined winning objective is closed under cyclic permutation and both the objective and its complement are closed under concatenation, then it is equivalent to the parity objective. Finally, we consider mod-k games, where the winner depends on the length of the path modulo k >= 2. We show that these games, in both semantics, are PSPACE-complete. Alongside computational complexity, we analyze the memory required to play optimally. We establish that for any game positionally determined in loop semantics, memory of size 2^n is sufficient in lasso semantics. We complement this by showing exponential memory lower bounds for lasso mean-payoff and mod-k games.

Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as the total duration of a run. Timed automata (TAs) are an extension of finite-state automata with a set of clocks evolving at the same rate and that can be tested or reset. Hence, this formalism is able to represent systems involving timing constraints reacting to the passage of time. Some of the transitions in a timed automaton may be controlled, i.e., enabled or disabled, to limit the runs that are allowed. Execution-time opacity (ET-opacity) aims at studying timing information leakage through the analysis of timed automata. More precisely, the ET-opacity problem consists in deciding whether an attacker can deduce whether some secret locations were visited by a run, solely from the run's duration. When control is allowed, the goal becomes to find a strategy that blocks the runs leaking information. This problem has been shown decidable for TAs, with and without control. However, these existing results only provide upper bounds on the complexity of the ET-opacity problem, sometimes largely above the tight bound. Our main contribution is to provide tight lower bounds for those two results. Moreover, for controllable TAs, two variants of ET-opacity (depending on whether detecting if a run did not visit a secret location represents an information leakage or not, and named full and weak ET-opacity respectively) had been separately studied; we prove here that these two notions are inter-reducible.

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus. This extends to a characterisation of the full bisimulation-invariant exponential-time hierarchy, using a higher-order extension of the polyadic mu-calculus, called PHFL, which is naturally stratified by type order. The bisimulation-invariant fragment of k-EXPTIME is captured by the fragment of PHFL whose formulas have type order at most k. This is obtained using a generalisation of the Immerman-Vardi Theorem by Freire and Martins. Here we provide such a characterisation of the exponential-space hierarchy. We show that the bisimulation-invariant fragment of k-EXPSPACE is captured by the fragment of PHFL of type order k+1 whose formulas are tail-recursive. Tail recursion limits the interplay between fixpoints and higher-order functions so that model checking based on fixpoint iteration can be made more space efficient in a way comparable to tail recursion in programming languages. The capturing result makes use of a generalisation of Vardi's characterisation of PSPACE as first-order logic with partial fixpoints, namely that k-EXPSPACE is captured by higher-order logic of order k+1 with partial fixpoints.

Strong direct-sum theorems relate the information needed to solve many independent instances of a communication problem to the information needed for one instance. For Gap-Majority composition, an optimal information bound was previously known, but preserving the number of communication rounds incurred an additional logarithmic loss. We prove a round-preserving Gap-Majority lemma with constant additive information loss, independent of both the number of instances and the number of rounds. More generally, we establish a variance direct-sum theorem for additive square-integrable observables over product distributions. For protocols with a bounded number of terminal answer values, the extracted single-coordinate protocols preserve the round budget, and their average information cost is at most the original information cost divided by the number of coordinates, plus a term depending only on the answer alphabet and the allowed variance loss. The proof uses centered counterfactual conditional means and a global variance amortization argument. Rather than encoding absolute conditional means for every possible terminal answer, we encode the information not already determined by the common view. The total squared innovation is controlled by a telescoping variance potential, yielding an information loss independent of the number of coordinates. We also derive same-round mean-square estimation bounds for arbitrary terminal outputs.

For every $n\ge22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.

Computational coarse-graining aims to replace a sequence of updates with a cheaper module while preserving task performance. We present a continuation-relative evaluation framework that assesses replacements through the computation that follows them, using downstream task quality and total execution cost as joint criteria. The framework distinguishes boundary representations, summaries of skipped computation, executed operations, and downstream loss. It makes interfaces and permitted deployment information explicit, combines fine-path references with directly trained controls using the same shortened architecture, and accounts for selection overhead. An exact loss decomposition separates replacement effects at a fixed downstream action from effects of changing that action. A finite construction shows how retained information can reduce the stipulated cost of zero-error prediction under fixed information and controller restrictions. Experiments in two frozen pretrained language models show that representation fidelity and task loss can favor different fitting objectives. In a prespecified comparison on a 1.7-billion-parameter model, next-token-loss training lowers in-distribution negative log-likelihood by 0.1901 nats per scored token compared with reconstructing the skipped blocks' output, using the same optimizer and update count. This ranking reverses in all nine paired comparisons under distribution shift. In a recursive expert prototype, the jointly adapted candidate lowers task error relative to frozen-bank and router-only baselines, but trails directly trained controls, and the tested input-only selectors fail the joint quality-cost criteria. Together, the protocol and studies provide explicit criteria and diagnostics for distinguishing useful computational replacement from local approximation gains within specified interfaces and evaluation settings.

Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-\kappa}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over trilinear tensor carrier graphs. In this work, we present a constructive combinatorial optimization over the alternating carrier bipartite matching graphs of the Schönhage trilinear tensor decomposition at dimensions h=23 and h=25. Through an alternating augmenting path search, we uncover a non-trivial cluster-unlocking cascade that eliminates 185 carrier roles (95 roles in h=23 and 90 roles in h=25), reducing the global physical wire width by 377,890 wires from the reviewed baseline W = 177,284,805 down to W = 176,906,915. Evaluated over the exact 10^{-14} rational grid, this wire reduction certifies an improved second-moment coefficient AB = 5,164,059 / 125,000,000,000 and establishes the sharpened conditional exponent \kappa = 826,215,307 / 20,000,000,000,000 \approx 4.131076535 \times 10^{-5}, strictly surpassing the preceding record on this architecture (\kappa \approx 4.123864 \times 10^{-5}). All 47 polynomial constraints and 7 rational security margins are audited in exact Q-arithmetic with zero floating-point error, and the fundamental wire reduction identity is formally verified in the Lean 4 interactive theorem prover without unproven axioms.

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $\Theta(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

We revisit autobidding equilibria in GSP sponsored shopping auctions, recently proposed and studied in Dütting et al. On the existence side, we show that autobidding equilibria under both budget constraints (ABE-B) and return-on-investment constraints (ABE-R) always exist and, moreover, always admit equilibria with polynomial-size support over the allocation space. On the computational side, we show that computing an exact equilibrium is in FIXP, and that computing an approximate equilibrium is in PPAD. We also prove that computing an approximate equilibrium is PPAD-hard for both ABE-B and ABE-R. Together, these results provide a fairly comprehensive picture of the computational complexity of autobidding equilibria in GSP sponsored shopping auctions.

We'll call a map from basic to clopen sets of binary sequences an encoding if it preserves uniform Lebesgue measure and the disjointedness relation. For some notion of randomness $R$ we can ask if there is a computable encoding $E$ such that for every non-Martin-Löf-random (non-MLR) sequence $\alpha$, the sequences in $E(\alpha)$ are non-$R$. Thus we can use $E$ and randomness test for $R$ to construct a randomness test for MLR. We show that there is no such $E$ for partial computable randomness (PCR), but there is one for Kolmogorov-Loveland randomness. Indeed, there is a total computable $E$ and a pair of total computable non-monotonic betting strategies such that on every sequence in $E(\alpha)$ at least one of the strategies wins whenever $\alpha$ is non-MLR.

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a “value” to each type, and prioritizes matches with high “surplus” (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

We study the difficulty of finding a new solution when a list of distinct solutions is already supplied. For any fixed finite collection of list lengths, we can prescribe the additional-solution degrees while preserving a given $1$-paddable domain and first-solution degree. We also prove an exact compatibility condition for prescribing an arbitrary positive-list degree at the same time: it must dominate every prescribed fixed-level degree, and this condition suffices. All degrees use polynomial-time reductions with at most one oracle query and correct behavior on empty fibers; the realization needs no assumption about P versus NP. The combined construction gives each underlying witness exponentially many short counter copies. A list that exhausts these copies is long enough to pay for exhaustive search through the underlying witness bound. Separately, we construct a total problem whose first-solution task and every fixed-length additional-solution task are polynomial-time solvable, while its arbitrary-list task is FNP-complete. Assuming P differs from NP, the domain, first degree, and entire fixed-level degree sequence therefore do not determine the arbitrary-list degree. A constant fiber cap restores determination by finitely many fixed levels. The constructions change witness sets and do not prescribe an infinite sequence of degrees or enumerate all remaining solutions.

We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary $U\in\mathrm{SU}(3)$ using only forward queries. Three queries prepare a catalyst independently of the input state. Four further queries implement transposition while returning the catalyst unchanged and uncorrelated with the output. Two uses within an antisymmetric encoding implement inversion with eight processing queries and return the same catalyst. Reusing the catalyst implements $m$ transpositions or inversions with $3+4m$ or $3+8m$ total queries, respectively. More generally, we prove that exact transposition and inversion of an unknown $U\in\mathrm{SU}(d)$, $d\ge2$, require at least $d+1$ and $d^2-1$ processing queries, respectively, in fixed causal order. These processing bounds hold for any program state prepared independently of the input state using finitely many forward queries, even if that state is consumed during processing. Both our catalytic qutrit algorithms attain their respective bounds. Moreover, exact qutrit transposition with four processing queries requires at least three preparation queries, and our construction attains this bound.

We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ game $\Psi$ with alphabet size at most $k$, it is $\mathbf{NP}$-hard to distinguish between the case that $\mathrm{val}(\Psi)=1$ and the case that $\mathrm{val}(\Psi)\leq \varepsilon$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, CCC 2002]. Previously, the best known result, due to [Dinur, Khot, Kindler, Minzer, Safra], established the almost-perfect completeness version (but applied to the stricter problem of $2$-to-$1$ games). Using results from the literature, we get the following implications: (1) for all $k\in \mathbb{N}$, given a $3$-colorable graph $G$, it is $\mathbf{NP}$-hard to find a proper $k$-coloring; (2) for all $\delta>0$, given a $2$-colorable $3$-uniform hypergraph $G$, it is $\mathbf{NP}$-hard to find in it an independent set containing at least $\delta$ fraction of the vertices. Our proof is a three-step construction that builds on the two-step framework of [Dinur, Khot, Kindler, Minzer, Safra]. In the outer-PCP step, we use quadratic equations to gain perfect completeness. We then construct a new middle PCP that performs low-rank tests while preserving a key covering property. Finally, we construct a new inner PCP based on a tensor of the standard Grassmann encoding with its low-rank variant due to [Golowich, FOCS 2023].

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $\Omega(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed $\delta<1$, a worst-case singleton success guarantee $\Omega(n^{-\delta})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $\omega(\log n/n)$ yields satisfiability circuits of size $(s+2)^{O(1)}2^{o(v)}$ for length-$s$ descriptions with at most $v$ witness variables, hence subexponential in $v$ when $s=v^{O(1)}$. Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to $NP\subseteq P/poly$. For explicit unions of at most $n^\beta$ affine components, success $\Omega(n^{-\delta})$ implies the same collapse whenever $\beta,\delta\ge0$ and $\beta+\delta<1$. The inverse-linear endpoint is not claimed.

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP $\cap$ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open since then. We answer this question negatively, under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for this problem would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting a widely believed conjecture. Second, assuming the hardness of learning with errors, an average-case analogue of bounded distance decoding, the problem is also hard on average, for an efficiently samplable distribution of polytopes. Both results rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our polytopes, such a matrix exists but is hard to find.

We prove an $\Omega((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetilde{\Omega}(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the strongest lower bound known for any dynamic problem. The same bound holds for incremental undirected shortest paths and subgraph connectivity. To prove it, we bring the recent framework of Ko [FOCS 2026], which gave this bound for Pătraşcu's multiphase problem with Inner Product, to the multiphase problem with Disjointness. Our main technical contribution is to show that verification in Ko's 2.5-round multiphase communication game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.

Agentic AI systems can improve by searching longer, receiving additional support, or modifying how they propose and verify outputs. A performance score does not distinguish these mechanisms. We compare these changes through bounded verification with hidden terminal randomness. A stage specifies admissible transcripts, polynomial bounds, an alternating verification protocol, and a terminal checker. Its native reach uses default support; its closure frontier permits all support already admitted by the interface. Under a uniform pointwise probability gap and task-relative soundness, these are well-defined languages. We prove that independent majority amplification preserves both languages, whereas existential acceptance over random tapes can admit incorrect outputs. Exact verification is the zero-randomness case, with placement and completeness results. The randomized-verifier classes satisfy $\Sigma_k^{\mathrm{P}}\subseteq\Sigma_k^{\mathrm{RV}}\subseteq\Sigma_{k+1}^{\mathrm{P}}$; strict enlargement and depth separation require explicit complexity assumptions, while $\mathrm{BPP}=\mathrm{P}$ yields exact companions with the same frontiers. Representation analysis separates invariant acceptance from core-versus-support labels that can change under refactoring. For recursive self-improvement, uniformly bounded self-modification under a common sound interpreter and fixed verification protocol remains within the same verification class. A separate conditional-error budget controls false selection across adaptively chosen candidates. A quota-enforced XOR-synthesis family separates unbounded ratios of search success from changes in the accepted languages; exact and probabilistic audits check the resulting evidence requirements. The framework ties self-improvement claims to obligations on correctness, admissible evidence, verification resources, and selection error.

The existential theory of the reals asks whether polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\textsf{BPP}^{\textsf C_3\textsf P}\subseteq\textsf C_4\textsf P$, the fourth level of the hierarchy. For each fixed $w$, sentences with $w$ alternating real quantifier blocks lie in $\textsf C_{9w+17}\textsf P$. We then treat exact semidefinite feasibility, PosSLP, square-root sum, geometric real counting, Euler characteristic, and complex feasibility in separate applications. The corresponding bounds include $\textsf{BPP}^{\textsf C_2\textsf P}$ for general SDP, $\textsf{BPP}^{\textsf{PP}}\cap\textsf{P}^{\textsf{NP}^{\textsf{PP}}}$ for PosSLP and square-root sum, and $\textsf{FP}^{\textsf C_4\textsf P}$ for total geometric real counting. Note: These proofs were discovered by ChatGPT after a series of conversations ending on September 29th 2026. A group of researchers has been working to digest the proof, and while the most essential arguments appear correct, we are endeavoring to give this result the treatment it deserves and a proper exposition and development to benefit of the community. However, on October 6th, OpenAI released a very similar result, with a slightly weaker bound. While we work to improve our exposition of this proof, the current version has been uploaded as a service to the community to compare the different proof techniques. While the listed author takes responsibility that the proofs appear to be correct, he has not played a nontrivial role in developing them, and believes the human value will be in good exposition and canonicalization of the results.

We determine the hundredths digit of the real Grothendieck constant by proving $1.773 \leq K_G \leq 1.7799$. Furthermore, numerical heuristics suggest the estimate $K_G \approx 1.779$. We start by simplifying the Gaussian duality theory of $K_G$, based on Hermite projection games and Krivine rounding schemes. The bounds are obtained by a heuristic primal/dual search for these objects, followed by rigorous certification of their values. The search and certification are performed using AI tools, and in particular the rigorous certificates are very large (analytical reductions to thousands of numerical inequalities).