complexity theorists

Abstract: The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

Abstract: We construct, for each deterministic Turing machine that halts on all inputs, one polynomial vector field with rational coefficients that performs the same logical computation at unit Euler step, at every smaller or variable step in $(0,1]$ with divergent sum, and along the flow. This unifies discrete-time and continuous-time computation by polynomial dynamics, which earlier characterizations treated separately. For a machine making $T$ transitions in space $H$, a logical scale $h=2^{-s}$ with $s=O(H)$ suffices, with physical time $O(s(T+s))$, drift disturbances up to $h^{2K}$ for a fixed exponent $K$, and $2Ks+3$ fractional bits at unit step. On a fixed compact domain, polynomial time and robust eventual decision characterize P and PSPACE, respectively, with polynomial scale thresholds and no supplied stabilization horizon in the space case. Without sign, floor or conditional primitives, margin amplification at bounded speed, overlapping polynomial gates and interval-product estimates give the common realization, from which we derive shared logical traces, fixed-field PSPACE-complete prediction and a robust safety family with polynomial certificates common to all Euler steps and the flow.

Abstract: For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{edge}}(H^<;q)$ of $H^<$ is the smallest positive integer $N$ such that there exists an edge-ordered $h$-uniform hypergraph $G^<$ on $N$ vertices such that, for every $q$-coloring of the hyperedges of $G^<$, there is a monochromatic copy of $H^<$ in $G^<$ preserving the hyperedge order. In this note, we show that, for every edge-ordered $h$-uniform hypergraph $F^<$ on $n$ vertices with $m\geq1$ hyperedges, $R_{\mathrm{edge}}(F^<;q) \leq R_h(F;q)^{Cm^2}$ where $F$ is the underlying unordered hypergraph, $R_h(F;q)$ is its standard $q$-color Ramsey number, and $C=C(h,q)>0$ is a constant. For fixed $h\geq3$ and $q\geq2$, this shows that prescribing the hyperedge order does not require an increase in the tower height of the classical upper bound. It also settles a problem posed by Fox and Li (2020), and for $h=2$ gives the bound $2^{O(n^4\log n)}$, improving their bounds for every fixed $q \geq 3$.

Abstract: We give complexity-theoretic separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$. Given a graph $G$, and a fugacity $λ>0$, the hard-core model is given by $Z_G(λ)=\sum_{I\in\mathcal I(G)}λ^{|I|}$, where $\mathcal I(G)$ denotes the independent sets of $G$. For $F\ge1$, an $F$-factor approximation to $Z_G(λ)$ is an estimate $\widehat Z$ satisfying $F^{-1}Z_G(λ)\le\widehat Z\le FZ_G(λ)$. Let $\mathcal G_Δ$ denote the class of $Δ$-regular graphs and $\mathcal G_{Δ,Δ}$ the class of $Δ$-regular bipartite graphs. We give two separation results. (1) There exist an integer $Δ\ge3$, a sufficiently large fugacity $λ$, and a constant $c>0$ so that the following hold: (a) For every $δ\in(0,1)$, deterministic $(1+δ)$-factor approximation on $\mathcal G_{Δ,Δ}$ is possible in time $\exp(cn)\operatorname{poly}(n,1/δ)$. (b) Under the Gap-Exponential Time Hypothesis, there exists no deterministic algorithm running in time $\exp(2cn)\operatorname{poly}(n)$ on $\mathcal G_Δ$ that gives an $\frac{11}{10}$-factor approximation. (2) For every fixed $Δ\ge3$ and $\varepsilon\in(0,1)$, for all sufficiently large fugacities $λ$, the following hold: (a) There exists an algorithm which outputs a deterministic $(1+\varepsilon)^n$-factor approximation to $Z_G(λ)$ on $\mathcal G_{Δ,Δ}$ in polynomial time. (b) Under the assumption $\mathrm P\ne\mathrm{NP}$, there exists no deterministic polynomial-time algorithm on $\mathcal G_Δ$ that gives a $(1+\varepsilon)^n$-factor approximation. Both our algorithmic results follow from a new spanning-tree encoding of independent sets that enables an efficient representation of large independent sets.

