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 interactive communication and information theory, and their role in computational complexity, data-structures and economics. I was a graduate student in the Theory group at Princeton University (2015), where I was lucky to have Mark Braverman as my advisor. Before joining Columbia, I spent a year and a half at Courant Institute (NYU) as a Simons Society Junior Fellow, under the wise guidance of Oded Regev. Before all that, I got a B.Sc. in mathematics and computer science from Tel-Aviv University (2006-09). My research was previously supported by Simons Graduate Award in TCS, and a Siebel scholarship.

My CV can be found here.

The Minrank of Random Graphs,
with Alexander Golovnev and Oded Regev,
Submitted | [ECCC]
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication,
with Huacheng Yu,
FOCS'16 (to appear) | [ECCC]
On the Communication Complexity of Approximate Fixed Points,
with Tim Roughgarden,
FOCS'16 (to appear) | [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,
Submitted | [ECCC]
Welfare Maximization with Limited Interaction,
with Noga Alon, Noam Nisan and Ran Raz,
FOCS '15 (to appear) | [ECCC]
The Simultaneous Communication of Disjointness with Applications to Data Streams,
with David P. Woodruff,
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,
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]
    Data-Structure Lower Bounds Reading Group (Columbia, Fall '16)| [webepage].
    Reasoning About Computation (COS 340, Fall '12)| [webepage].
    Advanced Algorithms (COS 521, Fall '13)| [webepage].
    Computational Complexity (Spring '10)| [webepage].