Omri Weinstein
Omri Weinstein
Assistant Professor, Columbia University
Verified email at cs.columbia.edu
Title
Cited by
Cited by
Year
From information to exact communication
M Braverman, A Garg, D Pankratov, O Weinstein
Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013
872013
Inapproximability of densest κ-subgraph from average case hardness
N Alon, S Arora, R Manokaran, D Moshkovitz, O Weinstein
Unpublished manuscript 1, 2011
762011
Direct products in communication complexity
M Braverman, A Rao, O Weinstein, A Yehudayoff
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 746-755, 2013
712013
A discrepancy lower bound for information complexity
M Braverman, O Weinstein
Algorithmica 76 (3), 846-864, 2016
522016
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
M Braverman, YK Ko, O Weinstein
Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete …, 2014
522014
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
M Braverman, YK Ko, A Rubinstein, O Weinstein
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017
442017
Massively parallel algorithms for finding well-connected components in sparse graphs
S Assadi, X Sun, O Weinstein
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing …, 2019
362019
Faster dynamic matrix inverse for faster lps
S Jiang, Z Song, O Weinstein, H Zhang
arXiv preprint arXiv:2004.07470, 2020
352020
Direct product via round-preserving compression
M Braverman, A Rao, O Weinstein, A Yehudayoff
International Colloquium on Automata, Languages, and Programming, 232-243, 2013
352013
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
KG Larsen, O Weinstein, H Yu
SIAM Journal on Computing 49 (5), STOC18-323-STOC18-367, 2019
312019
Information lower bounds via self-reducibility
M Braverman, A Garg, D Pankratov, O Weinstein
Theory of Computing Systems 59 (2), 377-396, 2016
312016
An interactive information odometer and applications
M Braverman, O Weinstein
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing …, 2015
282015
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
D Gavinsky, O Meir, O Weinstein, A Wigderson
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
272014
Welfare maximization with limited interaction
N Alon, N Nisan, R Raz, O Weinstein
2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 1499-1512, 2015
262015
Static data structure lower bounds imply rigidity
Z Dvir, A Golovnev, O Weinstein
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019
232019
Unsupervised svms: On the complexity of the furthest hyperplane problem
Z Karnin, E Liberty, S Lovett, R Schwartz, O Weinstein
Conference on Learning Theory, 2.1-2.17, 2012
232012
On the communication complexity of approximate fixed points
T Roughgarden, O Weinstein
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
212016
Approximating the influence of monotone Boolean functions in O (√ n) query complexity
D Ron, R Rubinfeld, M Safra, A Samorodnitsky, O Weinstein
ACM Transactions on Computation Theory (TOCT) 4 (4), 1-12, 2012
202012
Amortized dynamic cell-probe lower bounds from four-party communication
O Weinstein, H Yu
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
172016
An improved upper bound for the most informative boolean function conjecture
O Ordentlich, O Shayevitz, O Weinstein
2016 IEEE International Symposium on Information Theory (ISIT), 500-504, 2016
172016
The system can't perform the operation now. Try again later.
Articles 1–20