Abstract: We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.

Abstract: If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a mapping $f: E(G)\rightarrow E(H)$, such that for every $v\in V(G)$ there is a vertex $x\in V(H)$, such that $f(\partial_G(v))=\partial_H(x)$. If $G$ admits an $H$-coloring then it is common to write $H\prec G$. In this paper, for a fixed connected cubic graph $H$, we consider a decision problem, which we call $H$-coloring. In this problem, on the input one is given a connected cubic graph $G$. The goal is to decide whether $H\prec G$. A conjecture by Hakobyan and the author states that $H$-coloring is polynomial time solvable, if $H$ does not admit a $P_{12}$-coloring. Here $P_{12}$ is the unique cubic graph obtained from the Petersen graph by expanding one of its vertices into a triangle. In this paper, we disprove this conjecture under $P\neq NP$, by showing that $S_6$-coloring is NP-complete. Here $S_6$ is the unique cubic graph on six vertices having exactly one bridge. Our second result is an algorithm that solves $H$-coloring problem in time $O^*(c^n)$, where $H$ is a simple connected cubic graph, $n$ is the number of vertices of the input cubic graph $G$ and $c=\sqrt{8}\approx 2.8284$.

Abstract: We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

Abstract: The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally~$Σ^0_3$, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree $d$ is $Π^0_3$-complete whenever $\mathbf{0}_s <_s d <_s \mathbf{1}_s$.

Abstract: In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately. The question is which of two terminals the token reaches first. ARRIVAL lies in $\mathsf{NP} \cap \mathsf{coNP}$, but no polynomial-time algorithm is known.The fastest known algorithms turn some vertices into terminals and search for consistent guesses of the numbers of tokens that these vertices send out. The first, due to Gärtner et al. [ICALP 2021], searches all vertices at once with an algorithm for fixed points of monotone maps, and the second, due to Haslebacher [ICALP 2025], searches one vertex at a time by binary search. Both search for a fixed point of the same map, which returns how many tokens arrive at the guessed vertices. We guess the vertices in blocks of $k$, between these two extremes, which needs a search in $k$ dimensions with few evaluations of this map. To do so, we build on the connection between ARRIVAL and $\ell_1$-contractions established in the second of these works. We search with $\ell_1$-centerpoints of the remaining guesses, which are guaranteed to exist by Haslebacher et al. [FOCS 2025], and which we approximate deterministically. In order to prove our results, we show how to find the least fixed points of maps from $\{0, \ldots, N\}^k$ to itself that have unit increments. For ARRIVAL on $n$-vertex switch digraphs, this gives run time $2^{\mathcal{O}(n^{1/3} \cdot \log^{2/3} n)}$, improving the previous time bound of $n^{\mathcal{O}(\sqrt{n})}$. We work with the more general \garrival problem, with many tokens and several terminals, and solve it in the same time when there are at most $2^n$ tokens.

Abstract: Cheng and Wang (CCC' 24) showed that BPL is contained in logspace uniform AC$^1$ (denoted as L-AC$^1$). We upgrade their result by showing that $\#$SAC functions (i.e., functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits) can be approximately computed by L-AC circuits with high precision. In particular, approximations of $\#$SAC$^1$ functions can be computed in L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Previously, approximations of $\#$SAC$^1$ functions are known to be in $\mathsf{NC}^2$ via its exact computation given by Vinay (CCC' 91). A main corollary of our result is that BPAuxPDMs and Read-$k$-BPL are computable by L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Notice that multiplicative error approximations can be used directly to decide non-deterministic computations. So our L-AC$^1$ circuits can automatically be used to decide non-deterministic AuxPDMs and hence NL. We note that recently OpenAI announced that BPL $=$ L. Even if we only consider derandomizing BPL, our L-AC$^1$ computation has the advantage that the error can be $2^{-\mathrm{poly}\log n}$ and can be multiplicative.

