research
∙
09/15/2023
The discrepancy of greater-than
The discrepancy of the n × n greater-than matrix is shown to be π/2 ln n...
share
research
∙
04/08/2023
A Unified Characterization of Private Learnability via Graph Theory
We provide a unified framework for characterizing pure and approximate d...
research
∙
04/07/2023
Replicability and stability in learning
Replicability is essential in science as it allows us to validate and ve...
research
∙
03/03/2022
A Characterization of Multiclass Learnability
A seminal result in learning theory characterizes the PAC learnability o...
research
∙
11/03/2021
Regularization by Misclassification in ReLU Neural Networks
We study the implicit bias of ReLU neural networks trained by a variant ...
research
∙
07/13/2021
Tight bounds on the Fourier growth of bounded functions on the hypercube
We give tight bounds on the degree â„“ homogenous parts f_â„“ of a bounded f...
research
∙
05/28/2021
A lower bound for essential covers of the cube
Essential covers were introduced by Linial and Radhakrishnan as a model ...
research
∙
05/05/2021
On the Communication Complexity of Key-Agreement Protocols
Key-agreement protocols whose security is proven in the random oracle mo...
research
∙
02/10/2021
Slicing the hypercube is not easy
We prove that at least Ω(n^0.51) hyperplanes are needed to slice all edg...
research
∙
11/09/2020
A Theory of Universal Learning
How quickly can a given class of concepts be learned from examples? It i...
research
∙
07/01/2019
On Symmetry and Initialization for Neural Networks
This work provides an additional step in the theoretical understanding o...
research
∙
11/25/2018
Average-Case Information Complexity of Learning
How many bits of information are revealed by a learning algorithm for a ...
research
∙
06/14/2018
On the Perceptron's Compression
We study and provide exposition to several phenomena that are related to...
research
∙
06/10/2018
On the Covariance-Hessian Relation in Evolution Strategies
We consider Evolution Strategies operating only with isotropic Gaussian ...
research
∙
04/16/2018
A Direct Sum Result for the Information Complexity of Learning
How many bits of information are required to PAC learn a class of hypoth...
research
∙
11/16/2017
On Communication Complexity of Classification Problems
This work introduces a model of distributed learning in the spirit of Ya...
research
∙
10/14/2017
Learners that Leak Little Information
We study learning algorithms that are restricted to revealing little inf...
research
∙
07/17/2017
On weak ε-nets and the Radon number
We show that the Radon number characterizes the existence of weak nets i...
research
∙
06/23/2016
