Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to ... more >>>

We study the query complexity of finding a Tarski fixed point over $[n]^k$. Previous work has left a large gap between $\smash{{\Omega}(\log^2 n)}$ and $\smash{\log^{O(k)}n}$. We show that both of the previous upper and lower bounds were far from tight: for every $k\geq 3$,
$$
\Omega\left((\log n)^{\frac{1}{2}\lceil \log k\rceil}\right)\le
more >>>

The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension ... more >>>

We prove that the scaling window of random $k$-SAT has width $O(n^{1/2+1/k})$, a polynomial improvement over our previous bound of $O(n/\log n)$. Combined with a result of Abbe and Montanari, this establishes the satisfiability conjecture for every fixed $k\geq 3$.

We study cryptographic primitives that are both locally computable (i.e., in $\mathrm{NC}^0$) and exponentially secure. For pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs), we further require linear stretch and linear compression, respectively, which is essentially the best one can hope for in this setting. Such primitives simultaneously achieve ... more >>>

Testing whether a bounded-degree $n$-vertex graph is bipartite or far from bipartite requires $\widetilde\Theta(\sqrt n)$ queries (Goldreich--Ron, Combinatorica'99, Algorithmica'02). An interactive proof of proximity (IPP) is a hybrid model of property testing and interactive proofs: the verifier faces the same task with the same query access, but it now interacts ... more >>>

