Computational Complexity of Discrete Problems

Given a sequence of N independent sources $X_1,X_2,\mathrm{\dots },X_N$, each on n bits, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC ’20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just $K\ge N1/2$ good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just $K\ge N0.01$ (FOCS ’21). In this paper, we finally achieve $K=3$. Our key ingredient is a near-optimal explicit construction of a new pseudorandom primitive, called a leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols. Our LRE can be viewed as a significantly more robust version of Li’s low-error three-source extractor (FOCS ’15), and resolves an open question put forth by Kumar, Meka, and Sahai (FOCS ’19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS ’20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and non-malleable extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.

Marx showed that $n^{o(k/\log k)}$ time algorithms for detecting colorful $H$-subgraphs would refute the exponential-time hypothesis ETH, even when $H$ is a $k$-vertex expander of constant degree. This shows that colorful $H$-subgraphs are hard even for sparse $H$, and this result is widely used to obtain almost-tight conditional lower bounds.

We show a self-contained proof of this result that further simplifies very recent works. For this, we introduce a novel graph parameter, the linkage capacity $\gamma (H)$, and we show that detecting colorful $H$-subgraphs in time $n^{o(\gamma (H))}$ refutes ETH.

A very simple construction of communication networks credited to Beneš gives $k$-vertex graphs of maximum degree $3$ and linkage capacity $\mathrm{\Omega }(k/\log k)$. Additionally, we obtain new tight lower bounds for certain patterns by analyzing their linkage capacity. For example, we prove that almost all $k$-vertex graphs of polynomial average degree $\mathrm{\Omega }(k^{\beta })$ for some $\beta >0$ have linkage capacity $\mathrm{\Theta }(k)$, which implies tight lower bounds for such patterns $H$.

In this talk we will show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an $n^{\mathrm{\Omega }(k)}$ lower bound for the clique function up to $k\le n^{1/2-ϵ}$, and an $\exp (\mathrm{\Omega }(n^{1/3-ϵ}))$ lower bound for a function in P.

The celebrated BLR linearity test states that if a Boolean function $f$ satisfies $f(x)\oplus f(y)=f(x\oplus y)$ with probability close to $1$, then $f$ is close to a linear function, that is, a function that satisfies this equation for all $x,y$. Another way to view the BLR test is through the lens of polymorphisms, a notion from universal algebra. Linear functions are polymorphisms of the predicate $P_{\oplus }=\{(a,b,c)\in {\{0,1\}}^3\mid a\oplus b=c\}$. The BLR test states that an approximate polymorphism of $P_{\oplus }$ (with respect to the uniform distribution) is close to an exact polymorphism. Other results of a similar sort include Mossel’s approximate Arrow theorem, a result of Friedgut and Regev about Kneser graphs, and a result about AND testing which is a prequel to the present work.

In this work, we show that a BLR-like result holds for all predicates on bits, with respect to any distribution which is fully supported on the predicate (this includes BLR for arbitrary distributions). As in the case of AND testing, the statement needs to be changed to allow “multi-sorted” polymorphisms. The proof resembles the classical proof of the triangle removal lemma using the regularity lemma, with Jones’ regularity lemma replacing Szemerédi’s, and It Ain’t Over Till It’s Over an essential ingredient for the counting lemma.

In this talk, we will introduce a new notion of information complexity for one-pass and multi-pass streaming problems, and use it to prove memory lower bounds for the coin problem. In the coin problem, one sees a stream of $n$ i.i.d. uniform bits and one would like to compute the majority (or sum) with constant advantage. We show that any constant pass algorithm must use $\mathrm{\Omega }(\log n)$ bits of memory. This information complexity notion is also useful to prove tight space complexity for the needle problem, which in turn implies tight bounds for the problem of approximating higher frequency moments in a data stream.

The Strong Exponential Time Hypothesis (SETH) asserts that for every $\epsilon >0$ there exists $k$ such that $k$-SAT requires time ${(2-\epsilon )}^n$. The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-$k$-SAT, and Set Cover.

In this paper, we show that fine-grained reductions implying even ${\lambda }^n$-hardness of these problems from SETH for any $\lambda >1$, would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question).

