2017 (3)
The Complexity of Public-Key Cryptography. Barak, B. In 2017. Tutorial/survey in honor of Oded Goldreich 60th birthday.
The Complexity of Public-Key Cryptography [link]Paper   bibtex
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Barak, B.; Brakerski, Z.; Komargodski, I.; and Kothari, P. 2017. Submitted for publication, posted on ECCC and ePrint
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) [link] paper   bibtex
Quantum entanglement, sum of squares, and the log rank conjecture. Barak, B.; Kothari, P.; and Steurer, D. In STOC, 2017.
Quantum entanglement, sum of squares, and the log rank conjecture [link] paper   bibtex
  2016 (3)
Tensor Prediction, Rademacher Complexity and Random 3-XOR. Barak, B.; and Moitra, A. In COLT, 2016.
Tensor Prediction, Rademacher Complexity and Random 3-XOR [link] paper   bibtex
A nearly tight Sum-of-Squares lower bound for the Planted Clique problem. Barak, B.; Hopkins, S.; Kelner, J.; Kothari, P.; Moitra, A.; and Potechin, A. In FOCS, 2016.
A nearly tight Sum-of-Squares lower bound for the Planted Clique problem [link] paper   bibtex
Hopes, Fears, and Software Obfuscation. Barak, B. Communications of the ACM, 59(3): 88--96. 2016.
Hopes, Fears, and Software Obfuscation [link] paper   bibtex
  2015 (3)
Beating the random assignment on constraint satisfaction problems of bounded degree. Barak, B.; Moitra, A.; O'Donnell, R.; Raghavendra, P.; Regev, O.; Steurer, D.; Trevisan, L.; Vijayaraghavan, A.; Witmer, D.; and Wright, J. In RANDOM-APPROX, 2015.
Beating the random assignment on constraint satisfaction problems of bounded degree [link] eccc   bibtex
Sum of Squares Lower Bounds from Pairwise Independence. Barak, B.; Chan, S. O.; and Kothari, P. In STOC, 2015.
Sum of Squares Lower Bounds from Pairwise Independence [link] paper   bibtex
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. Barak, B.; Kelner, J. A.; and Steurer, D. In STOC, 2015.
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method [link] paper   bibtex
  2014 (6)
A zero-knowledge protocol for nuclear warhead verification. Glaser, A.; Barak, B.; and Goldston, R. J. Nature, 510: 497-502. 2014. See also article by R. Stone (Science, June 2014)
A zero-knowledge protocol for nuclear warhead verification [link] paper   bibtex
Sum-of-squares proofs and the quest toward optimal algorithms. Barak, B.; and Steurer, D. In Proceedings of International Congress of Mathematicians (ICM), 2014.
Sum-of-squares proofs and the quest toward optimal algorithms [link] paper   bibtex
Structure vs. Combinatorics in Computational Complexity. Barak, B. Bulletin of the European Association for Theoretical Computer Science, 112. 2014. Survey, also posted on Windows on Theory blog.
Structure vs. Combinatorics in Computational Complexity [link] paper   Structure vs. Combinatorics in Computational Complexity [link] blog   bibtex
Rounding sum-of-squares relaxations. Barak, B.; Kelner, J. A.; and Steurer, D. In STOC, pages 31-40, 2014.
Rounding sum-of-squares relaxations [link]Link   Rounding sum-of-squares relaxations [link] paper   bibtex
Obfuscation for Evasive Functions. Barak, B.; Bitansky, N.; Canetti, R.; Kalai, Y. T.; Paneth, O.; and Sahai, A. In TCC, pages 26-51, 2014.
Obfuscation for Evasive Functions [link] paper   bibtex
Protecting Obfuscation against Algebraic Attacks. Barak, B.; Garg, S.; Kalai, Y. T.; Paneth, O.; and Sahai, A. In EUROCRYPT, volume 8441, of Lecture Notes in Computer Science, pages 221-238, 2014. Springer
Protecting Obfuscation against Algebraic Attacks [link] paper   bibtex
  2013 (3)
