All reports by Author Shachar Lovett:

__
TR18-206
| 3rd December 2018
__

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals#### Equality Alone Does Not Simulate Randomness

__
TR18-155
| 8th September 2018
__

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

__
TR18-142
| 17th August 2018
__

Kaave Hosseini, Shachar Lovett#### A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

__
TR18-095
| 11th May 2018
__

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin#### Hardness Amplification for Non-Commutative Arithmetic Circuits

__
TR18-076
| 22nd April 2018
__

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao#### Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 1

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

Kaave Hosseini, Shachar Lovett

The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role

in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c

applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem

with effective bounds.

more >>>

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>