Boaz Barak

According to our database, Boaz Barak authored at least 104 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

An Economic Solution to Copyright Challenges of Generative AI.

Jiachen T. Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, Weijie J. Su

CoRR, 2024

Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models.

Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Distinguishing the Knowable from the Unknowable with Language Models.

Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, Benjamin L. Edelman

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning.

Nikhil Vyas, Depen Morwani, Rosie Zhao, Gal Kaplun, Sham M. Kakade, Boaz Barak

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Named Tensor Notation.

David Chiang, Alexander M. Rush, Boaz Barak

Trans. Mach. Learn. Res., 2023

Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models.

Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak

IACR Cryptol. ePrint Arch., 2023

On the works of Avi Wigderson.

Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, Nisheeth K. Vishnoi

CoRR, 2023

Robust reconstruction of single-cell RNA-seq data with iterative gene weight updates.

Yueqi Sheng, Boaz Barak, Mor Nitzan

Bioinform., 2023

Scaling Data-Constrained Language Models.

Niklas Muennighoff, Alexander M. Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Aleksandra Piktus, Sampo Pyysalo, Thomas Wolf, Colin A. Raffel

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

On Provable Copyright Protection for Generative Models.

Nikhil Vyas, Sham M. Kakade, Boaz Barak

Proceedings of the International Conference on Machine Learning, 2023

Deconstructing Distributions: A Pointwise Framework of Learning.

Gal Kaplun, Nikhil Ghosh, Saurabh Garg, Boaz Barak, Preetum Nakkiran

Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022

Noisy tensor completion via the sum-of-squares hierarchy.

Boaz Barak, Ankur Moitra

Math. Program., 2022

Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit.

Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, Eran Malach, Cyril Zhang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs.

Boaz Barak, Kunal Marwaha

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage.

Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, Soonwon Choi

CoRR, 2021

Playing unique games on certified small-set expanders.

Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Revisiting Model Stitching to Compare Neural Representations.

Yamini Bansal, Preetum Nakkiran, Boaz Barak

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits.

Boaz Barak, Chi-Ning Chou, Xun Gao

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

For self-supervised learning, Rationality implies generalization, provably.

Yamini Bansal, Gal Kaplun, Boaz Barak

Proceedings of the 9th International Conference on Learning Representations, 2021

2020

On Higher-Order Cryptography (Long Version).

Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago

CoRR, 2020

Deep Double Descent: Where Bigger Models and More Data Hurt.

Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, Ilya Sutskever

Proceedings of the 8th International Conference on Learning Representations, 2020

On Higher-Order Cryptography.

Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

SIAM J. Comput., 2019

SGD on Neural Networks Learns Functions of Increasing Complexity.

Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, Boaz Barak

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs.

Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, Yueqi Sheng

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Sum-of-Squares Meets Program Obfuscation, Revisited.

Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai

IACR Cryptol. ePrint Arch., 2018

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture.

Boaz Barak, Pravesh Kothari, David Steurer

Electron. Colloquium Comput. Complex., 2018

2017

Merkle's Key Agreement Protocol is Optimal: An O(n²) Attack on Any Key Agreement from Random Oracles.

Boaz Barak, Mohammad Mahmoody-Ghidary

J. Cryptol., 2017

The Complexity of Public-Key Cryptography.

Boaz Barak

IACR Cryptol. ePrint Arch., 2017

Quantum entanglement, sum of squares, and the log rank conjecture.

Boaz Barak, Pravesh Kothari, David Steurer

Electron. Colloquium Comput. Complex., 2017

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation).

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

Electron. Colloquium Comput. Complex., 2017

The Complexity of Public-Key Cryptograph.

Boaz Barak

Electron. Colloquium Comput. Complex., 2017

The Complexity of Public-Key Cryptography.

Boaz Barak

Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016

Hopes, Fears and Software Obfuscation: A Survey.

Boaz Barak

IACR Cryptol. ePrint Arch., 2016

Computer science should stay young.

Boaz Barak

Commun. ACM, 2016

