Building on the techniques behind the recent progress on the 3-term arithmetic progression problem [15], Kelley, Lovett, and Meka [14] constructed the first explicit 3-player function $f:[N]^{3} \rightarrow\{0,1\}$ that demonstrates a strong separation between randomized and (non-)deterministic NOF communication complexity. Specifically, their hard function can be solved by a randomized protocol sending $O(1)$ bits, but requires $\Omega\left(\log ^{1 / 3}(N)\right)$ bits of communication with a deterministic (or non-deterministic) protocol. We show a stronger $\Omega\left(\log ^{1 / 2}(N)\right)$ lower bound for their construction. To achieve this, the key technical advancement is an improvement to the sifting argument for grid norms of (somewhat dense) bipartite graphs. In addition to quantitative improvement, we qualitatively improve over [14] by relaxing the hardness condition: while [14] proved their lower bound for any function f that satisfies a strong two-sided pseudorandom condition, we show that a weak one-sided condition suffices. This is achieved by a new structural result for cylinder intersections (or, in graph-theoretic language, the set of triangles induced from a tripartite graph), showing that any small cylinder intersection can be efficiently covered by a sum of simple “slice” functions.

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ω) time, where ω<3; much work has gone into bringing ω closer to 2. Since then, a parallel line of work has sought comparably fast combinatorial algorithms but with limited success. The na'ive O(n3)-time algorithm was initially improved by a log2n factor [Arlazarov et al.; RAS’70], then by log2.25n [Bansal and Williams; FOCS’09], then by log3n [Chan; SODA’15], and finally by log4n [Yu; ICALP’15].

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 → {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 it requires sending about (logN)1/3 many bits. This exponentially improves upon the previously best-known such separation. At the core of our proof is an extension of a recent result on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.

We show that for some constant $\beta\gt0$, any subset A of integers $\{1, \ldots, N\}$ of size at least $2^{-O\left((\log N)^{\beta}\right)} \cdot N$ contains a non-trivial three-term arithmetic progression. Previously, three-term arithmetic progressions were known to exist only for sets of size at least $N /(\log N)^{1+c}$ for a constant $c\gt0$.Our approach is first to develop new analytic techniques for addressing some related questions in the finite-field setting and then to apply some analogous variants of these same techniques, suitably adapted for the more complicated setting of integers.

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = \mathsf{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 the question of designing pseudorandom generators (PRG) for polynomial threshold functions (PTFs) in the gaussian space: design a PRG that takes a seed of few bits of randomness and outputs a $n$-dimensional vector whose distribution is indistinguishable from a standard multivariate gaussian by a degree $d$ PTF. Our main result is a PRG that takes a seed of $d^{O(1)}\log ( n / \varepsilon)\log(1/\varepsilon)/\varepsilon^2$ random bits with output that cannot be distinguished from $n$-dimensional gaussian distribution with advantage better than $\varepsilon$ by degree $d$ PTFs. The best previous generator due to O'Donnell, Servedio, and Tan (STOC'20) had a quasi-polynomial dependence (i.e., seedlength of $d^{O(\log d)}$) in the degree $d$. Along the way we prove a few nearly-tight structural properties of restrictions of PTFs that may be of independent interest.

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 O(logm) random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC0-circuits.

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 [Nis92], pseudorandom generators with seedlength O(log2n) were constructed (see also [INW94], [GR14]). Unfortunately, improving on this seed-length in general has proven challenging and seems to require new ideas. A recent line of inquiry (e.g., [BV10], [GMR+12], [IMZ12], [RSV13], [SVW14], [HLV17], [LV17], [CHRT17]) has suggested focusing on a particular limitation of the existing PRGs ([Nis92], [INW94], [GR14]), which is that they only fool roBPs when the variables are read in a particular known order, such as x1n. In comparison, existentially one can obtain logarithmic seed-length for fooling the set of polynomial-size roBPs that read the variables under any fixed unknown permutation xπ(1)xπ(n). While recent works have established novel PRGs in this setting for subclasses of roBPs, there were no known no(1)seed-length explicit PRGs for general polynomial-size roBPs in this setting. In this work, we follow the "bounded independence plus noise" paradigm of Haramaty, Lee and Viola [HLV17], [LV17], and give an improved analysis in the general roBP unknownorder setting. With this analysis we obtain an explicit PRG with seed-length O(log3n) for polynomial-size roBPs reading their bits in an unknown order. Plugging in a recent Fourier tail bound of Chattopadhyay, Hatami, Reingold, and Tal [CHRT17], we can obtain a Õ(log2n) seed-length when the roBP is of constant width.