Arrow Research search

Author name cluster

OMRI WEINSTEIN

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

ICML Conference 2025 Conference Paper

Discrepancy Minimization in Input-Sparsity Time

  • Yichuan Deng 0002
  • Xiaoyu Li
  • Zhao Song 0002
  • Omri Weinstein

A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal’s SDP algorithm for finding a coloring $x \in \\{-1, 1\\}^n$ that approximately minimizes the discrepancy $\mathrm{disc}(A, x): = \\|{A} x \\|_{\infty}$ of a real-valued $m \times n$ matrix $A$. Larsen’s algorithm runs in $\widetilde{O}(mn^2)$ time compared to Bansal’s $\widetilde{O}(mn^{4. 5})$-time algorithm, with a slightly weaker logarithmic approximation ratio in terms of the hereditary discrepancy of $A$ [Bansal, FOCS 2010]. We present a combinatorial $\widetilde{O}(\mathrm{nnz}(A) + n^3)$-time algorithm with the same approximation guarantee as Larsen’s, optimal for tall matrices where $m = \mathrm{poly}(n)$. Using a more intricate analysis and fast matrix multiplication, we further achieve a runtime of $\widetilde{O}(\mathrm{nnz}(A) + n^{2. 53})$, breaking the cubic barrier for square matrices and surpassing the limitations of linear-programming approaches [Eldan and Singh, RS&A 2018]. Our algorithm relies on two key ideas: (i) a new sketching technique for finding a projection matrix with a short $\ell_2$-basis using implicit leverage-score sampling, and (ii) a data structure for efficiently implementing the iterative Edge-Walk partial-coloring algorithm [Lovett and Meka, SICOMP 2015], and using an alternative analysis to enable “lazy” batch updates with low-rank corrections. Our results nearly close the computational gap between real-valued and binary matrices, for which input-sparsity time coloring was recently obtained by [Jain, Sah and Sawhney, SODA 2023].

Details

FOCS Conference 2023 Conference Paper

Quartic Samples Suffice for Fourier Interpolation

  • Zhao Song 0002
  • Baocheng Sun 0002
  • Omri Weinstein
  • Ruizhe Zhang 0001

We study the problem of interpolating a noisy Fourier-sparse signal in the time duration $[0, T]$ from noisy samples in the same range, where the ground truth signal can be any k-Fourier-sparse signal with band-limit $[-F, F]$. Our main result is an efficient Fourier Interpolation algorithm that improves the previous best algorithm by [Chen, Kane, Price, and Song, FOCS 2016] in the following three aspects: •The sample complexity is improved from $\widetilde{O}\left(k^{51}\right)$ to $\widetilde{O}\left(k^{4}\right)$. •The time complexity is improved from $\widetilde{O}\left(k^{10 \omega+40}\right)$ to $\widetilde{O}\left(k^{4 \omega}\right)$. •The output sparsity is improved from $\widetilde{O}\left(k^{10}\right)$ to $\widetilde{O}\left(k^{4}\right)$. Here, $\omega$ denotes the exponent of fast matrix multiplication. The state-of-the-art sample complexity of this problem is $\sim k^{4}$, but was only known to be achieved by an exponential-time algorithm. Our algorithm uses the same number of samples but has a polynomial runtime, laying the groundwork for an efficient Fourier Interpolation algorithm. The centerpiece of our algorithm is a new spectral analysis tool-the Signal Equivalent Method-which utilizes the structure of Fourier signals to establish nearly-optimal energy properties, and is the key for efficient and accurate frequency estimation. We use this method, along with a new sufficient condition for frequency recovery (a new high SNR band condition), to design a cheap algorithm for estimating “significant” frequencies within a narrow range. Together with a signal estimation algorithm, we obtain a new Fourier Interpolation algorithm for reconstructing the ground-truth signal.

Details

FOCS Conference 2023 Conference Paper

The Complexity of Dynamic Least-Squares Regression

  • Shunhua Jiang
  • Binghui Peng
  • Omri Weinstein

