Omri Weinstein

ASSISTANT PROFESSOR OF COMPUTER SCIENCE

523 S.W. Mudd

Omri Weinstein’s research lies in the intersection of theoretical computer science and information theory. His main thread of research is developing tools for understanding the minimum amount of resources (e.g., space, time, energy, communication) required for solving computational problems in various models of computation, in particular, proving unconditional lower bounds on such resources. This includes, for example, time-space tradeoffs for data structures, understanding the limitations of low-depth circuits, and proving lower bounds on the rate of convergence of markets to equilibrium.  The tools used in Weinstein’s work come primarily from the theory of interactive communication.  He has made basic contributions to the development of “Information Complexity”, an interactive analogue of Shannon’s information theory, and to its implications on the power and limits of parallel computation. 

Research Interests

Communication Complexity, Information Theory, Data Structure lower bounds, Computational Economics.

Weinstein received his BSc in mathematics and computer science from Tel-Aviv University and his PhD in computer science from Princeton University (2015). Before joining Columbia, he was a Simons society junior fellow at Courant institute. 

RESEARCH EXPERIENCE

  • Postdoctoral fellow, Courant Institute (NYU), 2015-2017

PROFESSIONAL EXPERIENCE

  • Program Committee FOCS’17.

HONORS & AWARDS

 

  • Simons Society Junior Fellowship, 2015. 

SELECTED PUBLICATIONS

  • Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication,with Huacheng Yu (FOCS 2016).
  • On the Communication Complexity of Approximate Fixed Points, with Tim Roughgarden (FOCS 2016).
  • Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis, with Mark Braverman and Young Kun Ko, (SODA 2015).
  • An Interactive Information Odometer with Applications, with Mark Braverman (STOC 2015).
  • Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture, with Dmitry Gavinsky, Or Meir and Avi Wigderson (STOC 2014).
  • Direct Products in Communication Complexity, with Mark Brverman, Anup Rao and Amir Yehudayoff (FOCS 2013). 
  • From Information to Exact Communication, with Mark Braverman, Ankit Garg and Denis Pankratov (STOC 2013). 
  • A Discrepancy Lower Bound for Information Complexity, with Mark Braverman (RANDOM 2012).