generated by bibbase.org
  2021 (3)
Work with what you've got. Barak, B. Nature Physics. Feb 2021.
Work with what you've got [link]Paper   doi   bibtex   abstract  
For self-supervised learning, Rationality implies generalization, provably. Bansal, Y.; Kaplun, G.; and Barak, B. ICLR, abs/2010.08508. 2021.
For self-supervised learning, Rationality implies generalization, provably [link]Paper   bibtex  
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. Barak, B.; Chou, C.; and Gao, X. ITCS 2021, abs/2005.02421. 2021.
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [link]Paper   bibtex  
  2020 (4)
Playing Unique Games on Certified Small-Set Expanders. Bafna, M.; Barak, B.; Kothari, P.; Schramm, T.; and Steurer, D. CoRR, abs/2006.09969. 2020.
Playing Unique Games on Certified Small-Set Expanders [link]Paper   bibtex  
On Higher-Order Cryptography. Barak, B.; Crubillé, R.; and Lago, U. D. In Czumaj, A.; Dawar, A.; and Merelli, E., editor(s), 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168, of LIPIcs, pages 108:1–108:16, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
On Higher-Order Cryptography [link]Paper   doi   bibtex  
Physical public templates for nuclear warhead verification. Glaser, A.; Barak, B.; Kütt, M.; and Philippe, S. Science & Global Security, 28(1): 48–59. 2020.
bibtex  
Deep Double Descent: Where Bigger Models and More Data Hurt. Nakkiran, P.; Kaplun, G.; Bansal, Y.; Yang, T.; Barak, B.; and Sutskever, I. In ICLR 2020, 2020.
Deep Double Descent: Where Bigger Models and More Data Hurt [link]Paper   bibtex  
  2019 (5)
Sum-of-Squares Meets Program Obfuscation, Revisited. Barak, B.; Hopkins, S. B.; Jain, A.; Kothari, P.; and Sahai, A. In EUROCRYPT 2019, pages 226–250, 2019.
Sum-of-Squares Meets Program Obfuscation, Revisited [link]Paper   doi   bibtex  
SGD on Neural Networks Learns Functions of Increasing Complexity. Nakkiran, P.; Kaplun, G.; Kalimeris, D.; Yang, T.; Edelman, B. L.; Zhang, F.; and Barak, B. In NeurIPS 2019 (spotlight), volume abs/1905.11604, 2019.
SGD on Neural Networks Learns Functions of Increasing Complexity [link]Paper   bibtex  
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. Barak, B.; Chou, C.; Lei, Z.; Schramm, T.; and Sheng, Y. In NeurIPS 2019, 2019.
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs [link]Paper   bibtex  
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Barak, B.; Kothari, P.; and Steurer, D. In ITCS 2019, 2019.
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture [link]Paper   bibtex  
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Barak, B.; Hopkins, S. B.; Kelner, J. A.; Kothari, P. K.; Moitra, A.; and Potechin, A. SIAM J. Comput., 48(2): 687–735. 2019. Special issue for FOCS 2016
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem [link] paper   doi   bibtex  
  2018 (1)
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Barak, B.; Brakerski, Z.; Komargodski, I.; and Kothari, P. In EUROCRYPT, 2018.
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) [link] paper   bibtex  
  2017 (2)
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  
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 (2)
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  
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  
  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  
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