All reports by Author Shachar Lovett:

__
TR23-203
| 15th December 2023
__

Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni#### Refuting approaches to the log-rank conjecture for XOR functions

__
TR23-180
| 17th November 2023
__

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka#### New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

__
TR20-156
| 22nd October 2020
__

Sankeerth Rao Karingula, Shachar Lovett#### Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

__
TR19-145
| 31st October 2019
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman#### XOR Lemmas for Resilient Functions Against Polynomials

__
TR19-110
| 23rd August 2019
__

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Improved bounds for the sunflower lemma

__
TR19-067
| 6th May 2019
__

Hamed Hatami, Kaave Hosseini, Shachar Lovett#### Sign rank vs Discrepancy

Revisions: 1

__
TR19-028
| 1st March 2019
__

Shachar Lovett, Noam Solomon, Jiapeng Zhang#### From DNF compression to sunflower theorems via regularity

Revisions: 1

__
TR18-206
| 3rd December 2018
__

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

Revisions: 1

__
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 Karingula#### Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 2

Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of ... more >>>

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

Sankeerth Rao Karingula, Shachar Lovett

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

A sunflower with $r$ petals is a collection of $r$ sets so that the

intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ...
more >>>

Hamed Hatami, Kaave Hosseini, Shachar Lovett

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.

In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ...
more >>>

Shachar Lovett, Noam Solomon, Jiapeng Zhang

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... more >>>

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 Karingula

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