I am interested in all areas of theoretical computer science, particularly cryptography and computational complexity. Electronic versions of my papers are below. See also non-technical writing - surveys, presentations, including essays for a non-expert audience. You can also download my thesis Non-Black-Box Techniques in Cryptography (pdf, 186 pages, 1.9MB) and view a draft our my complexity textbook with Sanjeev Arora.

Boaz Barak's Publications

 

B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff. Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes . In STOC, 2011.
[ bib | .pdf ]

 

B. Barak, Y. Dodis, H. Krawczyk, O. Pereira, K. Pietrzak, F.-X. Standaert, and Y. Yu. Leftover Hash Lemma, Revisited . In CRYPTO, 2011.
[ bib | .pdf ]

 

S. Arora, B. Barak, M. Brunnermeier, and R. Ge. Computational complexity and information asymmetry in financial products . Commun. ACM, 54(5):101-107, 2011. See http://m.cacm.acm.org/magazines/2011/5/107705-computational-complexity-and-information-asymmetry-in-financial-products/fulltext.
[ bib ]

 

B. Barak, M. Hardt, T. Holenstein, and D. Steurer. Subsampling Mathematical Programs and Average-Case Complexity . In SODA, 2011.
[ bib | .pdf ]

 

S. Arora, B. Barak, and D. Steurer. Subexponential Algorithms for Unique Games and Related problems . In Proc. of FOCS, pages 563-572, 2010.
[ bib | 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, http://eprint.iacr.org/2008/335.
[ bib | .pdf ]

 

B. Barak, I. Haitner, D. Hofheinz, and Y. Ishai. Bounded Key-Dependent Message Security . In EUROCRYPT, 2010.
[ bib | www: ]

 

B. Barak, M. Braverman, X. Chen, and A. Rao. How to compress interactive communication . In Proc. STOC, 2010.
[ bib | .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.
[ bib | .pdf ]

 

B. Barak, A. Rao, R. Raz, R. Rosen, and R. Shaltiel. Strong Parallel Repetition Theorem for Free Projection Games . In Proceedings RANDOM 2009, page 365. Springer, 2009.
[ bib | .pdf ]

 

B. Barak, M. Hardt, and S. Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections . In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
[ bib | .pdf ]

 

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

 

B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer. Rounding Parallel Repetitions of Unique Games . In Proceedings of 49th FOCS, 2008.
[ bib | .pdf ]

 

B. Applebaum, B. Barak, and D. Xiao. On Basing Lower-Bounds for Learning on Worst-Case Assumptions . In Proceedings of 49th FOCS, 2008.
[ bib | .pdf ]

 

B. Barak, S. Goldberg, and D. Xiao. Protocols and Lower Bounds for Failure Localization in the Internet . In Proceedings of Eurocrypt 2008, 2008.
[ bib | .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.
[ bib | .pdf ]

 

B. Barak and O. Goldreich. Universal Arguments and their Applications . SIAM Journal on Computing, 38(5):1661-1694, 2008. Preliminary version in CCC' 02.
[ bib | powerpoint | .ps ]

 

B. Barak and M. Mahmoody-Ghidary. Lower bounds on signatures from symmetric primitives . In Proc. 48th Foundations of Computer Science (FOCS). IEEE, 2007.
[ bib | .pdf ]

 

B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release . In L. Libkin, editor, Proceedings of ACM PODS, pages 273-282. ACM, 2007.
[ bib | .pdf ]

 

B. Barak, M. Prabhakaran, and A. Sahai. Concurrent Non-Malleable Zero Knowledge . In Proc. 47th Foundations of Computer Science (FOCS). IEEE, 2006.
[ bib | .pdf ]

 

B. Barak, A. Rao, R. Shaltiel, and A. Wigderson. 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction . In Proc. 38th Symposium on Theory of Computing (STOC), pages 671-680. ACM, 2006.
[ bib | .ps ]

 

B. Barak, R. Impagliazzo, and A. Wigderson. Extracting Randomness Using Few Independent Sources . SIAM Journal on Computing, 36(4):1095-1118, 2006. Preliminary version in FOCS' 04.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, Y. Lindell, and S. Vadhan. Lower bounds for non-black-box zero knowledge . J. Comput. Syst. Sci, 72(2):321-391, 2006. Preliminary version in FOCS' 03.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak and S. Halevi. An architecture for robust pseudo-random generation and Applications to /dev/random . In ACM, editor, Proc. Computing and Communication Security (CCS), 2005.
[ bib | .ps | .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.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, R. Canetti, Y. Lindell, R. Pass, and T. Rabin. Secure Computation Without Authentication . In Crypto '05, 2005. LNCS Volume 3621.
[ bib | link ]

 

B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors . In Proc. 37th STOC. ACM, 2005.
[ bib | .ps | .pdf ]

 

B. Barak and Y. Lindell. Strict Polynomial-Time in Simulation and Extraction . SIAM Journal on Computing, 33(4):783-818, Aug. 2004. Extended abstract appeared in STOC 2002.
[ bib | link | .ps | .pdf ]

 

B. Barak. Non-Black-Box Techniques in Cryptography. PhD thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 2004.
[ bib ]

 

B. Barak, R. Canetti, J. B. Nielsen, and R. Pass. Universally Composable Protocols with Relaxed Set-Up Assumptions . In Proc. 45th FOCS, pages 186-195. IEEE, 2004.
[ bib | .ps | .pdf ]

 

B. Barak and R. Pass. On the Possibility of One-Message Weak Zero-Knowledge . In First Theory of Cryptography Conference (TCC), 2004.
[ bib | .ps | .pdf ]

 

B. Barak, R. Shaltiel, and E. Tromer. True Random Number Generators Secure in a Changing Environment . In Workshop on Cryptographic Hardware and Embedded Systems (CHES), number 2779 in LNCS, pages 166-180, 2003.
[ bib | powerpoint | .ps | .pdf ]

 

B. Barak, R. Shaltiel, and A. Wigderson. Computational analogues of entropy . In Proc. of 7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003. See erratum note in abstract.
[ bib | powerpoint | .pdf ]

 

B. Barak, S. J. Ong, and S. Vadhan. Derandomization in Cryptography . In Crypto '03, 2003.
[ bib | 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.
[ bib | .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. See also my thesis.
[ bib | powerpoint | .pdf ]

 

B. Barak. Delegateable Signatures . Technical report, 2001.
[ bib | .ps ]

 

B. Barak, O. Goldreich, S. Goldwasser, and Y. Lindell. Resettably-Sound Zero-Knowledge and its Applications . In Proc. 42nd FOCS, pages 116-125. IEEE, 2001.
[ bib | .ps ]

 

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

 

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahay, S. Vadhan, and K. Yang. On the (Im)possibility of Obfuscating Programs . In Crypto '01, pages 1-18, 2001. LNCS No. 2139.
[ bib | powerpoint | .ps ]

 

B. Barak, S. Halevi, A. Herzberg, and D. Naor. Clock Synchronization with Faults and Recoveries . In Proc. of 19th ACM Principles of Distributed Computing (PODC). ACM, 2000.
[ bib | .ps ]

 

B. Barak, A. Herzberg, D. Naor, and E. Shai. The Proactive Security Toolkit and Applications . In Proc. of 6^th ACM Conference on Computer and Communications Security (CCS). ACM, 1999.
[ bib | .ps ]

 

B. Barak, P. Raghavendra, and D. Steurer. Rounding Semidefinite Programming Hierarchies via Global Correlation . Submitted for publication.
[ bib | http ]

This file has been generated by bibtex2html 1.74