We prove that every language in $\mathrm{P}^{\# \mathrm{P}}$ can be decided by a bounded-error randomized algorithm that uses only $O(\log n)$ bits of work space. The algorithm is guaranteed to halt for every input and every setting of the random tape. However, there is a catch: the algorithm uses a ... more >>>

We construct an explicit hitting set generator (HSG) for ordered read-once branching programs of width 4. For every length $n$ and every $\varepsilon \in (0,1)$, every width-4 length-$n$ program that accepts more than an $\varepsilon$ fraction of its inputs accepts at least one output of the generator, and the seed ... more >>>

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$.
Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have:
$$
agree(F,L) ... more >>>

We explore new directions in simulating complex computations with low space, building on the work of Williams [STOC'25] and Cook-Mertz [STOC'24, SICOMP'25]. We define and study a strengthened version of the parallel external memory model, in which there are $P$ processors each with private internal memory $M$, all of which ... more >>>

We show that random linear codes possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating applications follow:

First, random linear codes ... more >>>

We prove that Parity requires $2^{n^{\Omega(1)}}$ size De Morgan circuits of constant depth using a new method which is completely “top-down” in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds ... more >>>

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or ... more >>>

We revisit the semantic size-cost-capacity technique (Beyersdorff, Blinkhorn & Hinde, 2019) for proof-size lower bounds in proof systems for quantified Boolean formulas (QBF). While the original technique is only applicable to weak proof systems with bounded capacity, we present a fine-grained generalisation of this technique that allows us to attack ... more >>>

We prove an $\Omega(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, via an AI-assisted and AI-written proof. Assuming its correctness, this was the first super-linear lower bound ... more >>>

We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits.

The main ... more >>>

Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In ... more >>>

We study interactive proofs of proximity (IPP) for model evaluation: a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation is shaped by the constraints of practical evaluation: it separates sampling the input distribution ... more >>>

A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection ``too much’’. Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding and recovery, to derandomizing algorithms.

We ... more >>>

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between.
We first investigate ... more >>>

We consider the problem of deterministically factoring integers provided with oracle access to important number-theoretic functions such as Euler's Totient function - phi(.) and Carmichael's Lambda function - lambda(.).
We focus on Carmichael numbers - also known as Fermat pseudoprimes. In particular, we obtain the following results:

1. Let N ... more >>>

Given a prime $p$, an integer $0\le n\le p-1$, and a divisor $q\mid(1+p+p^2)$, we compute $n!\bmod p$ in expected bit complexity $\widetilde{O}\left(q^c+\frac{\sqrt{p}}{q^{1/4}}\right)$ for some absolute constant $c\ge1$. More generally, the construction applies when $q\mid\Phi_r(p)$, where $\Phi_r$ is the $r$-th cyclotomic polynomial and $r$ is any fixed odd prime power. Combining ... more >>>

We construct improved pseudorandom generators for read-$k$ oblivious branching programs with a known reading sequence.
For width-$w$ branching programs over $n$ variables, and designated error $\varepsilon$, our generator has seed length
$$\mathcal{O}\left(n^{1-\frac{1}{2k-1}}\log n\left(k\log w+\log\frac{n}{\varepsilon}\right)\right).$$
This improves upon the previous state-of-the-art due to Gurjar and Volk (ACM ToCT 2020), that has ... more >>>

We study interactive proofs when the prover and the verifier access the same underlying data through independent noisy views. The noise is \emph{persistent} for each party: each location is corrupted once, and repeated queries to the same location return the same corrupted value. We introduce two models in this setting: ... more >>>

We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over $\mathbb F_2$ and for alternating circuits with parity ... more >>>

We introduce a variant of a polynomial family called $\TQBFfamily$ obtained from `arithmetization' of the popular $\PSPACE$-complete problem - $\TQBF$. This polynomial family has several nice characteristics such as: $\TQBFfamily \in \VPSPACE_b$, where $\VPSPACEb$ is the `bounded' algebraic version of $\PSPACE$, it is \emph{self-testable}, it captures the computational power of ... more >>>

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions $f$
which counts the number of bits of an input that need to be known in order for the value of the
function to be determined. A certificate can be viewed as a partial assignment, or a ... more >>>

The slice rank method gives exponential bounds for sets with no three-term arithmetic progression in finite vector spaces of odd characteristic and for three-sunflower-free families of subsets of a fixed ground set. We show that for $k\ge4$, every tensor that is nonzero exactly on the $k$-term arithmetic progression relation or ... more >>>

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas (2026) about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick (2024) for constructing quantum LTCs, instantiated with ... more >>>

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the ... more >>>

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders.
In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev.
more >>>

Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and ... more >>>

Local LCL properties [Levi, Mosheiff, and Shagrithaya (LMS), FOCS 2025] give a language to express a broad range of linear properties of codes. Subspace design [Guruswami and Xing, 2013] is an elegant property about the linear structure of codes, and it governs important code behavior. In this note, we show ... more >>>

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies
\[
\omega^*(G^{\otimes n})
\le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n))
\]
for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen ... more >>>

Let f be a product of D generic linear forms in m variables over a field of characteristic 0, and for integers k, l >= 0 let Gamma_{k,l}(f) = dim S_l * partial^k f be its shifted partial derivative measure, the complexity measure behind the known lower bounds for homogeneous ... more >>>

We provide a digest of the paper of Fei and Rubinfeld (arXiv 2026), which provides an alternative analysis of the Bipartite Tester of Goldreich and Ron ({\em Combinatorica}, 1999), which operates in the bounded-degree graph model.
Loosely speaking, on input an $n$-vertex graph $G$, the tester selects few vertices, ... more >>>

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a ... more >>>

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 ... more >>>

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon ... more >>>

An outstanding open problem asks if there exists a boolean matrix with unbounded sign-rank, but bounded randomised communication complexity. We make progress towards this question by proving lower bounds against real linear sketches (a model weaker than sign-rank): Alice and Bob send few linear measurements to a referee, who makes ... more >>>

Cryptographic combiners take $n$ candidate schemes for some primitive $P$, and realize it securely provided that at least $k$ candidates are secure. Intuitively, we expect that if we plug $n$ independent instances of a $\delta$-weak candidate for $P$ into the combiner, assuming $\delta \ll (n-k)/n$, security should be amplified and ... more >>>

The permanent and mixed discriminant of positive matrices are classic problems for which we do not expect an efficient algorithm for exact computation. Thus much work has been done to understand how well we can bound and approximately compute these quantities. One line of research in this area begins with ... more >>>

In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{poly}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. Inspired by Gavinsky’s recent work (arXiv:2608.18784), our construction combines the ... more >>>

Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman–Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose ... more >>>

We give an elementary proof of the Komlos conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\|v_i\|_2\le1$ admit signs $\varepsilon_i\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i v_i\|_\infty\le36$. The proof uses only elementary combinatorial and probabilistic arguments and basic calculus.

For every fixed $k\ge3$, we construct an explicit total Boolean function in the $k$-player number-on-forehead model with public-coin randomized communication complexity $O_k(1)$ and nondeterministic communication complexity $\Omega_k(n)$, where $n$ is the number of bits on each forehead. This extends the explicit three-player separations of Kelley, Lovett, and Meka (STOC 2024) ... more >>>

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/\text{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the ... more >>>

Given any fixed constant $0<\varepsilon<1$ and a matrix space
$\mathcal{B}=\langle B_1,\ldots,B_m\rangle\le\mathbb{Q}^{n\times n}$,
we give a deterministic $NC^3$ algorithm that outputs a matrix \(A\in\mathcal{B}\) such that $rank(A)\geq (1-\varepsilon) crk(\mathcal{B})$,
where $crk(\mathcal{B})$ denotes the maximum rank of a matrix in $\mathcal{B}$. This complements the recent breakthrough of Chatterjee, Ghosh, Gurjar, Raj, and ... more >>>

Braverman, Rao, Raz, and Yehudayoff (SICOMP 2014) showed that there is an explicit pseudorandom generator (PRG) that fools standard-order regular read-once branching programs (ROBPs) with seed length
$$
O(\log n \cdot \log \log n + \log n \cdot \log(wd/\epsilon)),
$$
where $w$ is the width of ... more >>>

In this paper we show that iterated multiplication over a group has constant-communication protocols if and only if the
group is nilpotent, thus giving a new characterization of nilpotency based on communication
complexity.

Communication complexity studies how much information must be exchanged to solve a problem whose input is split among several parties. The classical setting deals with Boolean inputs split between two parties. We study an algebraic variant, where the inputs are vectors over a field $\mathbb{F} \in \{\mathbb{R}, \mathbb{C}\}$. Alice and ... more >>>

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$.

1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for all ... more >>>

We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output equal to $b$ ... more >>>

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 NP-hard to distinguish between the case that val$(\Psi)=1$ and the case that val$(\Psi)\leq \delta$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, CCC ... more >>>

We use this framework to construct HSGs for read-once CNFs and read-once CNFs with parities. For formulas on $n$ variables with density at least $\varepsilon$, our generators use $O(\log(n/\varepsilon))$ seed bits. This bound is optimal up to a constant factor. Applying the hitting reduction of Gopalan, Meka, Reingold, Trevisan, and ... more >>>

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about ... more >>>

We introduce a new family of *parallel* time-bounded Kolmogorov complexity measures ($KP^t$).
A string $w$ has low $KP^t$ complexity if any individual bit of $w$ can be decompressed from a "short" description using "few" parallel processors within at most $t$ steps.

The definition of $KP^t$ uses Parallel Random Access Machines ... more >>>

We study batch verification in QMA query and communication complexity, where the goal is to understand how the resources needed to verify $m$ copies of a Boolean function $f$ depend on $m$. We give a general technique for proving lower bounds on the witness-query tradeoff needed to batch verify a ... more >>>

We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the $\QMA$-complete Local Hamiltonian problem \cite{KSV02}. For the $\beta$-gapped, frustration-free case, \citet{BBT06} showed that the problem is $\MA$-complete when $\beta= \frac{1}{\poly(n)}$. \citet{AG19} derandomized this algorithm and proved membership in $\NP$ for constant gap $\beta = ... more >>>

In this work we give a randomized blackbox polynomial identity testing (PIT) algorithm for constant-depth homogeneous noncommutative circuits, with poly-logarithmic time complexity in the circuit size. In fact, we show that the polynomial computable by such a depth-$(\Delta-1)$ circuit of size $s$ cannot be a polynomial identity for the $O(\log ... more >>>

We present a methodology for constructing interactive proof systems.
This methodology, which is implicit in prior works, consists of reducing the original claim to an iteratively generated sequence of claims such that each claim is (interactively) generated based on the prior claim.
Viewing each of these interactive generation ... more >>>

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetilde{\Theta}(M)$, ... more >>>

The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are the fundamental algorithmic questions in the geometry of numbers. In the past two decades, their algorithmic complexity has been studied quite extensively due to their connection with lattice based cryptosystems. In this paper, we study these problems in ... more >>>

We give a unified hidden-derivative framework for list decoding and mutual correlated agreement of ordinary Reed--Solomon codes over prime fields, on arbitrary prescribed evaluation sets. For every fixed slack $\gamma>0$, every sufficiently large block length $n$, every prime $q\ge n$, and every dimension $1\le k\le(1-\gamma)n$, a deterministic algorithm finds all ... more >>>

Guo and Wang gave a deterministic polynomial-time black-box identity test for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of arbitrary characteristic, for constant $\delta$, assuming that one product gate is squarefree. This note communicates an observation suggested by a large language model: the squarefreeness assumption can be removed by combining the normalization argument ... more >>>

Kane and Williams proved average-case wire lower bounds at the $n^{5/2}/\mathrm{polylog}, n$ scale for an explicit function against depth-two linear-threshold circuits. We prove an almost-everywhere near-cubic wire lower bound for a language in $\mathrm{E}^{\mathrm{NP}}$. For every fixed $c>0$, there is one language $F_c$ and positive constants $b_{S,c}$ and $b_{T,c}$ such ... more >>>

Grochow and Pitassi (2018) introduced the algebraic proof system, the Ideal Proof System (IPS), which connects algebraic circuit complexity to propositional proof complexity. They showed that propositional proof systems such as Extended Frege (Frege) are equivalent to circuit IPS (formula IPS) if the correctness of PIT for circuits (formulas) can ... more >>>

In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of ... more >>>

We provide a deterministic polynomial-time list decoding algorithm for Reed-Solomon codes over prime fields that approaches list decoding capacity on every evaluation set in the low (constant) rate regime.

This work studies super-Ramanujan graphs: \(d\)-regular graphs whose spectral expansion lies strictly below the Ramanujan threshold \(2\sqrt{d-1}\). Although this threshold is asymptotically optimal for fixed \(d\) as \(n\) tends to infinity, it leaves open the finer question of how small the spectral expansion can be as a joint function of ... more >>>

The recent paper \cite{chatterjee2026bipartite} showed that deciding whether a bipartite graph has a perfect matching can be reduced to deciding whether a determinant, whose value may be assigned to any sufficiently large field $\mathbb{F}$, equals to zero. In the second part of their work, \cite{chatterjee2026bipartite} also generalized the algebraic method ... more >>>

In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment ... more >>>

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC ... more >>>

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample:
a pair of items in the wrong order. The goal is to identify ... more >>>

We prove exponential lower bounds for $k$-DNF resolution on random $3$-CNF formulas throughout the range $k=O(\sqrt{\log n})$ at every constant clause density above the elementary first-moment bound for unsatisfiability. For random $3$-CNFs this improves Alekhnovich's range $k=O(\sqrt{\log n/\log\log n})$, and matches the $O(\sqrt{\log n})$ range obtained by Sofronova and Sokolov ... more >>>

In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best known approximation ratio is $2.466$, whereas the currently strongest upper bound on the approximation guarantee of the maximum-overlap ... more >>>

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs).

We prove an upper bound of $2^{O\left(\sqrt{n\log n \log ... more >>>

We prove an exponential separation between zero-sided-error randomized and two-sided-error pseudodeterministic communication complexities of partial boolean functions. This qualitatively improves and simplifies the proof of the separation by Göös, Harms, Riazanov, Sofronova, Sokolov, and Yuan (STOC 2026), which had a two-sided-error randomized upper bound. Then, we generalize our technique to ... more >>>

We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.

We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $\gamma$ admits a signed decomposition into at most $2^{O(\gamma^4)}$ elementary pieces. In ... more >>>

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1\}^n_{n/2} \to G$ where $\{0,1\}^n_k$ denotes the set of vectors in $\{0,1\}^n$ of Hamming weight $k$ and $G$ is an Abelian group (not necessarily finite), the low-degree ... more >>>

We give quantitative bounds on the sparsity of a real polynomial with non-negative coefficients vanishing on a slice of the Boolean cube $\{\pm1\}^n$. We obtain similar bounds on the dimension of real orthogonal representations of (the complement of) Johnson-type graphs. The estimates are related to the classical problem about ... more >>>

The quantum analogue of the PCP theorem for QMA remains wide open. A central obstacle is the local indistinguishability of quantum codes: every sufficiently small view of an encoded witness is independent of the witness, seemingly preventing a local verifier from distinguishing YES from NO instances. One approach to this ... more >>>

For a prime $p\geq 3$, a somewhat restricted $3$-AP in $\mathbb{F}_p^n$ is a triplet $(x,x+a,x+2a)$, where $x\in\mathbb{F}_p^n$ and $a\in \{0,1,2\}^n$. We prove a counting lemma for somewhat restricted $3$-APs in dense sets in $\mathbb{F}_p^n$. More precisely, we prove that for all $\alpha>0$, there exists $\beta>0$, such that for sufficiently large ... more >>>

We give a randomized algorithmic version of the Balog--Szemer\'edi--Gowers theorem for sets of integers. Let $A\subseteq[N]$ have size $n:=|A|\geq2$, let $1\leq K\leq n$, and suppose that its additive energy satisfies $E(A)\geq n^3/K$. Reiher and Schoen proved existentially that, for every fixed $\epsilon \in (0,1/2)$, there is a subset $A'\subseteq A$ ... more >>>

The line--versus--point test asks the following local-to-global question. Suppose a function $f\colon\mathbb{F}_q^m\to\mathbb{F}_q$ is, on average over a random affine line $L$, correlated with some degree-$d$ polynomial on $L$. Must $f$ then be globally correlated with a single multivariate polynomial of degree at most $d$? Beyond being a natural combinatorial question, ... more >>>

A secret-sharing scheme allows a dealer to distribute a secret $s$ among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about $s$. Families of authorized sets are called access structures, and a scheme is called linear if ... more >>>

We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value $k\geq 3$, the window of random $k$-SAT is $O(n/\log n)$, improving the Friedgut-Bourgain bound of $O(n/\log\log n)$. We also show that random signed Not-All-Equal-$k$-SAT and hypergraph non-two-colourability ... more >>>

We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira. For hereditary graph properties, we prove that one-sided testability is quantitatively equivalent to the existence of suitable hypergraph containers, a central and widely used tool in ... more >>>

A Boolean-weighted graph is a finite graph whose edges carry DNF formulas over a common variable set. This paper studies two isomorphism problems on such graphs, distinguished by whether the per-edge condition requires the matched edge labels to be syntactically DNF-isomorphic (BWG-ISO) or syntactically DNF non-isomorphic (BWG-NI), each over a ... more >>>

We study shortest paths in directed graphs whose edge weights are of the form $$wt(e) = a_{e,1} \lambda_1 + a_{e,2} \lambda_2 + a_{e,3} \lambda_3 + \cdots + a_{e,d} \lambda_d + a_{e,d+1}.$$
Here, each $a_{e,i}\in\mathbb{R}$ is a fixed constant for each edge $e$, whereas each $\lambda_i$ is a shared variable ... more >>>

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m\ge 2$ is a
pair of ordered lists $U=(u_1,\ldots,u_K)$ and $V=(v_1,\ldots,v_K)$ with
$u_i,v_j\in \Z_m^n$ such that $\langle u_i,v_i\rangle=0 \pmod m$ for every
$i\in[K]$, while $\langle u_i,v_j\rangle\ne 0 \pmod m$ for every $i\ne j$. It
is called $r$-restricted if the set of ... more >>>

We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $\delta$, then ... more >>>

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth ... more >>>

Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a high dimensional ambient space whose image is contained in no subvariety of low complexity. Here, complexity is prescribed in terms of the ... more >>>

In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code.
More formally, given a code $C \subseteq \Sigma^n$ and input lists $S_1, \hdots, S_n \subseteq \Sigma$ of size at most $\ell$, list recoverability requires that there are at most $L$ codewords ... more >>>

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum ... more >>>

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem ... more >>>

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits ... more >>>

Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has ... more >>>

We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb R^n$ ... more >>>

A branching program is a labeled directed graph that, on each input $x$, induces an $s$-$t$ connectivity instance. Nondeterministic branching programs (NBPs) accept an input if there exists an accepting path, whereas parity branching programs ($\oplus$BPs) accept if the number of accepting paths is odd. Wigderson (Structure in Complexity Theory ... more >>>

We study pseudorandom bit generators for Boolean linear sums modulo a fixed
integer $M$. A distribution $X\in\{0,1\}^n$ $\varepsilon$-fools these tests if, for
every $a\in\mathbb{Z}_M^n$, the distribution of
\[
\sum_{i=1}^n a_iX_i \pmod M
\]
is $\varepsilon$-close in statistical distance to the corresponding distribution
under independent uniform bits.

Lovett, Reingold, Trevisan, ... more >>>

We prove new exponential monotone circuit lower bounds for detecting perfect matchings. We show that $\exp(\widetilde{\Omega}(n^{1/2}))$ gates are required to detect bipartite perfect matchings in $n$-vertex graphs. Our lower bounds are based on a new spread matching lemma.

We show the following hardness results for monotone learning and approximation of monotone circuit size:

1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires time $n^{\Omega(\log n)}$ to PAC-learn monotone formulas with $n$ input bits and size $s(n) = n$ by monotone circuits of size $n^{(\log n)^{1-\epsilon}}$, for every $\epsilon ... more >>>

We prove that every De Morgan formula with $n$ leaves has a pointwise $1/3$-approximating real polynomial of degree $O(\sqrt n)$ and coefficient $\ell_1$-norm $2^{O(\sqrt n)}$. The standard approximate-degree theorem for formulas gives the same degree bound, but only yields the weaker coefficient estimate $2^{O(\sqrt n\log n)}$.

Our proof constructs, for ... more >>>

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, ... more >>>

We describe a method that lifts an arbitrary polynomial $f$ with sparsity $s$ to a polynomial that requires a read-once oblivious algebraic program of width $s$ for every variable order. To do so, we introduce a technique for constructing a gadget based on erasure codes over finite fields, where each ... more >>>

For a directed graph $G = (V, E)$, we say that a weight function $\rho \colon E \to [M]$ is *min-isolating* if the minimum-weight path from $u$ to $v$ is unique for each pair of vertices $u, v \in V$ such that $v$ is reachable from $u$. If we could ... more >>>

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length
$$
O\left((\log w+\log(1/\varepsilon))\cdot \log n\right).
$$
This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the ... more >>>

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A straightforward brute-force algorithm for HOM has running time $O(2^{n \log h})$ and it is known that, under ETH, there are ... more >>>

The Orthogonal Vectors Problem (OV$_{n,d}$) takes as input two sets $A,B$ each containing $n$ $d$-dimensional Boolean vectors, and outputs $1$ if and only if there exists $a \in A$ and $b \in B$ such that $a$ and $b$ are orthogonal. The OV conjecture states that for every $\varepsilon > 0$, ... more >>>

For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in ... more >>>

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the ... more >>>

We prove a near-maximum ($2^n / n$) circuit lower bound for the complexity class $\mathrm{E}^{\mathrm{prMA}}/_1$, corresponding to exponential time with access to a promise-$\mathrm{MA}$ oracle and one bit of advice. Our proof incorporates the iterative win-win paradigm (Chen--Lu--Oliveira--Ren--Santhanam, FOCS'23), the reduction from the Range Avoidance problem to circuit lower bounds ... more >>>

We study one-way quantum communication lower bounds for search problems.Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of ... more >>>

We explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by $CC^0$ circuits - the class of constant-depth polynomial size circuits containing $MOD_m$ gates for some natural number $m$.
Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach ... more >>>

We prove an $\tilde{\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tilde{\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.

This paper studies the isomorphism problem for Boolean formulas and places it precisely in the polynomial hierarchy. Two of its results are new. The first sharpens the relationship between Boolean and graph isomorphism. Chang's reduction shows only that the unrestricted Boolean isomorphism problem is GI-hard, in one direction; restricting both ... more >>>

Two-server Private Information Retrieval achieves arbitrarily small polynomial communication, but relies on a strong non-collusion assumption that
is difficult to justify in practice.

We introduce a new variant of two-server PIR in which one server acts as a standard *compute* server, while the other is a restricted *retrieval-only* server. The ... more >>>

We continue the study of half-duplex communication complexity, a model introduced in [HIMS18] and further studied in [DISSU21], in which each player can either send a bit or listen in each round, similarly to communication over a walkie-talkie.
We prove improved upper bounds for the Inner Product function in the ... more >>>

We show that one-way functions suffice for constructing very efficient argument systems for proving the correctness of bounded-space computations. Taking $\kappa$ to be a cryptographic security parameter and $n$ to be the input length, our argument system applies to general computations running in time $T$ and space $S$. The protocol ... more >>>

A robust combiner for a cryptographic primitive $P$ takes multiple candidate constructions of $P$ and produces a secure construction of $P$ provided that sufficiently many of the candidates are secure. A closely related notion is that of a security amplifier, where given a weakly secure construction of $P$, we aim ... more >>>

We introduce a new family of propositional proof systems, denoted $\langle EF, R \rangle$, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in $\langle EF, R \rangle$ is given by a polynomial-time mapping reduction from the false-clause search problem ${\mathrm{Search}}_F$ to $R$, combined ... more >>>

We design a deterministic algorithm that, given blackbox access to the product $f=\prod_{i=1}^{\ell}{h_i}$ of $\ell$ irreducible $s$-sparse $n$-variate polynomials of bounded individual degree $d$, over fields of characteristic zero, and more generally over fields of sufficiently large positive characteristic, recovers the $h_i$'s and their multiplicities in time $\mathrm{poly}(n,(s\ell d)^d)$. ... more >>>

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, ... more >>>

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We ... more >>>

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results.
1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains ... more >>>

We study depth-$5$ algebraic circuits over small finite fields with restricted fan-in of the top product gates. We show that there exists an explicit degree-$d$ polynomial $P(\mathbf{x})$ such that any $\Sigma \Pi^{[\mathrm{poly(d)}]} \Sigma \Pi \Sigma$ circuit, computing $P(\mathbf{x})$, over a small finite field, requires size $2^{\Omega(\sqrt{d})}$. Our work builds upon ... more >>>

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{\Omega(\log k)}$ queries.

The ... more >>>

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof ... more >>>

For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous #SAT problem. Recently, important proof systems for QBFs and #SAT have been studied. By extending the ideas from both fields, we ... more >>>

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based ... more >>>

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior ... more >>>

Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems.

Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under standard derandomization (prBPP = prP) and cryptographic assumptions (LWE and SXDH), ... more >>>

The symmetric determinantal complexity $\sdc(f)$ of a polynomial $f$ is the
least $m$ such that $f=\Det(M)$ for an $m\times m$ symmetric matrix $M$ of
affine-linear forms. We prove, over $\CC$, that
\[
\sdc\!\left(\sum_{i=1}^n x_i^n\right)
\ge \left(\frac{1}{2e}-o(1)\right)n^2 .
\]
The result is a symmetric companion to the author's non-symmetric ... more >>>

I refute the 1995 dream XOR lemma conjecture by Goldreich, Nisan, and Wigderson. I also give a counterexample to the XOR lemma for low-degree polynomials.

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has ... more >>>

Weighted pseudorandom generators (wPRGs) were suggested by Braverman, Cohen, and Garg (STOC, 2018) as a relaxation of pseudorandom generator (PRG) used for derandomization.
We present proofs of several observations regarding wPRGs, where some of these observations are well known.

In this paper, we give a one-pass quantum streaming algorithm for Max-$k$SAT that uses $\operatorname{polylog}(n)$ space and achieves a $0.7172$-approximation on instances with $n$ variables. In contrast, prior work by Chou, Golovnev, and Velusamy (FOCS 2020) implies that achieving an approximation ratio better than $\sqrt{2}/2 \approx 0.7071$ for Max-$k$SAT requires ... more >>>

We show that several meta-complexity problems are NP-hard under randomized polynomial-time (half-Levin) reductions, and provably cannot be NP-hard under randomized Levin reductions, under the assumptions that
(cryptography): there exists a subexponentially-secure indistinguishability obfuscator in the sense of Barak et al. (JACM 2012), and
(proof complexity): there are no ... more >>>

Raz (2009) proved that multilinear formulas computing the determinant of a generic $n \times n$ matrix require size $n^{\Omega(\log n)}$. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. In pursuit of this question, we prove the existence of $n ... more >>>

We study the problem of constructing randomness extractors for samplable sources, introduced by Trevisan and Vadhan (FOCS 2000), a natural computational model of imperfect randomness, where the source $\mathbb{X}$ (on $n$ bits) is generated by a polynomial-size circuit. They showed how to extract from sources with min-entropy $(1-\alpha)n$ (for small ... more >>>

The work of Rothblum, Vadhan, and Wigderson ({\em STOC}, 2013) is pivotal to the study of interactive proofs of proximity (IPPs).
We present the main contents of their work, while clarify a few (conceptual) aspects.
Specifically, starting with the definition of IPP systems, our main focus is on ... more >>>

In this work, we study the space complexity of sketching the intersection profile of a distribution $D$ on $2^{[n]}$. Specifically, we seek a succinct data structure that, for any query set $S \subseteq [n]$, approximates the quantity $\Pr_{T \sim D}[T \cap S \neq \emptyset]$ to within a small constant additive ... more >>>

Let $S\subseteq {\mathbb F}_2^u$ have size $n=2^\ell$, and let $h:{\mathbb F}_2^u\to {\mathbb F}_2^\ell$ be a uniformly random linear map. For
$y\in{\mathbb F}_2^\ell$, write ${load}_h(y):=|h^{-1}(y)\cap S|$, and let
$M(S,h):=\max_{y\in{\mathbb F}_2^\ell}\{load}_h(y)$ be the maximum load. Jaber, Kumar and Zuckerman (STOC 2025) proved that the expected maximum load of $h$ on $S$ is ... more >>>

We study the parallel complexity of computing the arboricity of a graph, defined as the minimum number of forests into which its edges can be partitioned.
For graphs of bounded treewidth, we present a simple dynamic programming–based parallel algorithm that constructs an optimal partition of the edges into forests.
For ... more >>>

A depth-4 algebraic circuit with top fan-in $k$ and bottom fan-in $2$ is a circuit $\Phi$ of the form $\Phi = \sum_{i=1}^k \prod_{j=1}^{m_i} Q_{ij}$, where the polynomials $Q_{ij} \in \mathbb{K}[x_1, \ldots, x_n]$ have degree at most $2$.
The class of all such circuits is denoted by $\Sigma^k \Pi \Sigma ... more >>>

For a Boolean function $f:\{0,1\}^n\to\{0,1\}$, the higher-order Boolean derivative $D_S f$ computes the parity of $f$ over each $S$-dimensional subcube. We prove that $D_S f\equiv 1$ exactly when $S$ is a maximal monomial support in the algebraic normal form of $f$. This correspondence motivates the derivative certificate depth $\Delta_\partial(f)$, defined ... more >>>

The hardness vs. randomness paradigm converts a function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ that is hard for circuits of size $s$ into a pseudorandom generator (PRG) $G \colon \{0,1\}^d \to \{0,1\}^{s'}$ that fools circuits of size $s' = s'(s)$. In the application for derandomization, such as proofs of $\mathbf{BPP} = ... more >>>

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notion of robust extractors, which are extractors that remain sound even when a small number of points violate the min-entropy constraint. Using such objects, ... more >>>

Understanding the power of space-bounded computation with access to catalytic space has been an important theme in complexity theory over the recent years. One of the key algorithmic results in this area is that bipartite maximum matching can be computed in catalytic logspace with a polynomial-time bound, Agarwala and Mertz ... more >>>

Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function $S:\mathcal{X} \times \mathcal{X} \to [0,1]$ is a distribution over hash functions on $\mathcal{X}$ with the property that the probability of collision of any two elements $x,y\in ... more >>>

We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \leq \exp\bigl(n^{1-\varepsilon}\bigr)$ we exhibit an explicit family $\mathcal{A}$ of $n$-variate CNF formulas $A$, each of size $|A| \le s(n)^{1+\varepsilon}$, such that if $A$ is chosen uniformly ... more >>>

The seminal work of Benczu}r and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction ... more >>>

We present the first algorithms for polynomial identity testing (PIT) of read-$4$ arithmetic formulas in the non-multilinear setting. Specifically, we give a polynomial-time PIT algorithm in the whitebox model and a quasi-polynomial-time algorithm in the blackbox model. Since our techniques are based on proving hardness of representation results, we extend ... more >>>

We construct an explicit distribution $\mathbf{D}$ over $\{0,1\}^N$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distribution can be sampled exactly when each output bit is allowed two adaptive probes to an arbitrarily long sequence of independent uniform symbols from $[N]$. In contrast, any non-adaptive ... more >>>

List-decoding and list recovery ask how much corruption or uncertainty a code can tolerate while still keeping the number of plausible codewords small. For large alphabet codes, the ultimate benchmark for list-decoding is the ($\epsilon$-relaxed) generalized Singleton bound, which targets list-of-$L$ decoding radius with rate $R$ up to radius $\frac{L}{L+1}(1-R-\epsilon)$. ... more >>>

A famous theorem of Kruskal gives the simplest and arguably most fundamental criterion under which a tensor is guaranteed a unique minimum-rank decomposition. Kruskal's condition requires that the sum of the Kruskal ranks $\{k_i\}_{i=1}^m$ of the components satisfies $\sum_{i \in [m]} k_i \ge 2r + m - 1$, where $r$ ... more >>>

We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both hitting sets and lossless rank condensers. Roughly speaking, a variety-evasive subspace family $\mathcal{H}$ is a collection of subspaces such that for every algebraic variety $V$ in a fixed ... more >>>

The problem of recognizing $(k,l)$-tight graphs is a fundamental problem that has close connections to well studied problems
like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic
NC-algorithms for the problem are known for planar graphs, but no such ... more >>>

Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments. In particular, Forbes, Shpilka, Tzameret, and Wigderson (Theory Comput. 2021) developed the main lower-bound frameworks for restricted IPS fragments, ... more >>>

We introduce \emph{moonflowers}, a weaker analogue of sunflowers. A family of sets $S_1,\ldots,S_k$ is a $k$-moonflower if each set $S_i$ contains at least one element that is absent from all the others. We study the extremal problem of determining the largest possible size of a family of sets of size ... more >>>

Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$.

In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in ... more >>>

In secret-key private information retrieval (SK-PIR), the client in an offline phase processes the database using a short secret key. In the online phase the client could then use the secret key to make queries to the server, without revealing the entries accessed, and using only sublinear communication $o(N)$ in ... more >>>

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-tuple $\mathcal{P} = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: ... more >>>

The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding ... more >>>

Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction.

We show that breaking this barrier, even achieving seed length $O(\log^{3/2} n)$ (for, say, constant width), would follow from ... more >>>

We study two conjectures posed in the analysis of Boolean functions $f : \{-1, 1\}^n ? \{?1, 1\}$, in both of which, the Majority function plays a central role: the "Majority is Least Stable" (Benjamini et al., 1999) and the "Non-Interactive Correlation Distillation for Erasures" (Yang, 2004; O'Donnell and Wright, ... more >>>

We study when a sound arithmetic theory $\mathcal S{\supseteq}S^1_2$ with polynomial-time decidable axioms efficiently proves the bounded consistency statements $Con_{\mathcal S{+}\phi}(n)$ for a true sentence $\phi$. Equivalently, we ask when $\mathcal S$, viewed as a proof system, simulates $\mathcal S{+}\phi$. The paper's two unconditional contributions constrain possible characterizations. First, for ... more >>>

We prove a lower bound of $\Omega\left(n^{1.5}\right)$ for the number of product gates in non-commutative arithmetic circuits for an explicit $n$-variate degree-$n$ polynomial $f_{n}$ (over every field).

We observe that this implies that over certain non-commutative rings $R$, any arithmetic circuit that computes the induced polynomial function $f_{n}: R^n \rightarrow ... more >>>

Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [ABJ+22], the fundamental problem of estimating the $F_p$ moment to within any constant factor requires $\Omega(n)$ memory. In this model, the internal state of the (randomized) streaming algorithm is visible to ... more >>>

We consider (almost) $k$-wise independent hash functions, whose evaluations on any $k$ inputs are (almost) uniformly random, for very large values of $k$. Such hash functions need to have a large key that grows linearly with $k$. However, it may be possible to evaluate them in sub-linear time by ... more >>>

We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong $s$-blocking sets over finite fields.

Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or ... more >>>

The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it implies that the code has similar performance as random linear codes with respect to all “local properties”. Explicit algebraic codes, such as folded Reed-Solomon ... more >>>

We develop a topological framework for proving lower bounds on sign-rank via $\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms.

For every (partial) sign matrix $A$, we associate a free $\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ ... more >>>

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 >>>