All reports by Author Kaave Hosseini:

__
TR22-165
| 22nd November 2022
__

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley#### Separation of the factorization norm and randomized communication complexity

__
TR22-130
| 15th September 2022
__

Hamed Hatami, Kaave Hosseini, Xiang Meng#### A Borsuk-Ulam lower bound for sign-rank and its application

__
TR19-067
| 6th May 2019
__

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

Revisions: 1

__
TR18-169
| 18th September 2018
__

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev#### Optimality of Linear Sketching under Modular Updates

__
TR18-142
| 17th August 2018
__

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

__
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

__
TR18-015
| 25th January 2018
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett#### Pseudorandom Generators from Polarizing Random Walks

Revisions: 1
,
Comments: 1

__
TR16-044
| 21st March 2016
__

Kaave Hosseini, Shachar Lovett#### Structure of protocols for XOR functions

Revisions: 1

__
TR15-179
| 10th November 2015
__

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett#### Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate $\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger ... more >>>

Hamed Hatami, Kaave Hosseini, Xiang Meng

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... 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 >>>

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,

the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.

This improves upon the previous work ...
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 >>>

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

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

Kaave Hosseini, Shachar Lovett

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.

We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.

This relies on a novel technique ...
more >>>

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak" random source $X$ with min-entropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close ... more >>>