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. My main research interests lie in the intersection between information theory and theoretical computer science. I am particularly interested in applications of interactive communication and information theory to computational complexity, data-structures and economics. I was a graduate student 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 a a Simons Society Junior Fellowship, a Simons Graduate Award in TCS, and a Siebel scholarship.

My CV can be found here.

Program Committees : FOCS'17.

 
 
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,
with Kasper Green Larsen and Huacheng Yu,
 
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]
 
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]
 
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]
 
PhD Thesis : Interactive Information Complexity and Applications | [link]
 
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,
with Kasper Green Larsen and Huacheng Yu,
 
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,
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]
    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].