Publications

2015
Noga Alon, Nisan, Noam , Raz, Ran , and Weinstein, Omri . 2015. Welfare Maximization With Limited Interaction. In Ieee 56Th Annual Symposium On Foundations Of Computer Science, Focs 2015, Berkeley, Ca, Usa, 17-20 October, 2015, Pp. 1499–1512. IEEE Computer Society. doi:10.1109/FOCS.2015.95. Publisher's Version
Mark Braverman, Kun-Ko, Young , and Weinstein, Omri . 2015. Approximating The Best Nash Equilibrium In&Nbsp;$N^{O(Log N)}$-&Nbsp;Time Breaks The Exponential Time Hypothesis. In Proceedings Of The Twenty-Sixth Annual Acm-Siam Symposium On Discrete Algorithms, Soda 2015, San Diego, Ca, Usa, January 4-6, 2015, Pp. 970–982. SIAM. doi:10.1137/1.9781611973730.66. Publisher's Version
2014
Mark Braverman, Kun-Ko, Young , and Weinstein, Omri . 2014. Approximating The Best Nash Equilibrium In N\(^\Mboxo(Log N)\)-Time Breaks The Exponential Time Hypothesis. Electron. Colloquium Comput. Complex., 21, Pp. 92. . Publisher's Version
Moran Feldman, Tennenholtz, Moshe , and Weinstein, Omri . 2014. Display Advertising With Information Mediators. Corr, abs/1404.2861. . Publisher's Version
Mark Braverman and Weinstein, Omri . 2014. An Interactive Information Odometer With Applications. Electron. Colloquium Comput. Complex., 21, Pp. 47. . Publisher's Version
Dmitry Gavinsky, Meir, Or , Weinstein, Omri , and Wigderson, Avi . 2014. Toward Better Formula Lower Bounds: An Information Complexity Approach To The Krw Composition Conjecture. In Symposium On Theory Of Computing, Stoc 2014, New York, Ny, Usa, May 31 - June 03, 2014, Pp. 213–222. ACM. doi:10.1145/2591796.2591856. Publisher's Version
Shahar Dobzinski, Feldman, Michal , Talgam-Cohen, Inbal , and Weinstein, Omri . 2014. Welfare And Revenue Guarantees For Competitive Bundling Equilibrium. Corr, abs/1406.0576. . Publisher's Version
2013
Mark Braverman, Rao, Anup , Weinstein, Omri , and Yehudayoff, Amir . 2013. Direct Product Via Round-Preserving Compression. In Automata, Languages, And Programming - 40Th International Colloquium, Icalp 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, 7965:Pp. 232–243. Springer. doi:10.1007/978-3-642-39206-1\_20. Publisher's Version
Mark Braverman, Rao, Anup , Weinstein, Omri , and Yehudayoff, Amir . 2013. Direct Product Via Round-Preserving Compression. Electron. Colloquium Comput. Complex., 20, Pp. 35. . Publisher's Version
Mark Braverman, Rao, Anup , Weinstein, Omri , and Yehudayoff, Amir . 2013. Direct Products In Communication Complexity. In 54Th Annual Ieee Symposium On Foundations Of Computer Science, Focs 2013, 26-29 October, 2013, Berkeley, Ca, Usa, Pp. 746–755. IEEE Computer Society. doi:10.1109/FOCS.2013.85. Publisher's Version
Mark Braverman, Garg, Ankit , Pankratov, Denis , and Weinstein, Omri . 2013. From Information To Exact Communication. In Symposium On Theory Of Computing Conference, Stoc'13, Palo Alto, Ca, Usa, June 1-4, 2013, Pp. 151–160. ACM. doi:10.1145/2488608.2488628. Publisher's Version
Mark Braverman, Garg, Ankit , Pankratov, Denis , and Weinstein, Omri . 2013. Information Lower Bounds Via Self-Reducibility. In Computer Science - Theory And Applications - 8Th International Computer Science Symposium In Russia, Csr 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings, 7913:Pp. 183–194. Springer. doi:10.1007/978-3-642-38536-0\_16. Publisher's Version
Dmitry Gavinsky, Meir, Or , Weinstein, Omri , and Wigderson, Avi . 2013. Toward Better Formula Lower Bounds: An Information Complexity Approach To The Krw Composition Conjecture. Electron. Colloquium Comput. Complex., 20, Pp. 190. . Publisher's Version
2012
Dana Ron, Rubinfeld, Ronitt , Safra, Muli , Samorodnitsky, Alex , and Weinstein, Omri . 2012. Approximating The Influence Of Monotone Boolean Functions In O(\(\Surd\)N) Query Complexity. Acm Trans. Comput. Theory, 4, 4, Pp. 11:1–11:12. doi:10.1145/2382559.2382562. Publisher's Version
Mark Braverman, Rao, Anup , Weinstein, Omri , and Yehudayoff, Amir . 2012. Direct Products In Communication Complexity. Electron. Colloquium Comput. Complex., 19, Pp. 143. . Publisher's Version
Mark Braverman and Weinstein, Omri . 2012. A Discrepancy Lower Bound For Information Complexity. In Approximation, Randomization, And Combinatorial Optimization. Algorithms And Techniques - 15Th International Workshop, Approx 2012, And 16Th International Workshop, Random 2012, Cambridge, Ma, Usa, August 15-17, 2012. Proceedings, 7408:Pp. 459–470. Springer. doi:10.1007/978-3-642-32512-0\_39. Publisher's Version
Mark Braverman, Garg, Ankit , Pankratov, Denis , and Weinstein, Omri . 2012. From Information To Exact Communication. Electron. Colloquium Comput. Complex., 19, Pp. 171. . Publisher's Version
Mark Braverman, Garg, Ankit , Pankratov, Denis , and Weinstein, Omri . 2012. Information Lower Bounds Via Self-Reducibility. Electron. Colloquium Comput. Complex., 19, Pp. 177. . Publisher's Version
Zohar Shay Karnin, Liberty, Edo , Lovett, Shachar , Schwartz, Roy , and Weinstein, Omri . 2012. Unsupervised Svms: On The Complexity Of The Furthest Hyperplane Problem. In Colt 2012 - The 25Th Annual Conference On Learning Theory, June 25-27, 2012, Edinburgh, Scotland, 23:Pp. 2.1–2.17. JMLR.org. . Publisher's Version
2011
Dana Ron, Rubinfeld, Ronitt , Safra, Muli , and Weinstein, Omri . 2011. Approximating The Influence Of A Monotone Boolean Function In O(\Textbackslashsqrt\N\) Query Complexity. Corr, abs/1101.5345. . Publisher's Version