# Omri Weinstein

 Assistant Professor Department of Computer Science
500 West 120 Street, New York, NY 10027
 Email: omri(at)cs(dot)columbia(dot)edu

I am an assistant professor in the theoretical computer science group at Columbia University. I am broadly interested in the interplay between information theory, data structures and optimization, in particular, in the role (and limitations) of dynamic data structures and dimensionality-reduction techniques ("sketching'') in speeding up optimization and search. I was a graduate student at Princeton University and a Simons Society Junior Fellow at Courant Institute (NYU). My research is supported by an NSF CAREER Award on data structure lower bounds.

My CV can be found here.

Program Committees : FOCS'17 , STOC'20, ESA'21, ISIT'21 .

Editorial Boards : Theory of Computing journal (ToC).

News : Co-delivering the ICALP'18 Summer School on Data Strucutre Lower Bounds.

Students :

Hengjie Zhang (with Alex Andoni, 2019-)

Shunhua Jiang (with Alex Andoni, 2019-)

Gleb Posobin (2018-)

Victor Lecomte (MsC, 2019-2020, now at Stanford)

Alexander Golovnev (Postdoc, 2017-2018, now the Rabin fellow at Harvard)

Postdocs :

Alexander Golovnev (Postdoc, 2017-2018, now the Rabin fellow at Harvard)

 A Faster Algorithm for Solving General LPs, with Shunhua Jiang, Zhao Song, Hengjie Zhang, STOC'21 (to appear) | Arxiv Polynomial Data Structure Lower Bounds in the Group Model, with Gleb Posobin, Alexandr Golovnev, Oded Regev, FOCS'20 (Invited to SICOMP special issue ) | ECCC Static Data Structure Lower Bounds Imply Rigidity, with Zeev Dvir and Alexander Golovnev, STOC'19 | [ECCC] Invited extended talk at 2018 Simons Lower Bounds semester, [E.Viola's blog post] ) Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds, with Kasper Green Larsen and Huacheng Yu, STOC'18 (Invited to SICOMP special issue) | [ECCC] Invited TCS+ Talk, April 2017 On the Communication Complexity of Approximate Fixed Points, with Tim Roughgarden, FOCS'16 | [ECCC] Approximating the best Nash Equilibrium in $n^{o(log n)}$-time breaks the Exponential Time Hypothesis, with Mark Braverman and Young Kun Ko, SODA '15 | [ECCC] Invited TCS+ Talk, March 2017 Direct Products in Communication Complexity, with Mark Brverman, Anup Rao and Amir Yehudayoff, FOCS '13 | [ECCC] Invited TCS+ talk, February 2013 PhD Thesis : Interactive Information Complexity and Applications | [link]
 Training (Overparametrized) Neural Networks in Near-Linear Time, with Jan Van-der Brand, Bingui Peng, Zhao Song, ITCS'21 | Arxiv Faster Dynamic Matrix Inverse for Faster LPs, with Shunhua Jiang, Zhao Song, Hengjie Zhang, (submitted) | Arxiv Summary: Motivated by recent LP solvers, we design a novel dynamic data structure for maintaining the inverse of an n x n real matrix under \emph{low-rank} updates, with polynomially faster amortized running time. This data structure leads to the fastest known LP solver for general (dense) linear programs. Polynomial Data Structure Lower Bounds in the Group Model, with Gleb Posobin, Alexandr Golovnev, Oded Regev, FOCS'20 (Invited to SICOMP special issue ) | ECCC Summary: 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 lower bound on the query time of linear-space arithmetic data structures for an explicit range-counting problem of convex polygons in $\R^2$. An Adaptive Step Toward the Multiphase Conjecture, with Young Kun-Ko , FOCS'20 | Arxiv Summary: We develop a new tool in information complexity and use it to make progress on Patrascu's Multiphase Conjecture, proving a polynomial (~ $\sqrt\left\{n\right\}$) lower bound on weakly-adaptive dynamic data structures . Settling the Relationship of Wilber's Bounds for Dynamic Optimality, with Victor Lecomte , (ESA'20) | Arxiv Summary: We resolve a 35-year open question of Wilber on combinatorial lower bounds for online binary search trees, related to the long-standing Dynamic Optimality conjecture (Tarjan and Sleator, 1985). How to Store a Random Walk, with Emanuele Viola and Huacheng Yu, SODA'20 | Arxiv Summary: We study the problem of "locally-decodable" data compression of correlated data, and show that random walks can be stored close to their entropy, while facilitating constant-time decoding of any step on a word-RAM. Lower Bounds for Oblivious Near-Neighbor Search, with Kasper Green Larsen, Tal Malkin and Kevin Yeo, SODA'20 | [Arxiv] Summary: A quadratic improvement over the highest unconditional lower bound for oblivious (secure) near-neighbor search in dynamic settings. Data Structure Lower Bounds Imply Rigidity, with Zeev Dvir and Alexander Golovnev, STOC'19 | [ECCC] Summary: We prove a new relationship between additive and multiplicative low-rank factorizations of a matrix, and use it to show a new connection between static data structure lower bounds and matrix rigidity. Local Decodability of the Burrows-Wheeler Transform, with Sandip Sinha, Summary: We show how to compress strings using their BW transform so that each character can be decoded locally, and use our data structure to achieve an exponential speedup for compressed pattern-matching on strings. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs, with Sepehr Assadi and Xiaorui Sun, PODC'19 | [Arxiv] Summary: An exponentially faster parallel (MapReduce) algorithm for reachability on sparse expanding graphs. Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds, with Kasper Green Larsen and Huacheng Yu, STOC'18 (Invited to SICOMP special issue, Invited TCS+ talk)| [ECCC] Summary: The first super-logarithmic unconditional lower bound on dynamic decision problems, partially settling Patrascu's obituary question and the classic "range counting" problem in 2D. The Minrank of Random Graphs, with Alexander Golovnev and Oded Regev, IEEE Transactions on Information Theory (preliminary version in RANDOM'17) | [ECCC] Summary: We settle the problem of linear index coding over random knowledge graphs, by proving a tight (\Theta(n/lgn)) bound on the minrank of random Erdos-Renyi graphs. Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication, with Huacheng Yu, FOCS'16 | [ECCC] Summary: We develop a new techniques for proving amortized dynamic data structure lower bounds (through a new nondeterministic communication model), and use it to settle the complexity of dynamic weighted 2D range counting. On the Communication Complexity of Approximate Fixed Points, with Tim Roughgarden, FOCS'16 | [ECCC] Summary: We prove the first communication lower bounds on the 2-party problem of computing approximate fixed-points of a composition of two Lipschitz functions f*g. Our "geometric lifting" technique was subsequently used to settle the important open problem of distributed computation of approximate Nash equilibria. An Improved Upper Bound for the Most Informative Boolean Function Conjecture with Or Ordentlich and Ofer Shayevitz, ISIT'16 | [ECCC] Summary: We improve the previously best known lower bound on the highest "correlation" a Boolean function can have with a noisy binary string, relating hypercontractivity to mutual information. Distributed Signaling Games with Moran Feldman and Moshe Tennenholtz, ESA'16 | [Arxiv] Summary: We introduce a more realistic model of "signaling" in auctions where agents have knowledge on the underlying prior value. We design an equilibrium and a 5-approximation to revenue in a natural special class . Information Complexity and the Quest for Interactive Compression SIGACT News Complexity Column, June 2015 issue (invited survey) | [ECCC] ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness with Mark Braverman, Young Kun Ko and Aviad Rubinstein, SODA'16 | [ECCC] Summary: We give a tight ~n^log(n) lower bound for the problem of finding a dense subgraph in a graph containing a large clique (Feige&Seltser), using information-theoretic tools to analyze the birthday repetition" reduction. Welfare Maximization with Limited Interaction, with Noga Alon, Noam Nisan and Ran Raz, FOCS '15 | [ECCC] Summary: We prove that finding an approximate maximum matching in n-bidder games requires Omega(log log n) rounds of communication, the first super-constant lower bound for general (unbounded-round) communication. The Simultaneous Communication of Disjointness with Applications to Data Streams, with David P. Woodruff, ICALP '15 [ECCC] Summary: We settle the simultaneous communication complexity of multiparty (NIH) set disjointness and use it to prove an essentially tight lower bound on streaming frequency moments. Approximating the best Nash Equilibrium in $n^{o(log n)}$-time breaks the Exponential Time Hypothesis, with Mark Braverman and Young Kun Ko, SODA '15 (Invited TCS+ Talk) | [ECCC] Summary: We settle the problem of finding an approximately-optimal Nash equilibrium in 2-party games under the ETH conjecture, using a novel adaptation of the birthday repetition" technique in 2-prover free games" [AIM'13]. Welfare and Revenue Guarantees of Competitive Bundling Equilibrium, with Shahar Dobzinski, Michal Feldman and Inbal Talgam-Cohen, WINE '15 | [Arxiv] An Interactive Information Odometer with Applications,, with Mark Braverman, STOC '15 |, | [ECCC] Summary: We develop a novel interactive technique that allows two players to keep an online estimate of the internal information cost of their communication, and use it to settle the direct product problem for information complexity in terms of communication. Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture, with Dmitry Gavinsky, Or Meir and Avi Wigderson, STOC '14 (Invited to Algorithmica special issue) | [ECCC] Summary: We use information complexity techniques to give the first improvement in a decade for the important KRW conjecture (for separating P from NC1). Direct Products in Communication Complexity, with Mark Brverman, Anup Rao and Amir Yehudayoff, FOCS '13 (Invited TCS+ Talk) | [ECCC] Summary: We prove the first direct-product theorem for general two-party communication complexity. This black-box hardness amplification theorem was key to many subsequent lower bounds in complexity theory and streaming. Direct Product via Round-Preserving Compression, with Mark Brverman, Anup Rao and Amir Yehudayoff, ICALP '13 | [ECCC] From Information to Exact Communication, with Mark Braverman, Ankit Garg and Denis Pankratov, STOC '13 | [ECCC] Summary: We develop a framework for proving exact bounds on the 0-error information cost of communication problems, via martingale theory, and use it to settle the communication complexity of Set Disjointness (0.482n). A Discrepancy Lower Bound for Information Complexity, with Mark Braverman, RANDOM '12 | [ECCC] Summary: The first technique (in a line of subsequent works) for proving lower bounds on the information complexity of two-party randomized communication problems. Information Lower Bounds via Self Reducibility, with Mark Braverman, Ankit Garg and Denis Pankratov, CSR '13 (Best paper award) | [ECCC] Summary: 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). Unsupervised SVM's: On the Furthest Hyperplane Problem, with Zohar Karnin, Edo Liberty, Shachar Lovett, and Roy Schwartz, COLT '12 | [Arxiv] Approximating the Influence of a Monotone Boolean function in O(sqrt(n)) query complexity, with Dana Ron, Ronitt Rubinfeld, Alex Smorodinsky and Muli Safra, RANDOM '11 | [Arxiv] Inapproximabilty of Densest $k$-Subgraph from Average Case Hardness, with Noga Alon, Sanjeev Arora, Rajsekar Manokaran and Dana Moshkovitz, PhD Thesis : Interactive Information Complexity and Applications | [link]
 Information Theory in TCS (COMSE 6998-004) (Columbia, Fall '20) [webepage]. CS Theory (COMS 3261) (Columbia, Fall '19) [webepage]. Advanced Data Structures (COMSE 6998-008) (Columbia, Spring '19) [webepage]. Introduction to Complexity Theory (COMSE 4236) (Columbia, Fall '18) Information Theory In TCS (COMSE 6998) (Columbia, Fall '17)| [webepage]. Data-Structure Lower Bounds Reading Group (Columbia)| [webepage].