Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Zander Kelley:

TR23-180 | 17th November 2023
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

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 can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a ... more >>>

TR23-124 | 24th August 2023
Zander Kelley, Shachar Lovett, Raghu Meka

Explicit separations between randomized and deterministic Number-on-Forehead communication

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 \to \{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 ... more >>>

TR21-047 | 26th March 2021
Zander Kelley, Raghu Meka

Random restrictions and PRGs for PTFs in Gaussian Space

Revisions: 1

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = sign(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address ... more >>>

TR20-182 | 3rd December 2020
Zander Kelley

An Improved Derandomization of the Switching Lemma

Revisions: 1

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 $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing ... more >>>

TR18-147 | 19th August 2018
Michael Forbes, Zander Kelley

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

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, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

ISSN 1433-8092 | Imprint