Publications (46)
Deconstructing Distributions: A Pointwise Framework of Learning
Gal Kaplun, Nikhil Ghosh, Saurabh Garg +2
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
Classical algorithms and quantum limitations for maximum cut on high-girth graphs
Boaz Barak, Kunal Marwaha
Merkle's Key Agreement Protocol is Optimal: An Attack on any Key Agreement from Random Oracles
Boaz Barak, Mohammad Mahmoody
OpenAI o1 System Card
OpenAI, :, Aaron Jaech +261
gpt-oss-120b & gpt-oss-20b Model Card
OpenAI, :, Sandhini Agarwal +124
Named Tensor Notation
David Chiang, Alexander M. Rush, Boaz Barak
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
Boaz Barak, Zeev Dvir, Avi Wigderson +1
Subsampling Mathematical Relaxations and Average-case Complexity
Boaz Barak, Moritz Hardt, Thomas Holenstein +1
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak, Ankur Moitra
Quantum entanglement, sum of squares, and the log rank conjecture
Boaz Barak, Pravesh Kothari, David Steurer
Trading Inference-Time Compute for Adversarial Robustness
Wojciech Zaremba, Evgenia Nitishinskaya, Boaz Barak +8
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak, David Steurer
Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati +3
Lower Bounds on Signatures from Symmetric Primitives
Boaz Barak, Mohammad Mahmoody
SGD on Neural Networks Learns Functions of Increasing Complexity
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris +4
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak, Jonathan A. Kelner, David Steurer
Scaling Data-Constrained Language Models
Niklas Muennighoff, Alexander M. Rush, Boaz Barak +6
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
Boaz Barak, Benjamin L. Edelman, Surbhi Goel +3
Revisiting Model Stitching to Compare Neural Representations
Yamini Bansal, Preetum Nakkiran, Boaz Barak
OpenAI GPT-5 System Card
Aaditya Singh, Adam Fry, Adam Perelman +483
For self-supervised learning, Rationality implies generalization, provably
Yamini Bansal, Gal Kaplun, Boaz Barak
A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph
Boaz Barak
Distinguishing the Knowable from the Unknowable with Language Models
Gustaf Ahdritz, Tian Qin, Nikhil Vyas +2
Deep Double Descent: Where Bigger Models and More Data Hurt
Preetum Nakkiran, Gal Kaplun, Yamini Bansal +3
Rounding Sum-of-Squares Relaxations
Boaz Barak, Jonathan Kelner, David Steurer
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Xun Gao, Marcin Kalinowski, Chi-Ning Chou +3
An Economic Solution to Copyright Challenges of Generative AI
Jiachen T. Wang, Zhun Deng, Hiroaki Chiba-Okabe +2
Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning
Nikhil Vyas, Depen Morwani, Rosie Zhao +3
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
Boaz Barak, Chi-Ning Chou, Xun Gao
Training LLMs for Honesty via Confessions
Manas Joglekar, Jeremy Chen, Gabriel Wu +4
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Boaz Barak, Pravesh K. Kothari, David Steurer
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh Kothari +2
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
Boaz Barak, Chi-Ning Chou, Zhixian Lei +2
On Higher-Order Cryptography (Long Version)
Boaz Barak, Raphaëlle Crubillé, Ugo Dal Lago
Stress Testing Deliberative Alignment for Anti-Scheming Training
Bronson Schoen, Evgenia Nitishinskaya, Mikita Balesni +16
Optimizing testing policies for detecting COVID-19 outbreaks
Janni Yuval, Mor Nitzan, Neta Ravid Tannenbaum +1
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
Deliberative Alignment: Reasoning Enables Safer Language Models
Melody Y. Guan, Manas Joglekar, Eric Wallace +12
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
Sepehr Ebadi, Alexander Keesling, Madelyn Cain +21
On Provable Copyright Protection for Generative Models
Nikhil Vyas, Sham Kakade, Boaz Barak
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari