Boaz Barak

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 60

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

IACR Cryptol. ePrint Arch.

Publications

Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, Benjamin L. Edelman
Distinguishing the Knowable from the Unknowable with Language Models. CoRR (2024)
Jiachen T. Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, Weijie J. Su
An Economic Solution to Copyright Challenges of Generative AI. CoRR (2024)
Nikhil Vyas, Sham M. Kakade, Boaz Barak
On Provable Copyright Protection for Generative Models. ICML (2023)
Nikhil Vyas, Depen Morwani, Rosie Zhao, Gal Kaplun, Sham M. Kakade, Boaz Barak
Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning. CoRR (2023)
Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, Nisheeth K. Vishnoi
On the works of Avi Wigderson. CoRR (2023)
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak
Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models. IACR Cryptol. ePrint Arch. 2023 (2023)
Niklas Muennighoff, Alexander M. Rush, Boaz Barak, Teven Le Scao, Aleksandra Piktus, Nouamane Tazi, Sampo Pyysalo, Thomas Wolf, Colin Raffel
Scaling Data-Constrained Language Models. CoRR (2023)
Gal Kaplun, Nikhil Ghosh, Saurabh Garg, Boaz Barak, Preetum Nakkiran
Deconstructing Distributions: A Pointwise Framework of Learning. ICLR (2023)
Niklas Muennighoff, Alexander M. Rush, Boaz Barak, Teven Le Scao, Nouamane Tazi, Aleksandra Piktus, Sampo Pyysalo, Thomas Wolf, Colin A. Raffel
Scaling Data-Constrained Language Models. NeurIPS (2023)
David Chiang, Alexander M. Rush, Boaz Barak
Named Tensor Notation. Trans. Mach. Learn. Res. 2023 (2023)
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak
Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models. CoRR (2023)
Yueqi Sheng, Boaz Barak, Mor Nitzan
Robust reconstruction of single-cell RNA-seq data with iterative gene weight updates. Bioinform. 39 (Supplement-1) (2023)
Nikhil Vyas, Sham M. Kakade, Boaz Barak
Provable Copyright Protection for Generative Models. CoRR (2023)
Boaz Barak, Ankur Moitra
Noisy tensor completion via the sum-of-squares hierarchy. Math. Program. 193 (2) (2022)
Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, Eran Malach, Cyril Zhang
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit. CoRR (2022)
Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham M. Kakade, Eran Malach, Cyril Zhang
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit. NeurIPS (2022)
Boaz Barak, Kunal Marwaha
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. ITCS (2022)
Gal Kaplun, Nikhil Ghosh, Saurabh Garg, Boaz Barak, Preetum Nakkiran
Deconstructing Distributions: A Pointwise Framework of Learning. CoRR (2022)
Boaz Barak, Kunal Marwaha
Classical algorithms and quantum limitations for maximum cut on high-girth graphs. CoRR (2021)
Yamini Bansal, Preetum Nakkiran, Boaz Barak
Revisiting Model Stitching to Compare Neural Representations. CoRR (2021)
Yamini Bansal, Preetum Nakkiran, Boaz Barak
Revisiting Model Stitching to Compare Neural Representations. NeurIPS (2021)
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer
Playing unique games on certified small-set expanders. STOC (2021)
Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, Soonwon Choi
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage. CoRR (2021)
David Chiang, Alexander M. Rush, Boaz Barak
Named Tensor Notation. CoRR (2021)
Boaz Barak, Chi-Ning Chou, Xun Gao
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. ITCS (2021)
Yamini Bansal, Gal Kaplun, Boaz Barak
For self-supervised learning, Rationality implies generalization, provably. ICLR (2021)
Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago
On Higher-Order Cryptography (Long Version). CoRR (2020)
Boaz Barak, Chi-Ning Chou, Xun Gao
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. CoRR (2020)
Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago
On Higher-Order Cryptography. ICALP (2020)
Yamini Bansal, Gal Kaplun, Boaz Barak
For self-supervised learning, Rationality implies generalization, provably. CoRR (2020)
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, Ilya Sutskever
Deep Double Descent: Where Bigger Models and More Data Hurt. ICLR (2020)
Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
Playing Unique Games on Certified Small-Set Expanders. CoRR (2020)
Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, Yueqi Sheng
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. NeurIPS (2019)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. 48 (2) (2019)
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, Boaz Barak
SGD on Neural Networks Learns Functions of Increasing Complexity. CoRR (2019)
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, Ilya Sutskever
Deep Double Descent: Where Bigger Models and More Data Hurt. CoRR (2019)
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
Sum-of-Squares Meets Program Obfuscation, Revisited. EUROCRYPT (1) (2019)
Boaz Barak, Pravesh K. Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS (2019)
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin L. Edelman, Tristan Yang, Boaz Barak, Haofeng Zhang
SGD on Neural Networks Learns Functions of Increasing Complexity. NeurIPS (2019)
Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, Yueqi Sheng
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. CoRR (2018)
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
Sum-of-Squares Meets Program Obfuscation, Revisited. IACR Cryptol. ePrint Arch. 2018 (2018)
Boaz Barak, Pravesh Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. 25 (2018)
Boaz Barak, Pravesh K. Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR (2018)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). EUROCRYPT (2) (2018)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). IACR Cryptol. ePrint Arch. 2017 (2017)
Boaz Barak, Pravesh K. Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. STOC (2017)
Boaz Barak, Mohammad Mahmoody-Ghidary
) Attack on Any Key Agreement from Random Oracles. J. Cryptol. 30 (3) (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. CoRR (2017)
Boaz Barak
The Complexity of Public-Key Cryptograph. Electron. Colloquium Comput. Complex. 24 (2017)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Electron. Colloquium Comput. Complex. 24 (2017)
Boaz Barak
The Complexity of Public-Key Cryptography. IACR Cryptol. ePrint Arch. 2017 (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. 24 (2017)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR (2016)
Boaz Barak
Hopes, Fears and Software Obfuscation: A Survey. IACR Cryptol. ePrint Arch. 2016 (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. 23 (2016)
Boaz Barak
A breakthrough in software obfuscation: technical perspective. Commun. ACM 59 (5) (2016)
Boaz Barak
Hopes, fears, and software obfuscation. Commun. ACM 59 (3) (2016)
Boaz Barak, Ankur Moitra
Noisy Tensor Completion via the Sum-of-Squares Hierarchy. COLT (2016)
Boaz Barak
Computer science should stay young. Commun. ACM 59 (6) (2016)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. STOC (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Boaz Barak, Ankur Moitra
Tensor Prediction, Rademacher Complexity and Random 3-XOR. CoRR (2015)
Boaz Barak, Siu On Chan, Pravesh K. Kothari
Sum of Squares Lower Bounds from Pairwise Independence. STOC (2015)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. SIAM J. Comput. 44 (5) (2015)
Boaz Barak, Siu On Chan, Pravesh Kothari
Sum of Squares Lower Bounds from Pairwise Independence. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, Jennifer Rexford
Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols. IEEE/ACM Trans. Netw. 23 (6) (2015)
Sanjeev Arora, Boaz Barak, David Steurer
Subexponential Algorithms for Unique Games and Related Problems. J. ACM 62 (5) (2015)
Boaz Barak
Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk). FSTTCS (2015)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. CoRR (2014)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding sum-of-squares relaxations. STOC (2014)
Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, Amit Sahai
Obfuscation for Evasive Functions. TCC (2014)
Boaz Barak, David Steurer
Sum-of-squares proofs and the quest toward optimal algorithms. CoRR (2014)
Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai
Protecting Obfuscation against Algebraic Attacks. EUROCRYPT (2014)
Boaz Barak
Structure vs Combinatorics in Computational Complexity. Bull. EATCS 112 (2014)
Boaz Barak, David Steurer
Sum-of-squares proofs and the quest toward optimal algorithms. Electron. Colloquium Comput. Complex. 21 (2014)
Boaz Barak
Structure vs Combinatorics in Computational Complexity. Electron. Colloquium Comput. Complex. 20 (2013)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. CoRR (2013)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. Electron. Colloquium Comput. Complex. 20 (2013)
Boaz Barak, Guy Kindler, David Steurer
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. ITCS (2013)
Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, Amit Sahai
Obfuscation for Evasive Functions. IACR Cryptol. ePrint Arch. 2013 (2013)
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
How to Compress Interactive Communication. SIAM J. Comput. 42 (3) (2013)
Boaz Barak, Irit Dinur
Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword. Comput. Complex. 22 (2) (2013)
Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai
Protecting Obfuscation Against Algebraic Attacks. IACR Cryptol. ePrint Arch. 2013 (2013)
Boaz Barak
Proof vs. Truth in Computational Complexity. Electron. Colloquium Comput. Complex. 19 (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, sum-of-squares proofs, and their applications. STOC (2012)
Boaz Barak
Truth vs. Proof in Computational Complexity. Bull. EATCS 108 (2012)
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
On the (im)possibility of obfuscating programs. J. ACM 59 (2) (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, Sum-of-Squares Proofs, and their Applications CoRR (2012)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. FOCS (2012)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. Electron. Colloquium Comput. Complex. 18 (2011)
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
Subsampling Mathematical Relaxations and Average-case Complexity. SODA (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture CoRR (2011)
Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. STOC (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. 18 (2011)
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, Tal Rabin
Secure Computation Without Authentication. J. Cryptol. 24 (4) (2011)
Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge
Computational complexity and information asymmetry in financial products. Commun. ACM 54 (5) (2011)
Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, Yu Yu
Leftover Hash Lemma, Revisited. CRYPTO (2011)

Boaz Barak.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Boaz Barak