Given a propositional proof system $P$, we may define a formula $\text{Prf}^P_s(F)$ which is satisfiable if and only if the formula $F$ has a length $\leq s$ refutation in $P$. These formulas have received much attention in recent years due to their fundamental nature --- if a powerful proof ... more >>>

For an arbitrary family of predicates $\mathcal{F} \subseteq \{0,1\}^{[q]^k}$ and any $\epsilon > 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\mathcal{F}})$ with at most $\beta+\epsilon$ fraction of satisfiable constraints from instances of with at least $\gamma-\epsilon$ fraction of satisfiable ... more >>>

We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems.

Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing ... more >>>

It is a long-standing open question whether the average-case hardness of NP implies the existence of a one-way function. The hypothetical world in which this does not hold is called Pessiland, which is the most pessimistic among Impagliazzo's five possible worlds. In this paper, we present the first "sharp" characterization ... more >>>

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ?s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin ... more >>>

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable ($WI$) arguments of knowledge. We establish that:

- Assuming that $NP\not\subseteq P/poly,$ the existence of a constant-round computational $WI$ argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist.

- Assuming that $NP\not\subseteq P^{Sam}/poly,$ there is no ... more >>>

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Point–Line Incidence problem is $\Theta(\log n)$. This confirms a conjecture of Cheung, Hatami, Hosseini, and Shirley (CCC 2023) that the complexity is super-constant, ... more >>>

The linear problem specified by an $n \times n$ matrix $M$ over a finite field is the problem of computing the product of $M$ and a given vector $x$. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit ... more >>>

We resolve the long-standing open problem of Boolean dynamic data structure hardness, proving an unconditional lower bound of $\Omega((\log n / \log\log n)^2)$ for the Multiphase Problem of Patrascu [STOC 2010] (instantiated with Inner Product over $\mathbb{F}_2$). This matches the celebrated barrier for weighted problems established by Larsen [STOC 2012] ... more >>>

A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH).
A ... more >>>

Can we use ``hardness vs randomness'' techniques to design low-space algorithms? This text surveys a sequence of recent works showing ways to do that.
These works designed algorithms for certified derandomization and for catalytic computation (which work unconditionally), derandomization and isolation algorithms from remarkably mild assumptions, and ``win-win'' pairs ... more >>>

The Tree Evaluation Problem (TreeEval) is a computational problem originally proposed as a candidate to prove a separation between complexity classes P and L. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that TreeEval can be solved using $O(\log n\log\log n)$ bits of space. ... more >>>

Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a longstanding open problem in algebraic complexity theory. All known multilinear lower bounds rely on the min-partition rank method, and the best bounds against ... more >>>

We establish tight connections between entanglement entropy and the approximation error in Trotter–Suzuki product formulas for Hamiltonian simulation. Product formulas remain the workhorse of quantum simulation on near-term devices, yet standard error analyses yield worst-case bounds that can vastly overestimate the resources required for structured problems.

For systems governed by ... more >>>

Recently, together with Kulikov, Mihajlin, and Smirnova (STACS 2026), we gave conditional constructions of functions with large monotone circuit complexity, matrices with high rigidity, and $3$-dimensional tensors of strongly superlinear rank.
In this note, I strengthen the rigidity construction under the same assumption and, as a direct consequence, immediately obtain ... more >>>

Determining the randomized (or distributional) communication complexity of disjointness is a central problem in communication complexity, having roots in the foundational work of Babai, Frankl, and Simon in the 1980s and culminating in the famous works of Kalyanasundaram-Schnitger and Razborov in 1992. However, the question of obtaining tight bounds for ... more >>>

Proving lower bounds against depth-$2$ linear threshold circuits (a.k.a. $THR \circ THR$) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for $THR \circ THR$ only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and ... more >>>

A central goal in average-case complexity is to understand how average-case hardness can be amplified to near-optimal hardness. Classical results such as Yao’s XOR lemma establish this principle for Boolean functions, but these techniques typically apply only to artificially constructed functions, rather than to natural computational problems. In this work, ... more >>>

Zero-knowledge codes, introduced by Decatur, Goldreich, and Ron (ePrint 1997), are error-correcting codes in which few codeword symbols reveal no information about the encoded message, and have been extensively used in cryptographic constructions. Quantum CSS codes, introduced by Calderbank and Shor (Phys. Rev. A 1996) and Steane (Royal Society A ... more >>>

We study sparse polynomials with bounded individual degree and the class of their factors. In particular we obtain the following algorithmic and structural results:

1. A deterministic polynomial-time algorithm for finding all the sparse divisors of a sparse polynomial with bounded individual degree. As part of this, we establish ... more >>>

A symbolic determinant under rank-one restriction computes a polynomial of the form $\det(A_0 + A_1y_1 + \ldots + A_ny_n)$, where $A_0, A_1, \ldots, A_n$ are square matrices over a field $\mathbb{F}$ and $\rank(A_i) = 1$ for each $i \in [n]$. This class of polynomials has been studied extensively, since the ... more >>>

We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the ... more >>>

I give an alternative proof of the xor lemma which may provide a simple explanation of why xor-ing decreases correlation.

Error-correcting codes are a method for representing data, so that one can recover the original information even if some parts of it were corrupted. The basic idea, which dates back to the revolutionary work of Shannon and Hamming about a century ago, is to encode the data into a ... more >>>

In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we introduce a problem called nested collision finding, and show ... more >>>

We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices ... more >>>

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form
\[
\Sigma^{[r]}\!\wedge^{[d]}\!\Sigma^{[s]}\!\Pi^{[\delta]}.
\]
This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is ... more >>>

We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-knowledge errors (denoted $\epsilon_c$, $\epsilon_s$, and $\epsilon_z$, respectively) that might not be negligible. Under the assumption that there are worst-case hard languages in NP, we show ... more >>>

We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n), where n>=2 is constant. For dimension N and error ?, the number of quantum gates in our circuits is polynomial in log(N) and log(1/?). Our construction relies on the Jordan-Schwinger representation, which allows us to realize ... more >>>