Toward a Secure Inspection System for Nuclear Warhead Veri cation Without Information Barrier. Glaser, A.; Barak, B.; and Goldston, R. J. 2013. Presented at 54th Annual INMM (Institute of Nuclear Materials Management) meeting
bibtex
Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013. Barak, B.; Kindler, G.; and Steurer, D. In Kleinberg, R. D., editor(s), ITCS, pages 197-214, 2013. ACM
Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013 [pdf] paper   bibtex
How to Compress Interactive Communication. Barak, B.; Braverman, M.; Chen, X.; and Rao, A. SIAM J. Comput., 42(3): 1327-1363. 2013. Preliminary version in STOC 2010
How to Compress Interactive Communication [pdf] paper   bibtex
  2012 (7)
Truth vs. Proof in Computational Complexity. Barak, B. Bulletin of the European Association for Theoretical Computer Science, (108). October 2012. Appeared in Logic in Computer Science column. Also posted in Windows on theory blog
Truth vs. Proof in Computational Complexity [pdf] paper   Truth vs. Proof in Computational Complexity [link] blog   bibtex
A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol. Glaser, A.; Barak, B.; and Goldston, R. J. 2012. Presented at 53rd Annual INMM (Institute of Nuclear Materials Management) meeting
A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol [pdf] paper   A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol [link] powerpoint   bibtex
Fractional Sylvester--Gallai theorems. Barak, B.; Dvir, Z.; Wigderson, A.; and Yehudayoff, A. Proceedings of the National Academy of Sciences, . 2012. Journal version of STOC '11 paper ``Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes''
Fractional Sylvester--Gallai theorems [pdf] paper   bibtex
Making the long code shorter. Barak, B.; Gopalan, P.; H\aastad, J.; Meka, R.; and Raghavendra, P. In FOCS, 2012.
Making the long code shorter [link] eccc   bibtex
Hypercontractivity, sum-of-squares proofs, and their applications. Barak, B.; Brandão, F. G. S. L.; Harrow, A. W.; Kelner, J. A.; Steurer, D.; and Zhou, Y. In STOC, pages 307-326, 2012.
Hypercontractivity, sum-of-squares proofs, and their applications [link] arxiv   bibtex
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction. Barak, B.; Rao, A.; Shaltiel, R.; and Wigderson, A. Annals of Mathematics, 176(3): 1483--1543. 2012. Prelimninary version in STOC '06
2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction [pdf] paper   bibtex
On the (im)possibility of obfuscating programs. Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; and Yang, K. J. ACM, 59(2): 6. 2012. Preliminary version in CRYPTO 2001
On the (im)possibility of obfuscating programs [pdf] paper   bibtex   10 downloads
  2011 (4)
Rounding Semidefinite Programming Hierarchies via Global Correlation. Barak, B.; Raghavendra, P.; and Steurer, D. In FOCS, pages 472-481, 2011.
Rounding Semidefinite Programming Hierarchies via Global Correlation [link]Link   Rounding Semidefinite Programming Hierarchies via Global Correlation [link] arxiv   bibtex
Leftover Hash Lemma, Revisited. Barak, B.; Dodis, Y.; Krawczyk, H.; Pereira, O.; Pietrzak, K.; Standaert, F.; and Yu, Y. In CRYPTO, 2011. According to the New Yorker, this was one of the more obscure titles in the CRYPTO '11 conference, see highlighted text in 4th page linked below
Leftover Hash Lemma, Revisited [pdf] paper   Leftover Hash Lemma, Revisited [pdf] new yorker   bibtex
Computational complexity and information asymmetry in financial products. Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R. Commun. ACM, 54(5): 101-107. 2011.
Computational complexity and information asymmetry in financial products [link] paper   bibtex   1 download
Subsampling Mathematical Programs and Average-Case Complexity. Barak, B.; Hardt, M.; Holenstein, T.; and Steurer, D. In SODA, 2011.
Subsampling Mathematical Programs and Average-Case Complexity [pdf] paper   bibtex
  2010 (4)
Subexponential Algorithms for Unique Games and Related problems. Arora, S.; Barak, B.; and Steurer, D. In Proc. of FOCS, pages 563--572, 2010.
Subexponential Algorithms for Unique Games and Related problems [pdf] paper   bibtex
Public Key Cryptography from Different Assumptions. Applebaum, B.; Barak, B.; and Wigderson, A. In Proc. of STOC, 2010. Preliminary version as cryptology eprint report 2008/335 by Barak and Wigderson
Public Key Cryptography from Different Assumptions [pdf] paper   bibtex
Bounded Key-Dependent Message Security. Barak, B.; Haitner, I.; Hofheinz, D.; and Ishai, Y. In EUROCRYPT, 2010.
Bounded Key-Dependent Message Security [pdf] paper   bibtex
Computational Complexity and Information Asymmetry in Financial Products. Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R. In Innovations in Computer Science (ICS) conference, 2010.
Computational Complexity and Information Asymmetry in Financial Products [pdf] paper   bibtex
  2009 (3)
