10 citations · 13 across the 7 of their papers we have counts for
9 papers
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…
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…
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)…
Strong Bounds for 3-Progressions
Zander Kelley, Raghu Meka
We show that for some constant , any subset of integers of size at least contains a non-trivial three-term arithmetic progre…
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…
Doppelgangers: the Ur-Operation and Posets of Bounded Height
Thomas Browning, Max Hopkins, Zander Kelley
In the early 1970's, Richard Stanley and Kenneth Johnson introduced and laid the groundwork for studying the order polynomial of partially ordered sets (posets). Decades later, Ham…
Roots of Sparse Polynomials over a Finite Field
Zander Kelley
For a -nomial , we show that the number of distinct, nonzero roots of is bounded above by $2 (q-1)^{1-\varepsilon} C^\…
Estimating the Number Of Roots of Trinomials over Finite Fields
Zander Kelley, Sean Owen
We show that univariate trinomials can have at most distinct roots in …