
Revisiting Model Stitching to Compare Neural Representations
We revisit and extend model stitching (Lenc Vedaldi 2015) as a metho...
read it

Classical algorithms and quantum limitations for maximum cut on highgirth graphs
We study the performance of local quantum algorithms such as the Quantum...
read it

Named Tensor Notation
We propose a notation for tensors with named axes, which relieves the au...
read it

For selfsupervised learning, Rationality implies generalization, provably
We prove a new upper bound on the generalization gap of classifiers that...
read it

Playing Unique Games on Certified SmallSet Expanders
We give an algorithm for solving unique games (UG) instances whose const...
read it

Spoofing Linear CrossEntropy Benchmarking in Shallow Quantum Circuits
The linear crossentropy benchmark (Linear XEB) has been used as a test ...
read it

On HigherOrder Cryptography (Long Version)
Typetwo constructions abound in cryptography: adversaries for encryptio...
read it

Deep Double Descent: Where Bigger Models and More Data Hurt
We show that a variety of modern deep learning tasks exhibit a "doubled...
read it

SGD on Neural Networks Learns Functions of Increasing Complexity
We perform an experimental study of the dynamics of Stochastic Gradient ...
read it

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
We give a quasipolynomial time algorithm for the graph matching problem ...
read it

SmallSet Expansion in Shortcode Graph and the 2to2 Conjecture
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (...
read it

Noisy Tensor Completion via the SumofSquares Hierarchy
In the noisy tensor completion problem we observe m entries (whose locat...
read it

Dictionary Learning and Tensor Decomposition via the SumofSquares Method
We give a new approach to the dictionary learning (also known as "sparse...
read it
Boaz Barak
is this you? claim profile