3 papers
cs.CC2025
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…
cs.DS2023
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…
cs.CC2018
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…