home|research|writing| courses|book |CS127  

Boaz Barak's photo Boaz Barak (In Hebrew: בועז ברק)
Gordon McKay Professor of Computer Science, Harvard John A. Paulson School of Engineering and Applied Sciences.

Email: (for Harvard related mails, please use )
Please use or for reference letter or manuscript review requests respectively.
(emails to these addresses are forwarded to my main inbox, but are also tagged appropriately so I don't lose track of them.)

Administrator: Kevin Doyle, 617-496-6257, Maxwell Dworkin 111A ,

Office hours (Spring 2016): Tuesdays 1-2:30pm.
During shopping week (Jan 24-30) I will have the following extended office hours if you want to talk to me: Monday (1/25) 2-3pm, Tuesday (1/26) 1pm-2:30pm, Thursday (1/28) 2pm-3pm, Friday (1/29) 2pm-3pm.

Mailing address: Boaz Barak, Harvard SEAS: Maxwell-Dworkin 329, 33 Oxford Street, Cambridge, MA 02138
Fax: (617) 496-6404 (please indicate my name)

About me: I am a professor of Computer Science at Harvard University, and a member of the Harvard SEAS Theory of Computing group. Previously, I was a principal researcher at Microsoft Research New England, and before that I was an associate professor (with tenure) at Princeton University's Computer Science department. I hold a Ph.D from the Weizmann Institute of Science, and was a postdoctoral fellow at the Institute for Advanced Study in Princeton. Current activities: I am on the program committee of the Highlights of Algorithms conference (Paris, summer 2016). I am a trustee of the Computational Complexity Foundation. 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 member of the Committee for the Advancement of Theoretical Computer Science (CATCS). I am a co organizer of the Harvard/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, Pravesh Kothari.

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

See also my curriculum vitae, brief bio and web pages for courses I have taught.

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

B. Barak, J. A. Kelner, and D. Steurer. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method , STOC 2015.
[ arxiv ]
A. Glaser, B. Barak, and R. J. Goldston. A zero-knowledge protocol for nuclear warhead verification . Nature, 510:497-502, 2014.
[ link ] See also this article by R. Stone (Science, June 2014) for a non technical overview.

B. Barak, J. Kelner, and D. Steurer. Rounding Sum-of-Squares Relaxations , STOC 2014.
[ 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 . SIAM Journal on Computing 42.3: 1327-1363 ,2913. Preliminary version in 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 ]