We also extend this barrier result to the class of parameterized problems. Namely, for every $\lambda >1$ we conditionally rule out fine-grained reductions implying SETH-based lower bounds of ${\lambda }^k$ for a number of problems parameterized by the solution size $k$.

Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds).

In this talk, I’ll show that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$-query robust test in the “high-error” regime. The previous results in this space either worked only in the "low-error" regime (Polishchuk & Spielman, STOC 1994), or required $q=\mathrm{\Omega }(d^4)$ (Arora & Sudan, Combinatorica 2003), or needed to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $\mathrm{\Omega }(d^2)$-query complexity (Raz & Safra, STOC 1997).

Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection (namely Hensel lifting) between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner in the context of root-finding.

We present an optimal “worst-case exact to average-case approximate” (non-uniform) reduction for Matrix Multiplication: Given an oracle that correctly computes, in expectation, a $(1/p+ϵ)$-fraction of pairs $(A,B)$ of uniformly random matrices over a finite field of order p, we design an efficient oracle non-uniform algorithm that computes Matrix Multiplication exactly for all the pairs of matrices. The proof is based on a simple proof for Yao’s XOR lemma, whose complexity overhead is independent of the output length.

I will discuss several fundamental complexity measures for Boolean matrices, such as rank, approximate rank, sign-rank, factorization norm, approximate factorization norm, etc. Then, I will discuss the relationship between these measures by addressing the following question: for two measures, $X$ and $Y$, is it true that for all Boolean matrices $M$, if $X(M)$ is small, then $Y(M)$ is small? The quantitative aspects of this question have been an important line of work for several decades, with applications in many areas such as communication complexity, learning theory, dimensionality reduction, etc. However, the question is still poorly understood for several pairs of measures $X$ and $Y$. I will discuss a few collaborative works to address this question.

We study connections between two fundamental questions from computer science theory. (1) Is witness encryption possible for NP [1]? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to provide a witness for $x\in L$? (2) Is computational learning (in the sense of [2]) hard for NP? That is, is there a polynomial-time reduction from instances of $L$ to instances of learning?

Our main result is that a certain formulation of NP-hardness of learning (very close to one described in [3]) characterizes the existence of witness encryption for NP. More specifically, we show:

• $\mathrm{■}$

  witness encryption for NP secure against non-uniform polynomial-size adversaries is equivalent to a “half-Levin” reduction from NP to the Computational Gap Learning problem [3];

• $\mathrm{■}$

  witness encryption for NP secure against uniform polynomial-time adversaries is equivalent to a BPP-black-box half-Levin reduction from NP to a search version of the same problem;

• $\mathrm{■}$

  witness encryption for NP with ciphertexts having logarithmic length, along with a circuit lower bound for E, are together equivalent to a half-Levin reduction from NP to a “distributional” version of the Minimum Circuit Size Problem.

Next, we prove two unconditional NP-hardness results for agnostic PAC learning. Building on ideas from [5], we prove that agnostic PAC-learning of polynomial-size boolean circuits is NP-hard in the “semi-proper” setting of learning size-$s(n)$ circuits by size-$s(n)\cdot n^{1/{(\log \log n)}^{O(1)}}$ circuits. We also prove NP-hardness of nearly improper learning in an agnostic “oracle-PAC” model that we define here, in which an algorithm is explicitly given the polynomial-length truth-table of a randomly sampled oracle function $𝒪$ and is asked to learn with respect to $𝒪$-oracle circuits.

