Follow
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
892013
Inapproximability of densest κ-subgraph from average case hardness
N Alon, S Arora, R Manokaran, D Moshkovitz, O Weinstein
Unpublished manuscript 1, 6, 2011
852011
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
762013
Faster dynamic matrix inverse for faster lps
S Jiang, Z Song, O Weinstein, H Zhang
arXiv preprint arXiv:2004.07470, 2020
592020
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
592014
A discrepancy lower bound for information complexity
M Braverman, O Weinstein
Algorithmica 76 (3), 846-864, 2016
532016
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
502017
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
462019
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
362019
Training (overparametrized) neural networks in near-linear time
J Brand, B Peng, Z Song, O Weinstein
arXiv preprint arXiv:2006.11648, 2020
342020
Direct product via round-preserving compression
M Braverman, A Rao, O Weinstein, A Yehudayoff
International Colloquium on Automata, Languages, and Programming, 232-243, 2013
342013
Information lower bounds via self-reducibility
M Braverman, A Garg, D Pankratov, O Weinstein
Theory of Computing Systems 59 (2), 377-396, 2016
312016
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
312014
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
282015
An interactive information odometer and applications
M Braverman, O Weinstein
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing …, 2015
282015
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
282012
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
262019
On the communication complexity of approximate fixed points
T Roughgarden, O Weinstein
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
222016
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
212012
The simultaneous communication of disjointness with applications to data streams
O Weinstein, DP Woodruff
International Colloquium on Automata, Languages, and Programming, 1082-1093, 2015
192015
The system can't perform the operation now. Try again later.
Articles 1–20