Guo, Saxena, and Sinhababu (TOC'18, CCC'18) defined a natural, approximative analog of the polynomial system satisfiability problem, which they called approximate polynomial satisfiability (APS). They proved algebraic and geometric properties of it and showed an NP-hardness lower bound and a PSPACE upper bound for it. They further established how the ... more >>>

The complexity of bilinear maps (equivalently, of $3$-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for $3$-mode tensors, this correspondence breaks down for $d \geq 4$ modes. As a result, the complexity of $d$-mode tensors for ... more >>>

We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in ... more >>>

Unlike in TFNP, for which there is an abundance of problems capturing natural existence principles which are incomparable (in the black-box setting), Kleinberg et al. [KKMP21] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TF$\Sigma_2$) reduce to the ... more >>>

We give new algorithms for tree evaluation (S. Cook et. al. TOCT 2012) in the catalytic-computing model (Buhrman et. al. STOC 2014). Two existing approaches aim to solve tree evaluation in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in ... more >>>

Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all $n$-bit strings $x$ and $y$, $K(x,y) = K(y) + K(x \mid y)$ up to an additive error of $O(\log n)$ [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related ... more >>>

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (QMA) and the class of languages that can be verified with a classical proof (QCMA). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof ... more >>>

We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, ... more >>>

We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every resolution-over-parities (Res($\oplus$)) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) ... more >>>

The hardness vs. randomness paradigm aims to construct pseudorandom generators (PRGs) based on complexity theoretic hardness assumptions. A seminal result in this area is a PRG construction by \cite{NW,IW97}.
A sequence of works \cite{KvM,SU01,Umans02,SU05} generalized the result of \cite{NW,IW97} to nondeterministic circuits. More specifically, they showed that if $\E=\DTIME(2^{O(n)})$ requires ... more >>>

Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola’s celebrated construction (CC 2009) gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large ... more >>>

In this work, we propose a new bounded arithmetic theory, denoted $\mathbf{APX}_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $\mathbf{APX}_1$ is strictly weaker than previously proposed frameworks, such as the theory $\mathbf{APC}_1$ introduced in the seminal work of Je?ábek ... more >>>

We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the ... more >>>

A major open problem at the interface of quantum computing and communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they are not. In a seminal work, Razborov (2002) resolved this question for AND-functions of ... more >>>

We study systems of linear equations modulo two in $n$ variables
with three variables in each equation. We assume that the system has
a solution with $pn$ variables taking the value 1 for some value
$00$ it is hard to find a solution
of the same weight that satisfies at ... more >>>

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general model for multi-block randomness sources with causal correlations.
A SHEDAG source is defined over a directed acyclic graph (DAG) $G$ whose nodes output $n$-bit blocks. Blocks output by honest nodes are independent (by ... more >>>

This paper explores the previously studied measure called block number of Boolean functions, that counts the maximum possible number of minimal sensitive blocks for any input. We present close to tight upper bounds on the block number in terms of the function’s sensitivity and the allowed block size, improving previous ... more >>>

In this short expository note, we provide an introduction to a distribution testing (and, more generally, indistinguishability) lower bound method based on moment-matching via polynomials. This method, which underlies several of the tight lower bounds on estimating symmetric properties, had for many years appeared mysterious and near-magical to the ... more >>>

Proving super-linear lower bounds on the size of circuits computing explicit linear functions $A:{\mathbb {F}}^n \to {\mathbb {F}}^n$ is a fundamental long-standing open problem in circuit complexity. We focus on the case where ${\mathbb {F}}$ is a finite field. The circuit can be either a Boolean circuit or an arithmetic ... more >>>

Res($\oplus$) is the simplest fragment of $\text{AC}^0[2]\text{-Frege}$ for which no super-polynomial lower bounds on the size of proofs are known. Bhattacharya and Chattopadhyay [BC25] recently proved lower bounds of the form $\exp(\tilde\Omega(N^{\varepsilon}))$ on the size of Res($\oplus$) proofs whose depth is upper bounded by $O(N^{2 - \varepsilon})$, where $N$ is ... more >>>

We prove that relative to a random oracle answering $O(\log n)$-bit queries, there exists a function computable in $O(n)$ time by a random-access machine (RAM) but requiring $n^2/polylog(n)$ time by any multitape Turing machine. This provides strong evidence that simulating RAMs on multitape Turing machines inherently incurs a nearly quadratic ... more >>>

We prove that $\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.

We present a new, simplified proof that the complexity class BPP is contained in the Polynomial Hierarchy (PH), using $k$-wise independent hashing as the main tool. We further extend this approach to recover several other previously known inclusions between complexity classes. Our techniques are inspired by the work of Bellare, ... more >>>

Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $\chi$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $\chi \circ g$ on ${\mathbb F}_q$, with up to a ... more >>>

In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). Separation theorems are well-studied in the context of classical complexity theory, Boolean circuit complexity, and algebraic complexity.

In an important work ... more >>>

It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mABPs). The best lower bounds in this setting are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the “min-partition rank” method introduced by ... more >>>