A breakthrough in software obfuscation: technical perspective.

Boaz Barak

Commun. ACM, 2016

Hopes, fears, and software obfuscation.

Boaz Barak

Commun. ACM, 2016

2015

Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols.

Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, Jennifer Rexford

IEEE/ACM Trans. Netw., 2015

Making the Long Code Shorter.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

SIAM J. Comput., 2015

Subexponential Algorithms for Unique Games and Related Problems.

Sanjeev Arora, Boaz Barak, David Steurer

J. ACM, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Tensor Prediction, Rademacher Complexity and Random 3-XOR.

Boaz Barak, Ankur Moitra

CoRR, 2015

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.

Boaz Barak, Jonathan A. Kelner, David Steurer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Sum of Squares Lower Bounds from Pairwise Independence.

Boaz Barak, Siu On Chan, Pravesh K. Kothari

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk).

Boaz Barak

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Sum-of-squares proofs and the quest toward optimal algorithms.

Boaz Barak, David Steurer

Electron. Colloquium Comput. Complex., 2014

2013

How to Compress Interactive Communication.

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

SIAM J. Comput., 2013

Protecting Obfuscation Against Algebraic Attacks.

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai

IACR Cryptol. ePrint Arch., 2013

Obfuscation for Evasive Functions.

Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, Amit Sahai

IACR Cryptol. ePrint Arch., 2013

Rounding Sum-of-Squares Relaxations.

Boaz Barak, Jonathan A. Kelner, David Steurer

Electron. Colloquium Comput. Complex., 2013

Structure vs Combinatorics in Computational Complexity.

Boaz Barak

Electron. Colloquium Comput. Complex., 2013

Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.

Boaz Barak, Irit Dinur

Comput. Complex., 2013

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.

Boaz Barak, Guy Kindler, David Steurer

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Proof vs. Truth in Computational Complexity.

Boaz Barak

Electron. Colloquium Comput. Complex., 2012

Truth vs. Proof in Computational Complexity.

Boaz Barak

Bull. EATCS, 2012

Hypercontractivity, sum-of-squares proofs, and their applications.

Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Secure Computation Without Authentication.

Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, Tal Rabin

J. Cryptol., 2011

Leftover Hash Lemma, Revisited.

Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, Yu Yu

IACR Cryptol. ePrint Arch., 2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

Boaz Barak, Prasad Raghavendra, David Steurer

Electron. Colloquium Comput. Complex., 2011

Making the long code shorter, with applications to the Unique Games Conjecture.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

Electron. Colloquium Comput. Complex., 2011

Computational complexity and information asymmetry in financial products.

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Commun. ACM, 2011

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.

Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Subsampling Mathematical Relaxations and Average-case Complexity.

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors.

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

Electron. Colloquium Comput. Complex., 2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2010

Public-key cryptography from different assumptions.

Benny Applebaum, Boaz Barak, Avi Wigderson

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract).

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Proceedings of the Innovations in Computer Science, 2010

2009

Bounded Key-Dependent Message Security.

Boaz Barak, Iftach Haitner, Dennis Hofheinz, Yuval Ishai

IACR Cryptol. ePrint Arch., 2009

Subsampling Semidefinite Programs and Max-Cut on the Sphere.

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Electron. Colloquium Comput. Complex., 2009

Direct Sums in Randomized Communication Complexity.

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Electron. Colloquium Comput. Complex., 2009

The uniform hardcore lemma via approximate Bregman projections.

Boaz Barak, Moritz Hardt, Satyen Kale

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Merkle Puzzles Are Optimal - An <i>O</i>(<i>n</i>²)-Query Attack on Any Key Exchange from a Random Oracle.

Boaz Barak, Mohammad Mahmoody-Ghidary

Proceedings of the Advances in Cryptology, 2009

Strong Parallel Repetition Theorem for Free Projection Games.

Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel

Proceedings of the Approximation, 2009

Computational Complexity - A Modern Approach.

Sanjeev Arora, Boaz Barak