Lastly, we give some consequences of our results for the possibility of private- and public-key cryptography. Improving a main result of [3], we show that if improper agnostic PAC learning is NP-hard under a randomized non-adaptive reduction, then $\text{NP}⊈\text{io}\text{BPP}$ implies the existence of one-way functions. Assuming a half-Levin reduction from an NP-complete language to CGL, we show that $\text{NP}⊈\text{io}\text{BPP}$ implies the existence of public-key encryption. Along the way, we obtain: if $\text{NP}⊈\text{io}\text{BPP}$, then witness encryption for NP implies public-key encryption.⁶⁶6We believe that this last statement follows from a combination of techniques used in prior work ([1, 4, 6]; see [7]), but we have not seen the uniform version stated. In any case, we offer an alternative proof that does not rely on properties of statistical zero knowledge arguments.

In this work, we develop a new method for proving lower bounds for static data structures in the classical cell probe model of Yao. Our methods give the strongest known lower bounds for any explicit problem in this model (quadratically stronger for space as a function of time) and break a barrier which has stood for a few decades. Our lower bounds are based on a connection we establish between the static cell probe model and ${\text{NC}}^0$ generators, which have been studied extensively in cryptography and more recently in the context of “range avoidance.” With this connection in mind, we analyze the best known cryptographic attacks on ${\text{NC}}^0$ PRGs, which in turn are based on semirandom CSP refutation, and apply a similar family of arguments to analyze the cell probe model.

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, exhibited the power of catalytic space (CSPACE) and in particular catalytic logspace machines (CL) beyond that of traditional space-bounded machines.

Several variants of CL have been proposed, including non-deterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et. al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes.

We settle almost all questions regarding randomized and non-deterministic catalytic computation, by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. One main consequence of this is $\text{CL}=\text{CNL}$ i.e. with access to a large filled hard-drive, non-determinism provides no additional power.

Our results build on the compress-or-compute framework of Cook et al. (STOC 2025). Despite proving broader and stronger results, our framework is simpler and more modular.

Expanders are well-connected graphs that have been extensively studied and have numerous applications in computer science, including error-correcting codes. High-dimensional expanders (HDXs) generalize expanders to hypergraphs and have the powerful local-to-global property. Roughly speaking, this property states that the expansion of an HDX can be certified by the expansion of certain local structures. This property has made HDXs crucial in the recent breakthrough on locally testable codes (LTCs) [Dinur et al.’22]. These LTCs simultaneously achieve constant rate, constant relative distance, and constant query complexity. However, despite these desirable properties, these LTCs have yet to find applications in proof systems, as they lack the crucial multiplication property present in widely used polynomial codes. A major open question is: Do there exist LTCs with the multiplication property that achieve the same rate, distance, and query complexity as those constructed by Dinur et al.?

In this talk, I will provide intuition behind the connection between HDXs and LTCs, explain why the LTCs by Dinur et al. lack the multiplication property, and discuss my recent and ongoing work on constructing LTCs with the multiplication property. This talk is based on joint works with Irit Dinur, Rachel Zhang, and Huy Tuan Pham.

We introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta (N)\ge 1/\mathrm{𝗉𝗈𝗅𝗒}(N)$ fixed in advance, output an $N$-bit string that has probability less than $\delta (N)$. We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization.

We will cover a recent breakthrough result by Williams [3] showing that $\text{TIME}[t]$ is contained in $\text{SPACE}[{(t\log t)}^{1/2}]$ for all $t\ge n$. We give an overview of the technique, which combines a decomposition of $\text{TIME}[t]$ (given by Hopcroft, Paul, and Valiant [2]) with a recent space-efficient algorithm for solving Tree Evaluation (given by Cook and Mertz [1]). Finally we analyze both ideas and barriers with regards to further progress, as well as potential other directions.

We exhibit supercritical trade-offs for monotone circuits, showing that there are functions computable by small circuits for which any small circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the first size-depth trade-offs for cutting planes and resolution that are truly supercritical, i.e., in terms of formula size rather than number of variables, and we also show supercritical trade-offs between width and size for treelike resolution.

