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 mainly interested in the interplay between information theory, complexity and data structures. I was a graduate student at Princeton University (2015), where I was lucky to have Mark Braverman as my advisor. Before joining Columbia, I was a Simons Society Junior Fellow at Courant Institute (NYU). Starting 2019, 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 .

Editorial Boards : Theory of Computing journal (ToC).

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

Students :

Gleb Posobin (PhD, 2018-)

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

Kevin Yeo (Part time with Google Research, 2018-)

 
 
Static Data Structure Lower Bounds Imply Rigidity,
with Zeev Dvir and Alexander Golovnev,
STOC'19 | [ECCC]
 
Local Decodability of the Burrows-Wheeler Transform,
with Sandip Sinha,
STOC'19 | [ECCC]
 
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]
 
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication,
with Huacheng Yu,
FOCS'16 | [ECCC]
 
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]
 
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]
 
An Interactive Information Odometer with Applications,,
with Mark Braverman,
STOC '15 |, | [ECCC]
 
Direct Products in Communication Complexity,
with Mark Brverman, Anup Rao and Amir Yehudayoff,
FOCS '13 | [ECCC]
 
PhD Thesis : Interactive Information Complexity and Applications | [link]
 
How to Store a Random Walk,
with Emanuele Viola and Huacheng Yu,
[ECCC] (Submitted)
 
Lower Bounds for Oblivious Near-Neighbor Search,
with Kasper Green Larsen, Tal Malkin and Kevin Yeo,
| [Arxiv] (Submitted)
 
Data Structure Lower Bounds Imply Rigidity,
with Zeev Dvir and Alexander Golovnev,
STOC'19 | [ECCC]
 
Local Decodability of the Burrows-Wheeler Transform,
with Sandip Sinha,
STOC'19 | [ECCC]
 
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs,
with Sepehr Assadi and Xiaorui Sun,
PODC'19 | [Arxiv]
 
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]
 
The Minrank of Random Graphs,
with Alexander Golovnev and Oded Regev,
IEEE Transactions on Information Theory (preliminary version in RANDOM'17) | [ECCC]
 
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication,
with Huacheng Yu,
FOCS'16 | [ECCC]
 
On the Communication Complexity of Approximate Fixed Points,
with Tim Roughgarden,
FOCS'16 | [ECCC]
 
An Improved Upper Bound for the Most Informative Boolean Function Conjecture
with Or Ordentlich and Ofer Shayevitz,
ISIT'16 | [ECCC]
 
Distributed Signaling Games
with Moran Feldman and Moshe Tennenholtz,
ESA'16 | [Arxiv]
 
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]
 
Welfare Maximization with Limited Interaction,
with Noga Alon, Noam Nisan and Ran Raz,
FOCS '15 | [ECCC]
 
The Simultaneous Communication of Disjointness with Applications to Data Streams,
with David P. Woodruff,
ICALP '15 [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]
 
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]
 
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]
 
Direct Products in Communication Complexity,
with Mark Brverman, Anup Rao and Amir Yehudayoff,
FOCS '13 | [ECCC]
 
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]
 
A Discrepancy Lower Bound for Information Complexity,
with Mark Braverman,
RANDOM '12 | [ECCC]
 
Information Lower Bounds via Self Reducibility,
with Mark Braverman, Ankit Garg and Denis Pankratov,
CSR '13 (Best paper award) | [ECCC]
 
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]
    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].