Abstract: For a partition $\boldsymbolλ = (λ_1,\ldots,λ_r)$ and $n\ge r$, the monomial symmetric polynomial is defined as $$m_{\boldsymbolλ}(x_1,\ldots,x_n) := \sum x_{i_1}^{λ_1} x_{i_2}^{λ_2} \cdots x_{i_r}^{λ_r},$$ where the sum ranges over all distinct monomials obtained by assigning the parts of $\boldsymbolλ$ to pairwise distinct variables. We establish an almost-complete dichotomy for the complexity of the monomial symmetric polynomials $m_{\boldsymbolλ}$: If a family of partitions contains polynomially many distinct parts, then the corresponding monomial symmetric polynomials (on sufficiently many variables) are VNP-complete. If the number of distinct parts is constant, the family admits polynomial-size circuits. Thus the only remaining gap concerns the intermediate regime where the number of distinct parts grows subpolynomially. As part of our proof, we use combinatorial properties of matching polynomials to establish VNP-hardness of the perfect matching polynomial for blow-up graphs; these are graphs with non-generic edge-weights that are obtained by "blowing up" a smaller graph. We reduce these matching polynomials to monomial-symmetric polynomials by combining classical techniques from algebraic complexity theory with structural properties of Sidon sets.

Abstract: We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $Ω((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})$. In particular, we obtain the optimal $Θ((\log n)^3)$ deterministic query complexity in six dimensions.

Abstract: Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.

Abstract: We construct countable, stable, $ω$-categorical structures with at most two binary relations whose CSPs exhibit three complexity regimes: NP-complete, decidable but not in NP, and undecidable. The templates arise from a controlled Hrushovski construction of stable $ω$-categorical graphs $M_α$ for suitable irrational parameters $α>1$. Some of these graphs have NP-complete CSPs. Expanding the graphs $M_α$ by the non-edge relation turns age membership into a restriction of the CSP. For every time-constructible bound $t$, there is such an expansion whose CSP is decidable but not in DTIME$(t)$. For an explicit parameter $α$, the restriction to complete instances belongs to $\mathrm{coNP}$ and the full CSP belongs to $Σ_2^{\mathrm P}$. Separating the ages of the $M_α$ using graphs with large girth and prescribed density yields $2^{\aleph_0}$ distinct CSPs of these expansions, all but countably many of which are undecidable.

Abstract: Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

Abstract: On 6 October 2026 OpenAI published an initial 722 AI-written mathematical manuscripts, organized into 372 problem families, in the public repository github.com/openai/math. The release includes claimed solutions to many prominent open problems. We approach this collection as a treasure mine of mathematical ideas. Our aim is to extract new lemmas, constructions, inequalities and proof mechanisms introduced in the source arguments, and to distinguish them from established tools and new combinations of those tools. We call these mathematical instruments. Extraction comes first; their validity, novelty and possible reuse then become subjects for further study. The resulting descriptions also help readers understand the selected papers without having to reconstruct every argument at the outset. We examine 38 families in two groups of 17 and 21, spanning number theory, geometry, analysis, combinatorics, complexity, algebra, operator algebras, topology and mathematical physics. Each entry records the claim, extracted instruments, antecedents and caveats. Eleven cross-cutting patterns connect the entries, and a scoreboard records formalization status and dependencies. Novelty assessments are provisional and sometimes mixed. Selected source comparisons correct mathematical statements, hypotheses and counts; they do not independently establish priority or certify the underlying proofs. No Lean development was compiled or kernel-checked for this survey. We also briefly describe a subsequent application of the signed restriction lemma from family 112 to circuit lower bounds at every fixed depth.

Abstract: Wyner's common information $J(p)$ and the common entropy $G(p)$ of a pair of random variables $(X,Y)$ with finite ranges and joint distribution $p$ are both defined by an optimization over the auxiliary random variables $W$ that make $X$ and $Y$ conditionally independent: $J(p)$ is the infimum of the mutual information $I(X,Y;W)$, and $G(p)$ is the infimum of the entropy $H(W)$. We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether $J(p)$ is strictly smaller than a given integer $r$ is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of $p$, for improving on the auxiliary $W=X$; every yes-instance satisfies $J(p)<r-1/(4N^2)$ and every no-instance satisfies $J(p)=r$, where $N$ is the number of positive entries of $p$. For the common entropy, deciding whether $G(p)\le r$ for a rational number $r$ is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of $p$, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of $p$, so that approximating $J(p)$ or $G(p)$ within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers $J$ below the threshold of our first reduction while leaving $G$ on it.