We settle the complexity of dynamic least-squares regression (LSR), where rows and labels $\left(\mathbf{A}^{(t)}, \mathbf{b}^{(t)}\right)$ can be adaptively inserted and/or deleted, and the goal is to efficiently maintain an $\epsilon$-approximate solution to $\min _{\mathbf{x}^{(t)}}\left\|\mathbf{A}^{(t)} \mathbf{x}^{(t)}-\mathbf{b}^{(t)}\right\|_{2}$ for all $t \in[T]$. We prove sharp separations $\left(d^{2-o(1)}\right. $ vs. $\left. \sim d\right)$ between the amortized update time of: (i) Fully vs. Partially dynamic 0. 01-LSR; (ii) High vs. low-accuracy LSR in the partially-dynamic (insertion-only) setting. Our lower bounds follow from a gap-amplification reduction–reminiscent of iterative refinement-from the exact version of the Online Matrix Vector Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where the i-th online product $\mathrm{Hv}^{(i)}$ only needs to be computed to 0. 1 -relative error. All previous fine-grained reductions from OMv to its approximate versions only show hardness for inverse polynomial approximation $\epsilon=$ $n^{-\omega(1)}$ (additive or multiplicative). This result is of independent interest in fine-grained complexity and for the investigation of the OMv Conjecture, which is still widely open.

Details

NeurIPS Conference 2022 Conference Paper

Fast Distance Oracles for Any Symmetric Norm

  • Yichuan Deng
  • Zhao Song
  • OMRI WEINSTEIN
  • Ruizhe Zhang

In the \emph{Distance Oracle} problem, the goal is to preprocess $n$ vectors $x_1, x_2, \cdots, x_n$ in a $d$-dimensional normed space $(\mathbb{X}^d, \| \cdot \|_l)$ into a cheap data structure, so that given a query vector $q \in \mathbb{X}^d$, all distances $\| q - x_i \|_l$ to the data points $\{x_i\}_{i\in [n]}$ can be quickly approximated (faster than the trivial $\sim nd$ query time). This primitive is a basic subroutine in machine learning, data mining and similarity search applications. In the case of $\ell_p$ norms, the problem is well understood, and optimal data structures are known for most values of $p$. Our main contribution is a fast $(1\pm \varepsilon)$ distance oracle for \emph{any symmetric} norm $\|\cdot\|_l$. This class includes $\ell_p$ norms and Orlicz norms as special cases, as well as other norms used in practice, e. g. top-$k$ norms, max-mixture and sum-mixture of $\ell_p$ norms, small-support norms and the box-norm. We propose a novel data structure with $\tilde{O}(n (d + \mathrm{mmc}(l)^2 ) )$ preprocessing time and space, and $t_q = \tilde{O}(d + n \cdot \mathrm{mmc}(l)^2)$ query time, where $\mathrm{mmc}(l)$ is a complexity-measure (modulus) of the symmetric norm under consideration. When $l = \ell_{p}$, this runtime matches the aforementioned state-of-art oracles.

PDF Details

STOC Conference 2021 Conference Paper

A faster algorithm for solving general LPs

  • Shunhua Jiang
  • Zhao Song 0002
  • Omri Weinstein
  • Hengjie Zhang

The fastest known LP solver for general (dense) linear programs is due to [Cohen, Lee and Song’19] and runs in O * ( n ω + n 2.5−α/2 + n 2+1/6 ) time. A number of follow-up works [Lee, Song and Zhang’19, Brand’20, Song and Yu’20] obtain the same complexity through different techniques, but none of them can go below n 2+1/6 , even if ω=2. This leaves a polynomial gap between the cost of solving linear systems ( n ω ) and the cost of solving linear programs, and as such, improving the n 2+1/6 term is crucial toward establishing an equivalence between these two fundamental problems. In this paper, we reduce the running time to O * ( n ω + n 2.5−α/2 + n 2+1/18 ) where ω and α are the fast matrix multiplication exponent and its dual. Hence, under the common belief that ω ≈ 2 and α ≈ 1, our LP solver runs in O * ( n 2.055 ) time instead of O * ( n 2.16 ).

Details

FOCS Conference 2020 Conference Paper

An Adaptive Step Toward the Multiphase Conjecture

  • Young Kun-Ko
  • Omri Weinstein

In 2010, Pătraşcu 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. He conjectured that any data structure for the Multiphase problem must make $n^{\epsilon}$ cell-probes in either update or query phases, and showed that this would imply similar unconditional lower bounds on many important dynamic data structure problems. There has been almost no progress on this conjecture in the past decade since its introduction. We show an $\tilde{\Omega}(\sqrt{n})$ cell-probe lower bound on the Multiphase problem for data structures with general (adaptive) updates, and queries with unbounded but “layered” adaptivity. This result captures all known set-intersection data structures and significantly strengthens previous Multiphase lower bounds, which only captured non-adaptive data structures. Our main technical result is a communication lower bound on a 4-party variant of Pătraşcu's Number-On-Forehead Multiphase game, using information complexity techniques. We then use this result to make progress on understanding the power of nonlinear gates in networks computing linear operators, a long-standing open problem in circuit complexity and network design: We show that any depth- $d$ circuit that computes a random $m\times n$ linear operator $x\mapsto Ax$ using gates of degree $k$ (width- $k$ DNFs) must have $\Omega(m\cdot n^{1/2(d+k)})$ wires. Finally, we show that a lower bound on Pătraşcu's original NOF game would imply a polynomial wire lower bound $(n^{1+\Omega(1/d)})$ for circuits with arbitrary gates computing a random linear operator. This suggests that the NOF conjecture is much stronger than its data structure counterpart.

