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

__
TR23-124
| 24th August 2023
__

Zander Kelley, Shachar Lovett, Raghu Meka#### Explicit separations between randomized and deterministic Number-on-Forehead communication

__
TR21-047
| 26th March 2021
__

Zander Kelley, Raghu Meka#### Random restrictions and PRGs for PTFs in Gaussian Space

Revisions: 1

__
TR20-182
| 3rd December 2020
__

Zander Kelley#### An Improved Derandomization of the Switching Lemma

Revisions: 1

__
TR18-147
| 19th August 2018
__

Michael Forbes, Zander Kelley#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

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

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 >>>

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 \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 >>>

Zander Kelley, Raghu Meka

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 >>>

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 $\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 >>>

Michael 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 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 >>>