Strong Parallel Repetition Theorem for Free Projection Games. Barak, B.; Rao, A.; Raz, R.; Rosen, R.; and Shaltiel, R. In Proceedings RANDOM 2009, pages 365, 2009. Springer
Strong Parallel Repetition Theorem for Free Projection Games [pdf] paper   bibtex
The Uniform Hardcore Lemma via Approximate Bregman Projections. Barak, B.; Hardt, M.; and Kale, S. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
The Uniform Hardcore Lemma via Approximate Bregman Projections [pdf] paper   bibtex
Merkle Puzzles are Optimal --- an $O(n^2)$ attack on key exchange from a random oracle. Barak, B.; and Mahmoody-Ghidary, M. In Proceedings of CRYPTO '09, 2009.
Merkle Puzzles are Optimal --- an $O(n^2)$ attack on key exchange from a random oracle [pdf] paper   bibtex
  2008 (5)
Rounding Parallel Repetitions of Unique Games. Barak, B.; Hardt, M.; Haviv, I.; Rao, A.; Regev, O.; and Steurer, D. In Proceedings of 49th FOCS, 2008.
Rounding Parallel Repetitions of Unique Games [pdf] paper   bibtex
On Basing Lower-Bounds for Learning on Worst-Case Assumptions. Applebaum, B.; Barak, B.; and Xiao, D. In Proceedings of 49th FOCS, 2008.
On Basing Lower-Bounds for Learning on Worst-Case Assumptions [pdf] paper   bibtex
Protocols and Lower Bounds for Failure Localization in the Internet. Barak, B.; Goldberg, S.; and Xiao, D. In Proceedings of Eurocrypt 2008, 2008.
Protocols and Lower Bounds for Failure Localization in the Internet [pdf] paper   bibtex
Path-Quality Monitoring in the Presence of Adversaries. Goldberg, S.; Xiao, D.; Tromer, E.; Barak, B.; and Rexford, J. In Proceedings of SIGMETRICS 2008, 2008.
Path-Quality Monitoring in the Presence of Adversaries [pdf] paper   bibtex
Universal Arguments and their Applications. Barak, B.; and Goldreich, O. SIAM Journal on Computing, 38(5): 1661-1694. 2008. Preliminary version in CCC' 02
Universal Arguments and their Applications [link] powerpoint   Universal Arguments and their Applications [ps] ps   bibtex
  2007 (2)
Lower bounds on signatures from symmetric primitives. Barak, B.; and Mahmoody-Ghidary, M. In Proceedings of FOCS '07, 2007.
Lower bounds on signatures from symmetric primitives [pdf] paper   bibtex
Privacy, accuracy, and consistency too: a holistic solution to contingency table release. Barak, B.; Chaudhuri, K.; Dwork, C.; Kale, S.; McSherry, F.; and Talwar, K. In Libkin, L., editor(s), Proceedings of ACM PODS, pages 273--282, 2007. ACM
Privacy, accuracy, and consistency too: a holistic solution to contingency table release [pdf] paper   bibtex
  2006 (3)
Concurrent Non-Malleable Zero Knowledge. Barak, B.; Prabhakaran, M.; and Sahai, A. In Proceedings of FOCS '06, 2006.
Concurrent Non-Malleable Zero Knowledge [pdf] paper   bibtex
Extracting Randomness Using Few Independent Sources. Barak, B.; Impagliazzo, R.; and Wigderson, A. SIAM Journal on Computing, 36(4): 1095-1118. 2006. Preliminary version in FOCS' 04
Extracting Randomness Using Few Independent Sources [pdf] paper   Extracting Randomness Using Few Independent Sources [link] powerpoint   bibtex
Lower bounds for non-black-box zero knowledge. Barak, B.; Lindell, Y.; and Vadhan, S. J. Comput. Syst. Sci, 72(2): 321--391. 2006. Preliminary version in FOCS' 03
Lower bounds for non-black-box zero knowledge [pdf] paper   Lower bounds for non-black-box zero knowledge [link] powerpoint   bibtex
  2005 (4)