Details

SODA Conference 2020 Conference Paper

How to Store a Random Walk

  • Emanuele Viola
  • Omri Weinstein
  • Huacheng Yu

Motivated by storage applications, we study the following data structure problem: an encoder wishes to store a collection of jointly-distributed files: = ( X 1, X 2, …, X n ) ∼ µ which are correlated ( H µ ( ) ≤ Σ i H µ ( X i )), using as little (expected) memory as possible, such that each individual file X i can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pǎtraşcu (FOCS’08) and subsequently by Dodis, Pǎtraşcu and Thorup (STOC’10) shows that it is possible to store using just a constant number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each X i in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least Ω( n /poly lg n ) extra bits for constant decoding time, even for “simple” joint distributions µ. We focus on the natural case of compressing Markov chains, i. e. , storing a length- n random walk on any (possibly directed) graph G. Denoting by κ ( G, n ) the number of length- n walks on G, we show that there is a succinct data structure storing a random walk using lg 2 κ ( G, n ) + O (lg n ) bits of space, such that any vertex along the walk can be decoded in O (1) time on a word-RAM. If the graph is strongly connected (e. g. , undirected), the space can be improved to only lg 2 k ( G, n ) + 5 extra bits. For the harder task of matching the point-wise optimal space of the walk, i. e. , the empirical entropy, we present a data structure with O (1) extra bits at the price of O (lg n ) decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the online version of the problem with constant update and query time.

Details

FOCS Conference 2020 Conference Paper

