home|research|courses|book  

Boaz Barak's photo Boaz Barak (In Hebrew: בועז ברק)
Senior Researcher, Microsoft Research New England

Please use or for reference letter or manuscript review requests respectively.
(emails to these addresses are forwarded to my main inbox, but just tagged appropriately so I don't lose track of them.)
Please use focs2014chair@outlook.com for any FOCS '14 related correspondence.

Maling address: Boaz Barak,Microsoft, 1 Memorial Drive, Cambridge, MA 02142
Fax: (857) 453-6063 (please indicate my name)

About me: I joined Microsoft in the summer of 2010. Previously I was an associate professor (with tenure) at Princeton University's Computer Science department, and before that a member in the School of Math at the Institute for Advanced Study. I have a Ph.D from the Weizmann Institute of Science. Current activities: I am the program chair for the FOCS 2014 conference. I am teaching a mini-course on "Sum of Squares relaxations" in June 2014 as part of the Swedish Summer School in Computer Science. I am co organizing a September 2014 workshop on Semidefinite Optimization, Approximation and Applications in the Simons institute for the theory of Computing. I am on the editorial board of the Journal of the ACM, the Theory of Computing Journal (ToC) and the Electronic Colloquium of Computational Complexity. I am a co organizer of the MSR/MIT reading group. See my CV for past activities.   Former  students: Sharon Goldberg (co advised with Jennifer Rexford), David Xiao (co advised with Avi Wigderson), Mohammad Mahmoody, Moritz Hardt. Former postdocs: Benny Applebaum, Thomas Holenstein, Guy Rothblum.Former/current interns: Moritz Hardt, Jonah Sherman, Yuan Zhou, Li-Yang Tan , Aaron Sidford, Aaron Potechin

I wrote a textbook with Sanjeev Arora: Computational Complexity: A Modern Apprach.

See also my curicculum vitae and web pages for courses I have taught.

Selected papers (see also full list of publications and some (slightly) less technical writing)

 
A. Glaser, B. Barak, and R. J. Goldston. A zero-knowledge protocol for nuclear warhead verification . Nature, 510:497-502, 2014.
[ bib | link ] (See also this article by R. Stone for a non technical overview.)

B. Barak, J. Kelner, and D. Steurer. Rounding Sum-of-Squares Relaxations , STOC 2014.
[ bib | eccc ]

B. Barak, F. G. S. L. Brandao, A. W. Harrow, J. A. Kelner, D. Steurer, and Y. Zhou. Hypercontractivity, sum-of-squares proofs, and their applications . In STOC, pages 307-326, 2012.
[ arxiv ]

B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff. Fractional Sylvester-Gallai theorems . Proceedings of the National Academy of Sciences, 2012. Journal version of STOC '11 paper.
[ .pdf ]

S. Arora, B. Barak, and D. Steurer. Subexponential Algorithms for Unique Games and Related problems . In Proc. of FOCS, 2010.
[ powerpoint | .pdf ]

B. Applebaum, B. Barak, and A. Wigderson. Public Key Cryptography from Different Assumptions . In Proc. of STOC, 2010. Preliminary version as cryptology eprint report 2008/335 by Barak and Wigderson.
[ .pdf ]

B. Barak, M. Braverman, X. Chen, and A. Rao. How to compress interactive communication . In Proc. STOC, 2010.
[ .pdf ]

S. Arora, B. Barak, M. Brunnermeier, and R. Ge. Computational Complexity and Information Asymmetry in Financial Products . In Innovations in Computer Science (ICS) conference, 2010. A description of this work also appeared as a Communication of ACM research highlight
[ .pdf ]

B. Barak and M. Mahmoody-Ghidary. Merkle Puzzles are Optimal - an O(n2) attack on key exchange from a random oracle . In Proceedings of CRYPTO '09, 2009.
[ powerpoint | .pdf ]

S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford. Path-Quality Monitoring in the Presence of Adversaries . In Proceedings of SIGMETRICS 2008, 2008.
[ .pdf ]

B. Barak, A. Rao, R. Shaltiel, and A. Wigderson. 2-source dispersers for no (1) entropy, and Ramsey graphs beating the Frankl-Wilson construction . Annals of Mathematics, 176(3):1483-1543, 2012. Prelimninary version in STOC '06.
[ .pdf ]

B. Barak and A. Sahai. How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation . In Proc. 46th FOCS. IEEE, 2005.
[ powerpoint | .ps | .pdf ]

B. Barak. A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms . In Proc. of 6th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2002.
[ .ps ]

B. Barak. Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model . In Proc. 43rd FOCS. IEEE, 2002.
[ powerpoint | .pdf ]

B. Barak. How to go beyond the black-box simulation barrier . In Proc. 42nd FOCS, pages 106-115. IEEE, 2001.
[ powerpoint | .pdf ]

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs . J. ACM, 59(2):6, 2012. Preliminary version in CRYPTO 2001.
[ powerpoint | .pdf ]