An architecture for robust pseudo-random generation and Applications to /dev/random. Barak, B.; and Halevi, S. In ACM, editor(s), Proc. Computing and Communication Security (CCS), 2005.
An architecture for robust pseudo-random generation and Applications to /dev/random [ps] ps   An architecture for robust pseudo-random generation and Applications to /dev/random [pdf] paper   bibtex
How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation. Barak, B.; and Sahai, A. In Proceedings of FOCS '05, 2005.
How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [ps] ps   How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [pdf] paper   How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [link] powerpoint   bibtex
Secure Computation Without Authentication. Barak, B.; Canetti, R.; Lindell, Y.; Pass, R.; and Rabin, T. In Proceedings of CRYPTO '05, 2005.
Secure Computation Without Authentication [link] paper   bibtex
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. Barak, B.; Kindler, G.; Shaltiel, R.; Sudakov, B.; and Wigderson, A. In Proceedings of STOC '05, 2005.
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors [pdf] paper   bibtex
  2004 (4)
Non-Black-Box Techniques in Cryptography. Barak, B. Ph.D. Thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 2004.
bibtex
Universally Composable Protocols with Relaxed Set-Up Assumptions. Barak, B.; Canetti, R.; Nielsen, J. B.; and Pass, R. In Proceedings of FOCS '04, pages 186--195, 2004.
Universally Composable Protocols with Relaxed Set-Up Assumptions [pdf] paper   bibtex
On the Possibility of One-Message Weak Zero-Knowledge. Barak, B.; and Pass, R. In First Theory of Cryptography Conference (TCC), 2004.
On the Possibility of One-Message Weak Zero-Knowledge [pdf] paper   bibtex
Strict Polynomial-Time in Simulation and Extraction. Barak, B.; and Lindell, Y. SIAM Journal on Computing, 33(4): 783--818. August 2004. Extended abstract appeared in STOC 2002
Strict Polynomial-Time in Simulation and Extraction [pdf] paper   bibtex
  2003 (3)
True Random Number Generators Secure in a Changing Environment. Barak, B.; Shaltiel, R.; and Tromer, E. In Workshop on Cryptographic Hardware and Embedded Systems (CHES), of LNCS, pages 166--180, 2003.
True Random Number Generators Secure in a Changing Environment [pdf] paper   True Random Number Generators Secure in a Changing Environment [link] powerpoint   bibtex
Computational analogues of entropy. Barak, B.; Shaltiel, R.; and Wigderson, A. In Proc. of $7$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003. See erratum note in abstract.
Computational analogues of entropy [pdf] paper   Computational analogues of entropy [link] powerpoint   bibtex
Derandomization in Cryptography. Barak, B.; Ong, S. J.; and Vadhan, S. In Proceedings of CRYPTO '03, 2003.
Derandomization in Cryptography [pdf] paper   Derandomization in Cryptography [link] powerpoint   bibtex
  2002 (2)
A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms. Barak, B. In Proc. of $6$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2002.
A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms [ps] ps   bibtex
Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model. Barak, B. In Proceedings of FOCS '02, 2002. See also my thesis.
Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model [pdf] paper   Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model [link] powerpoint   bibtex
  2001 (3)
Delegateable Signatures. Barak, B. Technical Report 2001.
Delegateable Signatures [ps] ps   bibtex
Resettably-Sound Zero-Knowledge and its Applications. Barak, B.; Goldreich, O.; Goldwasser, S.; and Lindell, Y. In Proceedings of FOCS '01, pages 116--125, 2001.
Resettably-Sound Zero-Knowledge and its Applications [ps] ps   bibtex
How to go beyond the black-box simulation barrier. Barak, B. In Proceedings of FOCS '01, pages 106--115, 2001. See also my thesis.
How to go beyond the black-box simulation barrier [pdf] paper   bibtex
  2000 (1)
Clock Synchronization with Faults and Recoveries. Barak, B.; Halevi, S.; Herzberg, A.; and Naor, D. In Proc. of 19$th$ ACM Principles of Distributed Computing (PODC), 2000. ACM
Clock Synchronization with Faults and Recoveries [ps] ps   bibtex
  1999 (1)
The Proactive Security Toolkit and Applications. Barak, B.; Herzberg, A.; Naor, D.; and Shai, E. In Proc. of 6$^{th}$ ACM Conference on Computer and Communications Security (CCS), 1999. ACM
The Proactive Security Toolkit and Applications [ps] ps   bibtex