research
∙
07/18/2023
On the works of Avi Wigderson
This is an overview of some of the works of Avi Wigderson, 2021 Abel pri...
share
research
∙
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 ...
research
∙
05/25/2023
Scaling Data-Constrained Language Models
The current trend of scaling language models involves increasing both pa...
research
∙
02/21/2023
Provable Copyright Protection for Generative Models
There is a growing concern that learned conditional generative models ma...
research
∙
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...
research
∙
02/20/2022
Deconstructing Distributions: A Pointwise Framework of Learning
In machine learning, we traditionally evaluate the performance of a sing...
research
∙
12/03/2021
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Demonstrating quantum advantage requires experimental implementation of ...
research
∙
06/14/2021
Revisiting Model Stitching to Compare Neural Representations
We revisit and extend model stitching (Lenc Vedaldi 2015) as a metho...
research
∙
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...
research
∙
02/25/2021
Named Tensor Notation
We propose a notation for tensors with named axes, which relieves the au...
research
∙
10/16/2020
For self-supervised learning, Rationality implies generalization, provably
We prove a new upper bound on the generalization gap of classifiers that...
research
∙
06/17/2020
Playing Unique Games on Certified Small-Set Expanders
We give an algorithm for solving unique games (UG) instances whose const...
research
∙
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 ...
research
∙
02/17/2020
On Higher-Order Cryptography (Long Version)
Type-two constructions abound in cryptography: adversaries for encryptio...
research
∙
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...
research
∙
05/28/2019
SGD on Neural Networks Learns Functions of Increasing Complexity
We perform an experimental study of the dynamics of Stochastic Gradient ...
research
∙
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 ...
research
∙
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 (...
research
∙
01/26/2015
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
In the noisy tensor completion problem we observe m entries (whose locat...
research
∙
07/06/2014