Abstract: We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(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 $Θ(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.

Abstract: Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from \textsc{3SAT} to the complement of \textsc{Dual}: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $\mathcal H$ and $\mathcal L$ of total size $2^{\bigoh(n^{2/3}(\log n)^{1/3})}$ such that $\mathcal L \subseteq \Tr(\mathcal H)$ and the formula is satisfiable if and only if $\mathcal L\neq \Tr(\mathcal H)$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither \textsc{Dual} nor \textsc{Dualization} admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for \textsc{Dual} and the combined input and output size for \textsc{Dualization}. In particular, \textsc{Dualization} cannot be solved in output-polynomial time under ETH.

Abstract: In the general probabilistic model of information theory, the signaling dimension of a given communication protocol (or, equivalently, of its state space) is the smallest possible complexity of a classical communication protocol capable of perfectly simulating the given one in terms of input-output correlations. The signaling dimensions of three-, four-, and five-dimensional cross-polytopes have been known to be 3. We give an upper and a lower bound for signaling dimensions of higher dimensional cross-polytopes.

Abstract: We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $Ω((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uniqueness, and adds a logarithmic factor to the lower bound. Iteration gives $Ω((\log N)^{r+2})$ queries in dimension $(7\cdot4^r-1)/3$, for every fixed nonnegative integer $r$, with an implicit constant that may depend on $r$. Consequently, no finite logarithmic exponent bounds the query complexity in all fixed dimensions.

Abstract: We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability. We also characterize exactly which fixed positive vertex weights preserve tractability, with both classifications extending from algebraic weights to fixed real weights in a prescribed exact representation. Our proof hinges on an entropy-based continuation argument: maximal logarithmic support identifies distance kernels as maximum-entropy completions, extending their positive definiteness throughout the parameter interval. This enables distance geometry to recover hidden product coordinates even when planar gadgets cannot distinguish colors; counting-hardness arguments then force the factors to be zero-field Boolean Ising interactions. The classification also yields complete tractability criteria for clock models, coupled Ising systems, and planar contractions of stoquastic imaginary-time kernels. All results have been formally verified in Lean 4.

Abstract: Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering \emph{strong separations}, witnessed by immune languages. The main result of the paper shows that with respect to a random oracle the levels of the polynomial hierarchy separate with immunity. Specifically, with probability one over a random oracle $A$, for every $k\geq 1$ there is a language in $Σ_{k}^{P,A}$ that is immune to $Π_{k}^{P,A}$, and, symmetrically, a language in $Π_{k}^{P,A}$ that is immune to $Σ_{k}^{P,A}$. We thus extend classical results due to Bennett and Gill and Vereshchagin. We accomplish this by developing a "rare-or-wrong" approach to strong separations. We highlight the flexibility of the approach by strengthening other separations with respect to a random oracle from the complexity-theoretic literature.

Abstract: We prove a complexity dichotomy theorem for $\mathrm{Holant}^*$ problems over complex-valued symmetric constraint functions $\mathcal{F}$ on domain size $3$. We give a decidable tractability criterion and prove that if $\mathcal{F}$ satisfies the criterion, then $\mathrm{Holant}^*(\mathcal{F})$ is solvable in polynomial time, and otherwise it is #P-hard. This is the first Holant dichotomy for a set of complex-valued constraint functions on higher domains. We show that complex-valued constraint functions have a rich structure not observed in real-valued constraint functions. This structure is only revealed when we analyze them in a bipartite Holant setting with a non-standard bilinear form and provides the backbone to the proof of the dichotomy. We use group actions and the spin representation of $\mathrm{SL}(2, \mathbb{C})$ in $\mathrm{SO}(3, \mathbb{C})$ and the generalized orthogonal group to facilitate this analysis. We also introduce $\textit{frames}$ and $\textit{shells}$. Frames linearize the group action and provide a unified framework for proving #P-hardness when used in conjunction with shells. Furthermore, we characterize the lower dimensional constraint functions by $\textit{annihilators}$, which makes it possible to analyze $\textit{essentially Boolean domain}$ functions in domain size $3$.

Abstract: We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

Abstract: Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal games. Due to the CSP dichotomy theorem, the complexity of constraint satisfaction problems with classical assignments can be fully understood by studying the symmetries of the CSP, in terms of the polymorphisms of the underlying relational structure. In this work, we show that the polymorphism-based reductions between CSPs can be generalised to gap-preserving reductions between entangled CSPs based on an entangled analogue of the polymorphisms. This reduction allows us to show undecidability of entangled graph colouring with more than three colours, a problem that has proved resistant to prior hardness reductions based on commutativity gadgets.

Abstract: We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with non-negative entries, the problem $\PlGH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs. Furthermore, $\PlGH(M)$ in (2) consists of precisely those that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy is achieved by forming a (centered) logarithmic matrix algebra (a vector space with bilinear multiplication) by taking entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. The current version is part I, which contains the proof for the dichotomy of entrywise positive and positive definite matrices, which is at the core of the dichotomy for non-negative matrices. Part II contains the extension from entrywise positive and positive definite matrices to non-negative matrices.

Abstract: The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

Abstract: We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the QMA-complete Local Hamiltonian problem (Kitaev, Shen, and Vyalyi, 2002). For the $β$-gapped, frustration-free case, Bravyi, Bessen, and Terhal (2006) showed that the problem is MA-complete when $β= 1/\mathrm{poly}(n)$. Aharonov and Grilo (2019) derandomized this algorithm and proved membership in NP for constant gap $β= Ω(1)$. We present an improved algorithm and analysis, establishing membership in NP even when $β= Ω(1/(\log\log n))$. We complement our result with an explicit example demonstrating why the analysis does not extend directly to $β= o(1/\log\log n)$.

Abstract: A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

Abstract: Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$. This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$. The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables. As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer. Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle. Our result then removes the oracle. We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).

Abstract: We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every polynomially bounded arity, a randomized polynomial-time comparator of error at most $(1-1/poly(n))2^{-t}$ gives $ NP/ poly\cap coNP/ poly$ recognition with common advice. The proof uses limited independence, polynomial occurrence certificates, and a self-contained positive-relation advice transfer. For SAT at arity $O((\log n)^d)$, both this relative-gap hypothesis and deterministic comparability imply $PH=S^{NP}$, the uniform bound $PH\subseteq BPTIME(2^{O((\log n)^{d^2})})$, and symmetric verification with polynomial-length certificates and an oracle-free deterministic $2^{O((\log n)^d)}$ predicate. Polynomial-advice deterministic decoding has the same exponent $d$. Applying the randomized simulation to an unconditional diagonal language yields, for every fixed $\varepsilon>0$, $\mathrm{BPP}\subsetneq BPTIME(2^{O((\log n)^{d^2+\varepsilon})})$, without advice. The larger clock remains subexponential under every fixed number of self-compositions. A layered oracle satisfies deterministic comparability and $NP^O=coNP^O$ but excludes randomized NP algorithms with smaller logarithmic power, establishing a relativized limit on the SAT exponent $d$. This expanded version also develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary between the randomized regimes. Under deterministic comparability, uniform deterministic promise-unique search additionally gives $UEXP=EXP$. The ordinary second-level collapse $PH=Σ_2^p$ for $d>1$ remains unproved.

Abstract: We prove an $Ω(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound for this fundamental algebraic problem for any explicit polynomial. However, the authors of this note were unable to follow the details and verify the argument in arXiv:2606.13628, in spite of considerable effort on their part. The proof we provide here is short, (almost) self-contained and seemingly simpler.

Abstract: We observe that the classical $n\log n$ time threshold for one-tape Turing machines is also a threshold for their accepting-path counts. Below it, every nondeterministic one-tape machine running in strong $o(n\log n)$ time has a rational ordinary generating function of accepting-path counts. At strong $O(n\log n)$ time, the situation changes completely: there is a fixed one-tape machine whose accepting-path function is complete for $\#\mathsf P_1$, the tally analogue of $\#\mathsf P$, under parsimonious polynomial-time tally reductions. A second construction within the same time bound gives positive accepting-path counts with a noncomputable exponential growth rate. The rationality result combines the one-tape time gap with the linear-time counting theorem of Tadaki, Yamakami and Lin. The completeness proof adapts the linear-time universal counting machine of Beame et al. to the one-tape setting.

Abstract: Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.

Abstract: Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing coefficient to be $δ(x,y)=\min(\mathbb{P}(x\prec y),\mathbb{P}(y\prec x))$ with $δ(P)=\max_{x,y}δ(x,y)$. We prove (Theorem 1) that sufficiently large width forces $δ(P)$ to be arbitrarily close to $1/2$, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on $k$ vertices, or an almost fixed order on $t$ vertices with one further vertex inserted uniformly among the $t+1$ slots. We also show that, for fixed $k$, the first possibility must occur within any antichain $X$ of size $Ω(n^{2/3})$.

Abstract: The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$--$\frac{2}{3}$ conjecture in over 30 years.

Abstract: A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree.

Abstract: Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $Ω(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ and asked about the range in between. We show that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $ε$ on affine circuit inputs with at most $2^{\lfloor 2/ε\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$. Success $10/\log L$ on affine inputs with at most $L^{1/3}$ satisfying assignments suffices, where $L$ is the description length, and on inputs with one or two satisfying assignments the threshold $2/3$ drops to $3/5$. No cryptographic assumption is used, and the procedure may read the entire circuit. The proof compiles a pool of circuits into one circuit whose satisfying assignments are indexed by tags in $\mathbb{F}_2^d$. Each member is assigned an affine region of tag space, and if one member is unsatisfiable, the satisfying set shrinks to that member's region. Because regions may overlap and have different dimensions, the collapse reduces to a combinatorial bound: no set of tags meets more than a $2/d$ fraction of an equally weighted family of affine subspaces of all dimensions below $d$ in exactly one point. This regional counting cannot go below order $1/\log L$. The range between $Θ(1/n)$, achieved by affine hashing, and $O(1/\log n)$ remains open.

Abstract: This paper characterises substantive agency and identifies the additional bridges under which it has a standard complexity-theoretic consequence: conditionally, P __ = N P . The constitutive core separates coherent plurality, causal openness, anticipatory non-pointing, act-level singularisation, and endogenous sourcehood. Its temporal claim yields a two-sided modal result: exact passive pre-act selection is incompatible with jointly retaining singularising priority and invariance under causally inert informational extension. If every standard polynomial procedure is deployable in that passive form, the actualisation map $α$ has no polynomial-time selector. On an effective presentation, $α$ is therefore either computable outside FP or noncomputable. A separate certifiedactualisation protocol supplies polynomially bounded, polynomially verifiable traces with extensional unique projection. This is the constructive interface that turns historical actualisation into a total standard search relation; combined with the modal result, it places that relation in TFNP search \ FP search , from which a self-contained search argument yields P __ = N P . The result is a domain-relative conditional transfer theorem: it neither assumes polynomial non-anticipability in the definition of agency nor proves that human decision-making satisfies the bridge and certification premises.

Abstract: We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et al. (2006) by constructing a language in UREC whose complement does not belong to REC. Our lower-bound argument is inspired by the communication-complexity approach to unambiguous automata of Göös et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.

Abstract: A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$. We consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is a $Θ(k)$ quantum property tester for this problem. With Gopalan \etal's classical lower bound of $Ω(2^{k/2})$ for this task, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, improving the best known upper bound and thus showing the prior lower bound is essentially tight.

Abstract: A majority coloring (also called an unfriendly partition) of a graph $G$ is a vertex coloring of $G$ in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of $G$ is the majority chromatic number $μ(G)$. The majority coloring game, introduced by Bosek--Grytczuk--Jakóbczak (2019), is a two-player Maker--Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex. The least number of colors required for the first player to have a winning strategy on $G$ is the majority game chromatic number $μ_g(G)$. In contrast with the static case, Bosek et al. show that $μ_g(G)$ is unbounded in general, while $μ_g(G) \le \mathrm{col}_g(G)$, where $\mathrm{col}_g(G)$ is the game coloring number of $G$. It is known that for any acyclic graph $G$, $\mathrm{col}_g(G) \le 4$, and hence $μ_g(G) \le 4$. We improve this bound by showing that $μ_g(G) \le 3$ for any acyclic graph $G$ of maximum degree at most $4$. We also show that $μ_g(G) \le 2$ if $G$ is a path, a star, or a complete graph, improving results of Bosek et al. We also initiate the study of the computational complexity of the majority coloring game. We show that the pre-coloring extension problem for majority coloring on $G$ with a palette of $χ(G)$ colors is NP-complete, and that its game version is PSPACE-complete. Furthermore, the problem remains NP-complete, and its game version remains PSPACE-complete, even with a palette of $2$ colors.

Abstract: Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $σ_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(σ_{n,d})$, $\bs(σ_{n,d})$, and $C(σ_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(σ_{n,d})<\bs(σ_{n,d})<C(σ_{n,d}), \] and exhibit infinite families for which it holds.

Abstract: We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

Abstract: We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple accept nodes, we attain three results. 1. When $n \le w$, we show an SC derandomization with space $O(\log^2 n+\log w)$ and error $1/\text{poly}(nw)$. 2. When $n \ge w$, we show an SC derandomization with space $O(\log n \log w)$ and error $1/\text{poly}(w)$. 3. When $w=O(\log n)$, we show an optimal $O(\log n)$ space derandomization with error $1/\text{poly}(w)$. We further show that two super sets of BPL can be computed in SC. 1. For probabilistic logspace TMs with a two-way access random tape, we show that it can be approximated in SC if each entry of the random tape is accessed for at most a constant number of times. 2. For probabilistic logspace TMs with a polynomial size stack, i.e. probabilistic logspace Auxiliary Push-down Machines (AuxPDMs), we show that it can be approximated in SC if the timings of push/pop/idle stack operations do not depend on the randomness. The first model is the read-multiplicity model considered by Impagliazzo, Nisan, Wigderson (STOC'94), in which they show that their INW generator can fool such computations. For the second model, we indicate that it contains candidate languages separating BQL from BPL considered by Apers and Edenhofer (CCC'25).

Abstract: We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

Abstract: We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by $\overrightarrow{\mathrm{in}}_{P_3}(T)$ and $\overrightarrow{\mathrm{in}}_{P_3^*}(T)$ on a tournament $T$. For each $\overrightarrow{\mathcal{X}} \in \{\overrightarrow{P_3}, \overrightarrow{P_3^*}\}$, we show that determining whether $\overrightarrow{\mathrm{in}}_{\mathcal{X}}(T) \leq k$ is W[2]-complete when parameterized by $k$. Moreover, under ETH, we show that there is no parameterized algorithm for that problem with running time $f(k)\, n^{o(k)}$ on an $n$-vertex tournament, where $f$ is any computable function. For the $\overrightarrow{P_3}$-convexity, we also show that $\overrightarrow{\mathrm{in}}_{P_3}(T) = \mathcal{O}(\log n)$, which yields a simple quasi-polynomial $n^{\mathcal{O}(\log n)}$ brute-force algorithm. On the other hand, under ETH, we show that the problem is NP-intermediate, that is, it is neither NP-hard nor in P. For the $\overrightarrow{P_3^*}$-convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $\overrightarrow{\mathrm{in}}_{P_3^*}(T) = Θ(n)$. We conjecture that this problem is NP-complete.

Abstract: We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.

Abstract: We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|Γ|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(Γ)\le k \quad\text{from}\quad \operatorname{opt}(Γ)>k\cdot\frac{c\log n}{k^2\log\log n} \] is $\mathsf{W[1]}$-hard. Assuming the Exponential Time Hypothesis, there is also an absolute constant $\varepsilon>0$ for which no deterministic algorithm solves this gap problem in time $f(k)|Γ|^{\varepsilon k}$, for any computable function $f$. For every fixed $α>0$, both hardness results hold even when $n=O((\log m)^{1+α})$, with constants allowed to depend on $α$. For fixed $k$, the gap is within an $O_k(\log\log n)$ factor of the greedy algorithm's guarantee. Under the Strong Exponential Time Hypothesis, we further rule out $o(\log n/\log\log n)$ approximation in time $O(|Γ|^{k-δ})$ for every fixed $k\ge 2$ and $δ>0$. Thus a near-logarithmic hardness factor persists even when the exponent is reduced from exhaustive search by only a fixed constant. The constant in this SETH hardness factor may depend on $k$ and $δ$.

Abstract: We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).

Abstract: The forced colouring function of a graph gives the probability that a random assignment of colours to a random subset of vertices can be extended, by a simple local process called forcing, to give a proper colouring of the whole graph using the same set of available colours. This is a polynomial for each fixed number of colours, and was introduced as a subject for research on the general theory of graph polynomials. In this paper we establish its fundamental properties and give combinatorial interpretations of its derivatives at two particular points. We also prove that the problem of computing its value at any specific point in a certain interval is #P-hard.

Abstract: Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Our previous work determined its certificate complexity when $d$ is odd and when $d$ is a power of $2$, while even degrees with at least two nonzero binary digits were left open. We solve that open question and determine $C(σ_{n,d})$ for every $1\le d\le n$.

Abstract: We study a conditional model of ontological free will in which a pre-act state structures several coherent global continuations without intrinsically distinguishing one as the future actualisation. The topos-theoretic component is formalised by a choice sheaf and by the action of automorphisms preserving the pre-act data: the absence of a fixed point rules out any natural equivariant selection. An act changes an unpointed object into a pointed one and reduces its symmetry group to a stabiliser. Independently, a causal algorithmic incompressibility axiom imposes nearly maximal online description complexity on the actual choices. Uniformly observable post-act traces then allow their reconstruction. We prove a conditional transfer result: such traces must carry asymptotically all the singularisation information unavailable in the pre-act regime, and no uniform Turing predictor computes the choices from causal histories alone. The formalism proves neither that human beings satisfy the model nor a separation of P from NP; it identifies a boundary at which prediction concerns the existence of a computable function rather than its time complexity.

Abstract: We determine the exact time exponent of space-optimal reversible pebbling on chains as $1.331742379256310\ldots$. The growth rate of space-optimal reach exists as a limit and admits a variational formula. The same exponent governs complete computations at minimal space, uniformly in the chain length.

Abstract: We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.

Abstract: We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

Abstract: This project began as an attempt to prove that Medvedev logic is decidable with the help of generative AI systems. The author (as well as the generative AI systems, or at least they claim to be since I have asked them) was surprised by its eventual conclusion. We prove that Medvedev logic ML, the intermediate logic of finite problems, is Pi-01-complete under computable many-one reductions. Consequently, ML is not recursively enumerable, a fortiori undecidable, and admits no recursively enumerable sound and complete proof calculus. The proof connects the periodic domino problem with intuitionistic formulas through a shared intermediate structure that we call a Wang-Medvedev pair. Such a pair consists of a finite partially ordered set of roles together with demands. Demands define the interaction between roles. A realization labels nonempty subsets of a finite set with these roles, respecting the order and satisfying the demands. We associate a pair with each finite Wang system and show that it has a realization iff the system tiles a finite torus. We then construct an intuitionistic formula that fails on some finite Medvedev frame iff the same pair is realizable. Realizability thus provides the link between periodic tilings and the countermodels.

Abstract: Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$. In particular, $\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from $\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$. The same proof also shows $\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$. Additionally, we show that $\mathsf{PromiseBQP}$, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although $\mathsf{AWPP}$ and $\mathsf{APP}$ are low for $\mathsf{PP}$, a corresponding promise analogue would collapse the counting hierarchy as $\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$. This motivates the introduction of $\mathsf{PromisePostBQP^*}$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain $\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$.

Abstract: We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC$^0$ circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC$^0$ circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC$^0$ and AC$^0$.