We prove several results concerning the communication complexity of a collision-finding problem, each of which has applications to the complexity of cutting-plane proofs, which make inferences based on integer linear inequalities.

In particular, we prove an $\Omega(n^{1-1/k} \log k \ /2^k)$ lower bound on the $k$-party number-in-hand communication complexity of ... more >>>

The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that $n$-variate non-zero polynomial functions of degree $d$ over a field $\mathbb{F}$, are non-zero over any ``grid'' (points of the form $S^n$ for finite subset $S \subseteq \mathbb{F}$) with probability at least $\max\{|S|^{-d/(|S|-1)},1-d/|S|\}$ over the choice of random point from the grid. In particular, ... more >>>

In a seminal work, Buhrman et al. (STOC 2014) defined the class $CSPACE(s,c)$ of problems solvable in space $s$ with an additional catalytic tape of size $c$, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform $TC^1$ circuits are ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_6^{\P}$) there are extractors ... more >>>

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results:

We first show that by making small modifications to the nonzero coefficients of the degree-$K$, $N$-variate elementary symmetric polynomial $\sigma_{N,K}$, one obtains a polynomial that can be computed by a monotone ... more >>>

In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ ... more >>>

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree.

As a consequence of our result, we obtain ... more >>>

We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies ... more >>>

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks of proving circuit lower bounds and ... more >>>

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism.

In this work we study ... more >>>

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G \setminus \{0\}$ such that $(x, y)$, $(x+d, y)$, $(x, y+d) \in A$. We prove that
$|A| \le |G|^2 ... more >>>

Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of such codes has remained a notorious challenge. While the construction of asymptotically-good explicit tree codes continues to be elusive, a work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, ... more >>>

Let $\mathcal{C}$ be a complexity class and $A$ be a language. The statement ``$A \not\in \mathcal{C}$'' is a separation of $A$ from $\mathcal{C}$. A separation is constructive if there is an efficient algorithm called a refuter that prints counterexamples to the statement ``$M$ decides $A$'' for every $\mathcal{C}$-algorithm $M$. Concretely, ... more >>>

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when ... more >>>

Consider graphs of n nodes and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log ... more >>>

The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a major challenge to understand the precise connections between PIT and lower bounds. In particular, a main goal has been to understand which lower ... more >>>

We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the ... more >>>

In a $3$-XOR game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$, and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a finite Abelian group $\mathcal{A}$ defining a constraint. The verifier sends the questions $x$, $y$ and $z$ to the players Alice, Bob and Charlie ... more >>>

