Aaron Putterman

Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman

Given a constraint satisfaction problem (CSP) predicate $P \subseteq D^r$, the non-redundancy (NRD) of $P$ is maximum-sized instance on $n$ variables such that for every clause of the instance, there is an assignment which satisfies all but that clause. The study of NRD for various CSPs is an active area of research which combines ideas from extremal combinatorics, logic, lattice theory, and other techniques. Complete classifications are known in the cases $r=2$ and $(|D|=2, r=3)$. In this paper, we give a near-complete classification of the case $(|D|=2, r=4)$. Of the 400 distinct non-trivial Boolean predicates of arity 4, we implement an algorithmic procedure which perfectly classifies 397 of them. Of the remaining three, we solve two by reducing to extremal combinatorics problems -- leaving the last one as an open question. Along the way, we identify the first Boolean predicate whose non-redundancy asymptotics are non-polynomial.

Aaron Putterman, Salil Vadhan, Vadim Zaripov

Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound on exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1. $O(\log(m))$-wise independence suffices for preserving connectivity when sampling at rate $1/2$ in a graph with minimum cut $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). 2. $O(\log(m))$-wise $\frac{1}{\mathrm{poly}(m)}$-almost independence suffices for ensuring cycle-freeness when sampling at rate $1/2$ in a graph with minimum cycle length $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.

Sanjeev Khanna, Christian Konrad, Aaron Putterman

Fault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) gives $(2k-1)$-stretch, $f$-fault-tolerant spanners with $O(k^2 f^{\frac{1}{2}-\frac{1}{2k}} n^{1+\frac{1}{k}} + k f n)$ edges for any odd $k$. For any $k = \tilde{O}(1)$, this bound is essentially optimal for deterministic spanners in part due to a known folklore lower bound that \emph{any} $f$-fault-tolerant spanner requires $Ω(nf)$ edges in the worst case. For $f \geq n$, this $Ω(nf)$ barrier means that any $f$-fault tolerant spanners are trivial in size. Crucially however, this folklore lower bound exploits that the spanner \emph{is itself a subgraph}. It does not rule out distance-reporting data structures that may not be subgraphs. This leads to our central question: can one beat the $n \cdot f$ barrier with fault-tolerant distance oracles? We give a strong affirmative answer to this question. As our first contribution, we construct $f$-fault-tolerant distance oracles with stretch $O(\log(n)\log\log(n))$ that require only $\widetilde{O}(n\sqrt{f})$ bits of space; substantially below the spanner barrier of $n \cdot f$. Beyond this, in the regime $n \leq f \leq n^{3/2}$ we show that by using our new \emph{high-degree, low-diameter} decomposition in combination with tools from sparse recovery, we can even obtain stretch $7$ distance oracles in space $\widetilde{O}(n^{3/2}f^{1/3})$ bits. We also show that our techniques are sufficiently general to yield randomized sketches for fault-tolerant ``oblivious'' spanners and fault-tolerant deterministic distance oracles in bounded-deletion streams, with space below the $nf$ barrier in both settings.

Sanjeev Khanna, Aaron Putterman, Junkai Song

We study the parallel (adaptive) complexity of the classic problem of finding a basis in an $n$-element matroid, given access via an \emph{independence oracle}. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS~1985, JCSS~1988; hereafter KUW) initiated this study, showing that $O(\sqrt{n})$ adaptive rounds suffice for any matroid, and that $\widetildeΩ(n^{1/3})$ rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS~2025; hereafter KPS) achieved $\widetilde O(n^{7/15})$ rounds, the first improvement since~KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in $\widetilde O(n^{3/7})$ rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously.

Arpon Basu, Joshua Brakensiek, Aaron Putterman

We study the problem of Hamiltonian sparsification: given a parameter $\varepsilon \in (0,1)$ and an $n$-qubit Hamiltonian $H$ which is the sum of $r$-local positive semi-definite (PSD) terms $H_1, \dots H_m$, our goal is to compute a sparse set $L \subseteq [m]$, along with weights $w: L \rightarrow \mathbb{R}_{\geq 0}$ such that for every state $|ψ\rangle\in \mathbb{C}^{2^n}$, $$ \sum_{i \in L} w(i) \langle ψ| H_i | ψ\rangle \in (1 \pm ε) \sum_{i = 1}^m \langle ψ| H_i | ψ\rangle $$. When the set $L$ is significantly smaller than $m$, this reduces the number of terms in the underlying system, while still ensuring that the behavior of the system is essentially unchanged. We show that many Hamiltonians indeed are sparsifiable to a number of terms much smaller than $n^r$, including: (a) Hamiltonians where each term is an $r$-local Pauli string, (b) Hamiltonians where each term is an $r$-local random operator of rank $R$, for $R \geq 2^{r-1}+1$, and (c) Hamiltonians where each term is an arbitrary $r$-local operator of rank $\geq 2^r -1$ (a.k.a. Quantum SAT). Taken together, our results show that the sparsifiability of Hamiltonians is a robust phenomenon, contrary to prevailing belief (see for instance, Aharonov-Zhou ITCS 2019, QIP 2019). Our results find applications, for instance, to better (semi-)streaming algorithms for quantum Max-Cut, answering a question left open by Kallaugher and Parekh (FOCS 2022). In fact, our results even codify that quantum systems are often easier to sparsify than their classical counterparts.