Results 1 - 10 of 24762

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and weighted linear matroid intersection. This in turn helps to show that the search versions of bipartite matching and linear matroid intersection are in NC as well. The techniques are based on a polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).

A subspace design is a collection of large linear subspaces whose members, on average, have small intersection dimension with every low-dimensional subspace. Originally introduced as a tool for constructing list-decodable codes, subspace designs have since become a useful primitive in linear-algebraic pseudorandomness, with applications to rank condensers and dimension expanders.

Intriguingly, near-optimal subspace designs are themselves constructed from algebraic codes, including folded Reed–Solomon and univariate multiplicity codes. Recent work reveals a powerful reverse connection: the subspace-design property explains why these highly structured codes admit optimal list-size bounds for list decoding and proximity gaps approaching the optimal radius. More broadly, near-optimal subspace-design codes inherit, up to an arbitrarily small loss in rate, the guarantees of random linear codes for local coordinate-wise linear (LCL) properties—a broad framework encompassing list decoding and list recovery.

The talk will survey this circle of ideas and explain how subspace designs have become a unifying tool for derandomization in coding theory and theoretical computer science. I will also briefly discuss their role in the recent deterministic NC algorithm for bipartite perfect matching.

Polynomial identity testing (PIT) is a central problem in theoretical computer science with numerous algorithmic applications, including applications to problems with no obvious algebraic character. Known polynomial-time algorithms for PIT crucially rely on the use of randomness. Designing a deterministic polynomial-time algorithm for PIT is a major goal of algebraic complexity theory.

Often, algorithms for PIT are obtained by constructing pseudorandom objects known as hitting set generators. Recently, there has been interest in constructing such hitting set generators in a “cryptographic” regime of parameters, where the complexity of the generator is very small compared to the class of algebraic circuits it fools.

In this talk, I will describe a new construction of a generator where each output can be computed by a formula of constant size and the generator itself fools algebraic circuits of polynomial size and constant depth. Under strong (but reasonable) hardness assumptions, this generator also fools polynomial-size algebraic branching programs.

In a recent breakthrough, Williams (STOC 2025) showed that any decision problem solvable in time $t$ by a multitape Turing machine can be solved in space $\tilde{O}(\sqrt{t})$ and time $2^{\tilde{O}(\sqrt{t})}$. The immediate question is whether this result is an anomaly, or an inherent feature of computation more generally.

In this work we provide evidence that the resource trade-offs phenomenon first demonstrated by Williams is systematic, i.e. inherent to computation in general. Specifically, under a plausible complexity-theoretic hardness assumption, we show that $t$-time algorithms can be simulated in space $t^{\epsilon}$, for any constant $\epsilon>0$, where the simulation is correct on average over a random input. We also show, under similar complexity-theoretic hardness assumptions, that $t$-time algorithms can be simulated in \emph{linear time} using sufficiently many alternations (i.e., $\forall/\exists$ quantifiers), where again the simulation is correct on average over a random input.

Some hardness assumption is necessary to prove these conclusions (as they imply that $\mathsf{P}\ne\mathsf{PSPACE}$), and the specific hardness assumption that we rely on has been extensively studied in complexity theory in recent years: hardness of a computational problem called Range Avoidance. Specifically, we introduce a new ``low-space'' variant of Range Avoidance, and show (under mild derandomization assumptions) that average-case hardness of this problem for polynomial-time algorithms is in fact \emph{equivalent} to low-space simulation of $\mathsf{FP}$, and implies linear-time simulation with alternations. We then study the complexity of this new problem, showing conditional hardness results and algorithms.

Joint work with Roei Tell.

Classical computer science offers two powerful ways to construct simple substitutes for ideal randomness: k-wise independent functions, which look random on any k inputs, and pseudorandom functions, which look random to any computationally efficient algorithm. This talk explores how these classical ideas can be used to construct quantum operations that look random.

For quantum operations, the natural benchmark is a Haar random unitary matrix. These matrices play important roles in quantum computation and cryptography and provide models of chaotic physical systems such as black holes. I will introduce the PFC ensemble, which combines random permutations (P) and functions (F) with quantum Clifford (C) operations. It provides a unified approach to constructing unitary designs and pseudorandom unitaries, the quantum counterparts of the two classical notions. I will also highlight a few recent developments and open questions in quantum pseudorandomness. No background in quantum information will be assumed for this talk.

Based in part on joint work with Tony Metger, Alexander Poremba and Henry Yuen.