Polynomial Data Structure Lower Bounds in the Group Model

  • Alexander Golovnev
  • Gleb Posobin
  • Oded Regev 0001
  • Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial (n Ω(1) ) lower bound for an explicit range counting problem of n 3 convex polygons in \mathbbR 2 (each with n Õ̃(1) facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing-in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k=n 1-δ ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

Details

STOC Conference 2019 Conference Paper

Local decodability of the Burrows-Wheeler transform

  • Sandip Sinha
  • Omri Weinstein

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a 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 of the bzip compression program. Alas, the decoding process of BWT is inherently sequential and requires Ω( n ) time even to retrieve a single character. We study the succinct data structure problem of locally decoding short substrings of a given text under its compressed BWT, i.e., with small additive redundancy r over the Move-To-Front ( bzip ) compression. The celebrated BWT-based FM-index (FOCS ’00), as well as other related literature, yield a trade-off of r =Õ( n /√ t ) bits, when a single character is to be decoded in O ( t ) time. We give a near-quadratic improvement r =Õ( n lg( t )/ t ). As a by-product, we obtain an exponential (in t ) improvement on the redundancy of the FM-index for counting pattern-matches on compressed text. In the interesting regime where the text compresses to o ( n ) (say, n /polylg( n )) bits, these results provide an exp( t ) overall space reduction. For the local decoding problem of BWT, we also prove an Ω( n / t 2 ) cell-probe lower bound for “symmetric” data structures. We achieve our main result by designing a compressed partial-sums (Rank) data structure over BWT. The key component is a locally-decodable Move-to-Front (MTF) code: with only O (1) extra bits per block of length n Ω(1) , the decoding time of a single character can be decreased from Ω( n ) to O (lg n ). This result is of independent interest in algorithmic information theory.

Details

FOCS Conference 2016 Conference Paper

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

  • 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 Ω(n(log n/log log n)2) cell-probe lower bound for the dynamic 2D weighted orthogonal range counting problem (2D-ORC) with n/poly log n updates and n queries, that holds even for data structures with exp(-Ω̃(n)) success probability. This result not only proves the highest amortized lower bound to date, but is also tight in the strongest possible sense, as a matching upper bound can be obtained by a deterministic data structure with worst-case operational time. This is the first demonstration of a "sharp threshold" phenomenon for dynamic data structures. Our broader motivation is that cell-probe lower bounds for exponentially small success facilitate reductions from dynamic to static data structures. As a proof-of-concept, we show that a slightly strengthened version of our lower bound would imply an Ω((log n/log log n)2) lower bound for the static 3D-ORC problem with O(n logO(1) n) space. Such result would give a near quadratic improvement over the highest known static cell-probe lower bound, and break the long standing Ω(log n) barrier for static data structures.

Details

FOCS Conference 2016 Conference Paper

On the Communication Complexity of Approximate Fixed Points

  • 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 o f: [0, 1] n → [0, 1] n, where Alice holds f and Bob holds g. We prove an exponential (in n) lower bound on the deterministic communication complexity of this problem. Our technical approach is to adapt the Raz-McKenzie simulation theorem (FOCS 1999) into geometric settings, thereby "smoothly lifting" the deterministic query lower bound for finding an approximate fixed point (Hirsch, Papadimitriou and Vavasis, Complexity 1989) from the oracle model to the two-party model. Our results also suggest an approach to the well-known open problem of proving strong lower bounds on the communication complexity of computing approximate Nash equilibria. Specifically, we show that a slightly "smoother" version of our fixed-point computation lower bound (by an absolute constant factor) would imply that: The deterministic two-party communication complexity of finding an ∈ = Ω(1/log 2 N)-approximate Nash equilibrium in an N × N bimatrix game (where each player knows only his own payoff matrix) is at least N γ for some constant γ > 0. (In contrast, the nondeterministic communication complexity of this problem is only O(log 6 N)). ; The deterministic (Number-In-Hand) multiparty communication complexity of finding an ∈ = Ω(1)-Nash equilibrium in a k-player constant-action game is at least 2 Ω(k/log k) (while the nondeterministic communication complexity is only O(k)).

Details

STOC Conference 2015 Conference Paper

An Interactive Information Odometer and Applications

  • 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-theoretic privacy. As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If I bits of information are required for solving a single copy of f under μ with probability 2/3, then any protocol attempting to solve n independent copies of f under μ n using o(n • I) communication, will succeed with probability 2 -Ω(n) . This is tight, as Braverman and Rao [BR11] previously showed that O(n • I) communication suffice to succeed with probability ~(2/3) n . We then show how the information odometer can be used to achieve the best possible information-theoretic privacy between two untrusted parties: If the players' goal is to compute a function f(x,y), and f admits a protocol with information cost is I and communication cost C, then our odometer can be used to produce a "robust" protocol which: (i) Assuming both players are honest, computes f with high probability, and (ii) Even if one party is malicious, then for any k∈N, the probability that the honest player reveals more than O(k • (I+log C)) bits of information to the other player is at most 2 -Ω(k) . Finally, we outline an approach which uses the odometer as a proxy for breaking state of the art interactive compression results: We show that our odometer allows to reduce interactive compression to the regime where I=O(log C), thereby opening a potential avenue for improving the compression result of [BBCR10] and to new direct sum and product theorems in communication complexity.

Details

SODA Conference 2015 Conference Paper

Approximating the best Nash Equilibrium in n o (log n ) -time breaks the Exponential Time Hypothesis

  • 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 approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O (log n ) in the random graph ( n, 1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it would imply a 2 Õ ( n 1/2) algorithm for SAT. Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games, the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications.

Details

FOCS Conference 2015 Conference Paper

Welfare Maximization with Limited Interaction

  • 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, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n 1/(r+1) -approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is n ε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n 1/5r+1), implying an Ω(log log n) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

Details

STOC Conference 2014 Conference Paper

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

  • Dmitry Gavinsky
  • Or Meir
  • Omri Weinstein
  • Avi Wigderson

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P ⊈ 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 first milestones toward proving super-polynomial circuit lower bounds. Karchmer, Raz, and Wigderson [21] suggested to approach this problem by proving the following conjecture: given two boolean functions f and g , the depth complexity of the composed function g o f is roughly the sum of the depth complexities of f and g . They showed that the validity of this conjecture would imply that P ⊈ NC 1 . As a starting point for studying the composition of functions, they introduced a relation called "the universal relation", and suggested to study the composition of universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [12]. An alternative proof was given later by Håstad and Wigderson [18]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open. In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it. Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations -- communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Details

FOCS Conference 2013 Conference Paper

Direct Products in Communication Complexity

  • Mark Braverman
  • Anup Rao 0001
  • 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 the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μ n be the product distribution on n inputs and f n denote the function that computes n copies of f on these inputs. We prove that if T log 3/2 T ≪ (C - 1)√n and suc(μ, f, C) n, f n, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log 2 T ≪ Cn, we must have suc(μ n, f n, T) ≤ exp(-Ω(n)).

Details