Zander Kelley

FOCS Conference 2025 Conference Paper

More efficient sifting for grid norms, and applications to multiparty communication complexity

• Zander Kelley
• Xin Lyu

Building on the techniques behind the recent progress on the 3-term arithmetic progression problem [15], Kelley, Lovett, and Meka [14] constructed the first explicit 3-player function $f: [N]^{3} \rightarrow\{0, 1\}$ that demonstrates a strong separation between randomized and (non-)deterministic NOF communication complexity. Specifically, their hard function can be solved by a randomized protocol sending $O(1)$ bits, but requires $\Omega\left(\log ^{1 / 3}(N)\right)$ bits of communication with a deterministic (or non-deterministic) protocol. We show a stronger $\Omega\left(\log ^{1 / 2}(N)\right)$ lower bound for their construction. To achieve this, the key technical advancement is an improvement to the sifting argument for grid norms of (somewhat dense) bipartite graphs. In addition to quantitative improvement, we qualitatively improve over [14] by relaxing the hardness condition: while [14] proved their lower bound for any function f that satisfies a strong two-sided pseudorandom condition, we show that a weak one-sided condition suffices. This is achieved by a new structural result for cylinder intersections (or, in graph-theoretic language, the set of triangles induced from a tripartite graph), showing that any small cylinder intersection can be efficiently covered by a sum of simple “slice” functions.

STOC Conference 2024 Conference Paper

Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication

• Zander Kelley
• Shachar Lovett
• Raghu Meka

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function f :[ N ] 3 → {0,1}, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing it requires sending about (log N ) 1/3 many bits. This exponentially improves upon the previously best-known such separation. At the core of our proof is an extension of a recent result on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.

STOC Conference 2024 Conference Paper

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

• Amir Abboud
• Nick Fischer
• Zander Kelley
• Shachar Lovett
• Raghu Meka

FOCS Conference 2023 Conference Paper

Strong Bounds for 3-Progressions

• Zander Kelley
• Raghu Meka

We show that for some constant $\beta\gt0$, any subset A of integers $\{1, \ldots, N\}$ of size at least $2^{-O\left((\log N)^{\beta}\right)} \cdot N$ contains a non-trivial three-term arithmetic progression. Previously, three-term arithmetic progressions were known to exist only for sets of size at least $N /(\log N)^{1+c}$ for a constant $c\gt0$. Our approach is first to develop new analytic techniques for addressing some related questions in the finite-field setting and then to apply some analogous variants of these same techniques, suitably adapted for the more complicated setting of integers.

STOC Conference 2021 Conference Paper

An improved derandomization of the switching lemma

• Zander Kelley

We prove a new derandomization of Håstad’s switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size m using only O (log m ) random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC 0 -circuits. Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC 0 -circuits (CCC’13): we show that the generator ε-fools size- m , depth- D circuits with n -bit inputs using only O (log( m /ε) D · log n ) random bits. In particular, we obtain (modulo the loglog-factors hidden in the O -notation) a dependence on m /ε which is best-possible with respect to currently-known AC 0 -circuit lower bounds.

FOCS Conference 2018 Conference Paper

Pseudorandom Generators for Read-Once Branching Programs, in Any Order

• Michael A. Forbes 0001
• Zander Kelley

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL = L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan [Nis92], pseudorandom generators with seedlength O(log 2 n) were constructed (see also [INW94], [GR14]). Unfortunately, improving on this seed-length in general has proven challenging and seems to require new ideas. A recent line of inquiry (e. g. , [BV10], [GMR+12], [IMZ12], [RSV13], [SVW14], [HLV17], [LV17], [CHRT17]) has suggested focusing on a particular limitation of the existing PRGs ([Nis92], [INW94], [GR14]), which is that they only fool roBPs when the variables are read in a particular known order, such as x 1 n. In comparison, existentially one can obtain logarithmic seed-length for fooling the set of polynomial-size roBPs that read the variables under any fixed unknown permutation x π(1) xπ(n). While recent works have established novel PRGs in this setting for subclasses of roBPs, there were no known n o(1) seed-length explicit PRGs for general polynomial-size roBPs in this setting. In this work, we follow the "bounded independence plus noise" paradigm of Haramaty, Lee and Viola [HLV17], [LV17], and give an improved analysis in the general roBP unknownorder setting. With this analysis we obtain an explicit PRG with seed-length O(log 3 n) for polynomial-size roBPs reading their bits in an unknown order. Plugging in a recent Fourier tail bound of Chattopadhyay, Hatami, Reingold, and Tal [CHRT17], we can obtain a Õ(log 2 n) seed-length when the roBP is of constant width.