Cambridge University Press, ISBN: 978-0-521-42426-4, 2009

2008

Universal Arguments and their Applications.

Boaz Barak, Oded Goldreich

SIAM J. Comput., 2008

Public Key Cryptography from Different Assumptions.

Boaz Barak, Avi Wigderson

IACR Cryptol. ePrint Arch., 2008

Lower Bounds on Signatures From Symmetric Primitives.

Boaz Barak, Mohammad Mahmoody-Ghidary

IACR Cryptol. ePrint Arch., 2008

Merkle Puzzles are Optimal.

Boaz Barak, Mohammad Mahmoody-Ghidary

IACR Cryptol. ePrint Arch., 2008

Path-quality monitoring in the presence of adversaries.

Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, Jennifer Rexford

Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

Rounding Parallel Repetitions of Unique Games.

Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

On Basing Lower-Bounds for Learning on Worst-Case Assumptions.

Benny Applebaum, Boaz Barak, David Xiao

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Protocols and Lower Bounds for Failure Localization in the Internet.

Boaz Barak, Sharon Goldberg, David Xiao

Proceedings of the Advances in Cryptology, 2008

2007

Derandomization in Cryptography.

Boaz Barak, Shien Jin Ong, Salil P. Vadhan

SIAM J. Comput., 2007

Privacy, accuracy, and consistency too: a holistic solution to contingency table release.

Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, Kunal Talwar

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

2006

Extracting Randomness Using Few Independent Sources.

Boaz Barak, Russell Impagliazzo, Avi Wigderson

SIAM J. Comput., 2006

Lower bounds for non-black-box zero knowledge.

Boaz Barak, Yehuda Lindell, Salil P. Vadhan

J. Comput. Syst. Sci., 2006

Concurrent Non-Malleable Zero Knowledge.

Boaz Barak, Manoj Prabhakaran, Amit Sahai

IACR Cryptol. ePrint Arch., 2006

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.

Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Non-black-box Techniques in Cryptography.

Boaz Barak

Proceedings of the Computer Science, 2006

2005

A model and architecture for pseudo-random generation with applications to /dev/random.

Boaz Barak, Shai Halevi

IACR Cryptol. ePrint Arch., 2005

How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation

Boaz Barak, Amit Sahai

Electron. Colloquium Comput. Complex., 2005

2004

Strict Polynomial-Time in Simulation and Extraction.

Boaz Barak, Yehuda Lindell

SIAM J. Comput., 2004

Protocol Initialization for the Framework of Universal Composability.

Boaz Barak, Yehuda Lindell, Tal Rabin

IACR Cryptol. ePrint Arch., 2004

On the Possibility of One-Message Weak Zero-Knowledge.

Boaz Barak, Rafael Pass

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Universally Composable Protocols with Relaxed Set-Up Assumptions.

Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Computational Analogues of Entropy.

Boaz Barak, Ronen Shaltiel, Avi Wigderson

Proceedings of the Approximation, 2003

True Random Number Generators Secure in a Changing Environment.

Boaz Barak, Ronen Shaltiel, Eran Tromer

Proceedings of the Cryptographic Hardware and Embedded Systems, 2003

2002

A Probabilistic-Time Hierarchy Theorem for "Slightly Non-uniform" Algorithms.

Boaz Barak

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model.

Boaz Barak

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Resettably-Sound Zero-Knowledge and its Applications.

Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell

IACR Cryptol. ePrint Arch., 2001

On the (Im)possibility of Obfuscating Programs

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang

Electron. Colloquium Comput. Complex., 2001

How to Go Beyond the Black-Box Simulation Barrier.

Boaz Barak

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Clock synchronization with faults and recoveries (extended abstract).

Boaz Barak, Shai Halevi, Amir Herzberg, Dalit Naor

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

1999

The Proactive Security Toolkit and Applications.

Boaz Barak, Amir Herzberg, Dalit Naor, Eldad Shai

Proceedings of the CCS '99, 1999