10 citations · 13 across the 7 of their papers we have counts for
4 papers · 1 filter
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 \cite{KelleyM2023strong}, Kelley, Lovett, and Meka \cite{KelleyLM2024-nof} constr…
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 , such that: (i)…
Random restrictions and PRGs for PTFs in Gaussian Space
Zander Kelley, Raghu Meka
A polynomial threshold function (PTF) is a function of the form where is a polynomial of degree at most …
Pseudorandom Generators for Read-Once Branching Programs, in any Order
Michael A. Forbes, 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 gener…