All reports by Author Omri Weinstein:

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

__
TR19-144
| 29th October 2019
__

Young Ko, Omri Weinstein#### An Adaptive Step Toward the Multiphase Conjecture

Revisions: 1

__
TR19-055
| 9th April 2019
__

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo#### Lower Bounds for Oblivious Near-Neighbor Search

__
TR18-188
| 7th November 2018
__

Zeev Dvir, Alexander Golovnev, Omri Weinstein#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

__
TR18-141
| 6th August 2018
__

Sandip Sinha, Omri Weinstein#### Local Decodability of the Burrows-Wheeler Transform

Revisions: 1

__
TR17-047
| 10th March 2017
__

Kasper Green Larsen, Omri Weinstein, Huacheng Yu#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

__
TR16-110
| 19th July 2016
__

Alexander Golovnev, Oded Regev, Omri Weinstein#### The Minrank of Random Graphs

Revisions: 1

__
TR16-055
| 11th April 2016
__

Tim Roughgarden, Omri Weinstein#### On the Communication Complexity of Approximate Fixed Points

__
TR16-054
| 11th April 2016
__

Omri Weinstein, Huacheng Yu#### Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

__
TR15-084
| 21st May 2015
__

Or Ordentlich, Ofer Shayevitz, Omri Weinstein#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

__
TR15-083
| 14th May 2015
__

Omri Weinstein, David Woodruff#### The Simultaneous Communication of Disjointness with Applications to Data Streams

Revisions: 1

__
TR15-074
| 29th April 2015
__

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

__
TR15-060
| 14th April 2015
__

Omri Weinstein#### Information Complexity and the Quest for Interactive Compression

Revisions: 1

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR14-092
| 22nd July 2014
__

Mark Braverman, Young Kun Ko, Omri Weinstein#### Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

__
TR14-047
| 8th April 2014
__

Mark Braverman, Omri Weinstein#### An Interactive Information Odometer with Applications

Revisions: 1

__
TR13-190
| 28th December 2013
__

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR12-177
| 19th December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### Information lower bounds via self-reducibility

__
TR12-171
| 3rd December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### From Information to Exact Communication

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR11-164
| 9th December 2011
__

Mark Braverman, Omri Weinstein#### A discrepancy lower bound for information complexity

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

Young Ko, Omri Weinstein

In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving $polynomial$ lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make $n^\epsilon$ cell-probes in either the update or query phase, ... more >>>

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

Zeev Dvir, Alexander Golovnev, Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

Sandip Sinha, Omri Weinstein

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a \emph{reversible} preprocessing step that rearranges an $n$-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis for the ubiquitous \texttt{bzip} program. ... more >>>

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ...
more >>>

Alexander Golovnev, Oded Regev, Omri Weinstein

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

Tim Roughgarden, Omri Weinstein

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition

of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an

exponential (in $n$) lower bound on the deterministic ...
more >>>

Omri Weinstein, Huacheng Yu

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic

data structure problems. We introduce a new randomized nondeterministic four-party communication model

that enables "accelerated", error-preserving simulations of dynamic data structures.

We use this technique to prove an $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe ... more >>>

Or Ordentlich, Ofer Shayevitz, Omri Weinstein

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... more >>>

Omri Weinstein, David Woodruff

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>>

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

Omri Weinstein

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model

where agent's valuations are unknown to the central planner, and therefore communication is required to determine an

efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ...
more >>>

Mark Braverman, Young Kun Ko, Omri Weinstein

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game

initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

Mark Braverman, Omri Weinstein

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, ... more >>>

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We obtain a strong direct product theorem for two-party bounded round communication complexity.

Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses

at most C bits of communication in computing f(x,y) when (x,y)~\mu.

Jain et al. [JPY12] have recently showed that if

more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform ... more >>>

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(?,f,C) denote the maximum success probability of a 2-party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>

Mark Braverman, Omri Weinstein

This paper provides the first general technique for proving information lower bounds on two-party

unbounded-rounds communication problems. We show that the discrepancy lower bound, which

applies to randomized communication complexity, also applies to information complexity. More

precisely, if the discrepancy of a two-party function $f$ with respect ...
more >>>