Boaz Barak | DeepAI

DeepAI AI Chat

Featured Co-authors

Alexander M. Rush
77 publications
Colin Raffel
57 publications
Ilya Sutskever
53 publications
Ankur Moitra
53 publications
Nisheeth K. Vishnoi
49 publications
Sham Kakade
48 publications
Saurabh Garg
39 publications
David Chiang
36 publications
Ugo Dal Lago
34 publications
Pravesh K. Kothari
30 publications
Surbhi Goel
29 publications

∙ 07/18/2023

On the works of Avi Wigderson

This is an overview of some of the works of Avi Wigderson, 2021 Abel pri...

0 Boaz Barak, et al. ∙

∙ 06/14/2023

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

The success of SGD in deep learning has been ascribed by prior works to ...

0 Nikhil Vyas, et al. ∙

∙ 05/25/2023

Scaling Data-Constrained Language Models

The current trend of scaling language models involves increasing both pa...

0 Niklas Muennighoff, et al. ∙

∙ 02/21/2023

Provable Copyright Protection for Generative Models

There is a growing concern that learned conditional generative models ma...

0 Nikhil Vyas, et al. ∙

∙ 07/18/2022

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

There is mounting empirical evidence of emergent phenomena in the capabi...

0 Boaz Barak, et al. ∙

∙ 02/20/2022

Deconstructing Distributions: A Pointwise Framework of Learning

In machine learning, we traditionally evaluate the performance of a sing...

0 Gal Kaplun, et al. ∙

∙ 12/03/2021

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

Demonstrating quantum advantage requires experimental implementation of ...

0 Xun Gao, et al. ∙

∙ 06/14/2021

Revisiting Model Stitching to Compare Neural Representations

We revisit and extend model stitching (Lenc Vedaldi 2015) as a metho...

0 Yamini Bansal, et al. ∙

∙ 06/10/2021

Classical algorithms and quantum limitations for maximum cut on high-girth graphs

We study the performance of local quantum algorithms such as the Quantum...

0 Boaz Barak, et al. ∙

∙ 02/25/2021

Named Tensor Notation

We propose a notation for tensors with named axes, which relieves the au...

0 David Chiang, et al. ∙

∙ 10/16/2020

For self-supervised learning, Rationality implies generalization, provably

We prove a new upper bound on the generalization gap of classifiers that...

0 Yamini Bansal, et al. ∙

∙ 06/17/2020

Playing Unique Games on Certified Small-Set Expanders

We give an algorithm for solving unique games (UG) instances whose const...

0 Mitali Bafna, et al. ∙

∙ 05/05/2020

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

The linear cross-entropy benchmark (Linear XEB) has been used as a test ...

0 Boaz Barak, et al. ∙

∙ 02/17/2020

On Higher-Order Cryptography (Long Version)

Type-two constructions abound in cryptography: adversaries for encryptio...

0 Boaz Barak, et al. ∙

∙ 12/04/2019

Deep Double Descent: Where Bigger Models and More Data Hurt

We show that a variety of modern deep learning tasks exhibit a "double-d...

13 Preetum Nakkiran, et al. ∙

∙ 05/28/2019

SGD on Neural Networks Learns Functions of Increasing Complexity

We perform an experimental study of the dynamics of Stochastic Gradient ...

0 Preetum Nakkiran, et al. ∙

∙ 05/07/2018

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

We give a quasipolynomial time algorithm for the graph matching problem ...

0 Boaz Barak, et al. ∙

∙ 04/23/2018

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

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (...

0 Boaz Barak, et al. ∙

∙ 01/26/2015

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

In the noisy tensor completion problem we observe m entries (whose locat...

0 Boaz Barak, et al. ∙

∙ 07/06/2014

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

We give a new approach to the dictionary learning (also known as "sparse...

0 Boaz Barak, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world