Our results build on a new supercritical depth-width trade-off for resolution, obtained by refining and strengthening the compression scheme for the cop-robber game in [Grohe, Lichter, Neuen & Schweitzer 2023]. This yields robust supercritical trade-offs for dimension versus iteration number in the Weisfeiler–Leman algorithm. Our other results follow from improved lifting theorems that might be of independent interest.

I will prove an exponential lower bound on bottom regular read-once linear branching programs computing non-malleable affine disperser. This is an improvement of our result [1], where we proved an exponential lower bound on branching programs satisfying a stronger condition.

How can we efficiently construct a $t$-wise independent permutation from local permutation gates that act only on a constant number of bits? This question, originally studied by Gowers in 1996, turns out to be linked to an important object in quantum information theory called $t$-unitary designs. These designs are pseudorandom unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure on the unitary group. An important recent line of work in quantum computing concerns efficiently constructing such $t$-unitary designs from local unitary gates that act on a constant number of qubits.

This talk presents a survey of recent developments toward efficient construction of such objects. The talk will mainly be based on my work on the "PFC ensemble" [1], but will also discuss some subsequent followup works by other researchers.

Query-to-communication lifting is a powerful method for transferring lower bounds from the query (or decision-tree) model to the communication model. A landmark result by Göös, Pitassi, and Watson (FOCS 2017, SICOMP 2020) demonstrated how to lift randomized query complexity bounds to randomized communication complexity of a related problem, obtained by replacing each input bit with a small “gadget”. A key lemma in their work is the uniform marginals lemma, whose proof is the most technical component of their paper.

We present a new, simpler proof for this lemma. We also discuss limitations of the lemma and, more broadly, of lifting results with the Index gadget, suggesting a modified gadget to address these limitations.

Classical PRGs are coupled with a reconstruction argument, asserting that if an adversary can break the PRG, then the adversary can also compute the underlying hard function. Classical reconstruction procedures are randomized, but a recent research effort developed reconstruction procedures for various PRGs that are deterministic, when considering limited types of adversaries.

This talk will present a recent result within this research effort. We construct a pair of deterministic low-space algorithms such that on every input graph, at least one of these algorithms solves a classical problem significantly better than the state-of-the-art: either s-t connectivity is solved, or random walk probabilities are estimated. Consequently, we’ll see how to connect the $\text{BPL}=\text{L}$ question to the question of improving on Savitch’s theorem.

We give an introduction to graph rigidity. Similarly as the perfect matching problem it is related to many other algorithmic problems. In particular, minimal graph rigidity reduces to bipartite perfect matching, which puts it in quasi-NC. Our results are that minimal graph rigidity for planar graphs is in NC, as well as for $K_{3,3}$-free and $K_5$-free graphs.

We give the first explicit constructions of vertex expanders that pass the spectral barrier.

Previously, the strongest known explicit vertex expanders were those given by d-regular Ramanujan graphs, whose spectral properties imply that every small set S of vertices has at least $0.5d|S|$ distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S that has no more than $0.5d|S|$ distinct neighbors. In fact, no explicit construction was known to beat the 0.5 barrier.

In this talk, I will discuss how we construct vertex expanders for which every small set expands by a factor of $0.6d$. In fact, our construction satisfies an even stronger property: small sets actually have $0.6d|S|$ *unique neighbors*.

Savitch’s Theorem [2], which states that $\text{NSPACE}[s]$ is contained in $\text{SPACE}[s^2]$, has stood as a benchmark result in complexity theory for over fifty years. We propose that its tree-like structure can be exploited in conjunction with recent work of Cook and Mertz [1] to show that $\text{NSPACE}[s]\subseteq \text{SPACE}[o(s^2)]$. This can be achieved by taking the classic ${\text{NC}}^2$ algorithm implicit in [2] and improving its height by an $\omega (\log \log n)$ factor at the expense of increasing the alphabet size of the wires and functions from $\{0,1\}$ to ${\{0,1\}}^{o({\log }^{2}n)}$.