research
∙
07/24/2023
On Privileged and Convergent Bases in Neural Network Representations
In this study, we investigate whether the representations learned by neu...
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
∙
02/21/2023
Provable Copyright Protection for Generative Models
There is a growing concern that learned conditional generative models ma...
research
∙
06/30/2022
On the Number of Quantifiers as a Complexity Measure
In 1981, Neil Immerman described a two-player game, which he called the ...
research
∙
06/20/2022
Limitations of the NTK for Understanding Generalization in Deep Learning
The “Neural Tangent Kernel” (NTK) (Jacot et al 2018), and its empirical ...
research
∙
06/24/2021
Optimal Fine-grained Hardness of Approximation of Linear Equations
The problem of solving linear systems is one of the most fundamental pro...
research
∙
04/30/2021
Multi-Structural Games and Number of Quantifiers
We study multi-structural games, played on two sets 𝒜 and ℬ of structure...
research
∙
11/07/2020
Fast Low-Space Algorithms for Subset Sum
We consider the canonical Subset Sum problem: given a list of positive i...
research
∙
01/21/2020
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
We continue the program of proving circuit lower bounds via circuit sati...
research
∙
07/18/2019
Imperfect Gaps in Gap-ETH and PCPs
We study the role of perfect completeness in probabilistically checkable...
research
∙
04/25/2019
Approximation Algorithms for Min-Distance Problems
We study fundamental graph parameters such as the Diameter and Radius in...
research
∙
04/25/2019
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Some of the most fundamental and well-studied graph parameters are the D...
research
∙
12/12/2018
Thwarting Adversarial Examples: An L_0-RobustSparse Fourier Transform
We give a new algorithm for approximating the Discrete Fourier transform...
research
∙
10/14/2018
Super Strong ETH is False for Random k-SAT
It has been hypothesized that k-SAT is hard to solve for randomly chosen...
research
∙
04/25/2018