The notion of closure of a set of linear forms, first introduced by Efremenko, Garlik, and Itsykson [EGI-STOC-24], has proven instrumental in proving lower bounds on the sizes of regular and bounded-depth Res($\oplus)$ refutations [EGI-STOC-24, AI-STOC-25]. In this work, we present amortized closure, an enhancement that retains the properties of ... more >>>

Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing ... more >>>

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let $\mathbb{K}$ be an algebraically closed field of characteristic zero, and let $\mathcal{F} = \{F_1, \ldots, F_m\} \subset \mathbb{K}[x_1, \ldots, x_N]$ denote a collection of irreducible homogeneous polynomials of degree at most $d$, where each $F_i$ is ... more >>>

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f: \{0,1\}^n\to \{0,1\}$ and $g : \mathcal{X} \times \mathcal{Y}\to \{0,1\}$, denote $f\circ g(x,y) := f(g(x_1,y_1),\ldots,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$,
\[D(f\circ g) \geq s\cdot \bigg(\frac{\Omega(D(g))}{\log rk(g)} - \log rk(g)\bigg),\]
where ... more >>>

A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, ... more >>>

Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-AVOID). It is known that deterministic polynomial time algorithms (even with access ... more >>>

We reduce the problem of proving deterministic and nondeterministic Boolean circuit size lower bounds to the analysis of certain two-dimensional combinatorial cover problems. This is obtained by combining results of Razborov (1989), Karchmer (1993), and Wigderson (1993) in the context of the fusion method for circuit lower bounds with the ... more >>>

We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erd?s-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on ... more >>>

Given an efficient algorithm that correctly computes a tiny fraction of the entries of the matrix multiplication of a small fraction of two matrices, can one design an efficient algorithm that computes matrix multiplication exactly for all the matrices? In this paper, we present such ``worst-case exact to average-case approximate'' ... more >>>

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach ... more >>>

This paper demonstrates a duality between the non-robustness of polynomial time dimension and the existence of one-way functions. Polynomial-time dimension (denoted $\mathrm{cdim}_\mathrm{P}$) quantifies the density of information of infinite sequences using polynomial time betting algorithms called $s$-gales. An alternate quantification of the notion of polynomial time density of information is ... more >>>

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a ROBP.
We have the following results.

For standard ROBPs, there exists an ... more >>>

Relaxations for the constraint satisfaction problem (CSP) include bounded width (BW), linear program (LP), semidefinite program (SDP), affine integer program (AIP), and their combinations. Tightening relaxations systematically leads to hierarchies and stronger algorithms. For LP+AIP and SDP+AIP hierarchies, various lower bounds were shown by Ciardo and Živný (STOC 2023, STOC ... more >>>

We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex ... more >>>

We consider a subclass of $\mathbf{AC}^0[2]$ circuits that simultaneously captures $\mathrm{DNF} \circ \mathrm{Xor}$ and depth-$3$ $\mathbf{AC}^0$ circuits. For this class we show a technique for proving lower bounds inspired by the top-down approach. We give lower bounds for the middle slice function, inner product function, and affine dispersers.

In Crypto'19, Goyal, Jain, and Sahai (GJS) introduced the elegant notion of *secret-sharing of an NP statement* (NPSS). Roughly speaking, a $t$-out-of-$n$ secret sharing of an NP statement is a reduction that maps an instance-witness pair to $n$ instance-witness pairs such that any subset of $(t-1)$ reveals no information about ... more >>>

We study the communication complexity of multiplying $k\times t$
elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead
model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$.
This is an exponential improvement over previous work, and matches
the state-of-the-art in the area.

Relatedly, we show that the convolution ... more >>>

We prove several new results on the Hamming weight of bounded uniform and small-bias distributions.

We exhibit bounded-uniform distributions whose weight is anti-concentrated, matching existing concentration inequalities. This construction relies on a recent result in approximation theory due to Erdéyi (Acta Arithmetica 2016). In particular, we match the classical tail ... more >>>

We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, ... more >>>

The symmetric binary perceptron ($\mathrm{SBP}_{\kappa}$) problem with parameter $\kappa : \mathbb{R}_{\geq1} \to [0,1]$ is an average-case search problem defined as follows: given a random Gaussian matrix $\mathbf{A} \sim \mathcal{N}(0,1)^{n \times m}$ as input where $m \geq n$, output a vector $\mathbf{x} \in \{-1,1\}^m$ such that $$|| \mathbf{A} \mathbf{x} ||_{\infty} \leq ... more >>>

We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time $t$ in $O(t/\log t)$ space from 50 years ago [FOCS 1975, ... more >>>

We present a new technique for using catalytic space to simulate space-bounded randomized algorithms.
Allocate one bit on the catalytic tape for each configuration of a randomized machine.
Simulate the machine several times.
Each time it requests a random bit, use the bit from the catalytic tape corresponding to its ... more >>>

In the last year, there have been some remarkable improvements in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes. Starting from the work on Kopparty, Ron-Zewi, Saraf and Wootters (and subsequent simplifications due to Tamo), we have had dramatic improvements in the list-size bounds of FRS ... more >>>

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where $n$ parties, each holding an input bit, wish to know each other's input. For this, they communicate in rounds, where, in each round, one designated party sends ... more >>>

We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to $\epsilon d$ gates on every root-to-leaf path ... more >>>

An oblivious bit-fixing source is a distribution over $\{0,1\}^n$, where $k$ bits are uniform and independent and the rest $n-k$ are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity ... more >>>

Pseudodeterministic algorithms are probabilistic algorithms that solve search problems but do so by always providing the same (``canonical'') solution to a given instance, except with small probability.
While the complexity theoretic implications of pseudodeterministic algorithms were explored in the past, we suggest to conduct this exploration within the framework ... more >>>

The question of optimal derandomization, introduced by Doron et. al (JACM 2022), garnered significant recent attention. Works in recent years showed conditional superfast derandomization algorithms, as well as conditional impossibility results, and barriers for obtaining superfast derandomization using certain black-box techniques.

Of particular interest is the extreme high-end, which ... more >>>

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash ... more >>>

In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 ($\Sigma\Pi\Sigma(3)$ circuits) over the fields $\mathbb{R}$ and $\mathbb C$. Concretely, we show that given blackbox access to an $n$-variate polynomial $f$ computed by a $\Sigma\Pi\Sigma(3)$ circuit of ... more >>>

We prove that if a degree-$d$ homogeneous polynomial $f$ has border Waring rank $\underline{\mathrm{WR}}({f}) = r$, then its Waring rank is bounded by
\[
{\mathrm{WR}}({f}) \leq d \cdot r^{O(\sqrt{r})}.
\]
This result significantly improves upon the recent bound ${\mathrm{WR}}({f}) \leq d \cdot 4^r$ established in [Dutta, Gesmundo, Ikenmeyer, Jindal, ... more >>>

We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, \mu_p^{\otimes n})$ in the 1% regime. For a distribution $\nu$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $\mu_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(\nu)$ proceeds as follows: Given query access to a function ... more >>>

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfiable. It is known that the CSPs that admit efficient robust satisfaction algorithms are precisely those of bounded width, i.e., CSPs whose satisfiability can be ... more >>>

We prove a time hierarchy theorem for the promise-BPTIME. This is considered to be a folklore problem and was thought to follow from the existence of complete problems or through direct diagonalization. We observe that neither argument carries through in some immediate way in the promise version. However, the hierarchy ... more >>>

For any constant $\alpha > 0$, we construct an explicit pseudorandom generator (PRG) that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $(1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$. For context, one can achieve seed length $(2 + o(1)) \cdot ... more >>>

We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree $F_2$-polynomials that we did not have correlation bounds for before. In particular:

1. We construct a PRG for width-2 $poly(n)$-length branching programs which read $d$ bits ... more >>>

A secret-sharing scheme allows the distribution of a secret $s$ among $n$ parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about $s$. The collection of authorized/unauthorized sets is defined by a monotone function $f: \{0,1\}^n \rightarrow \{0,1\}$. ... more >>>