Home
Papers
Teaching
Students
Preprints
On the Optimality of Trees Generated by ID3
.
With Alon Brutzkus and Eran Malach.
Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
.
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
.
With
Yossi Arjevani
,
Stefanie Jegelka
and
Hongzhou Lin
.
2020
Learning Parities with Neural Networks
.
With Eran Malach.
NIPS, 2020. Oral.
Most ReLU Networks Suffer from $\ell^2$ Adversarial Perturbations
.
With Hadas Shacham.
NIPS, 2020. Spotlight.
Hardness of Learning Neural Networks with Natural Weights
.
With Gal Vardi.
NIPS, 2020.
Neural Networks Learning and Memorization with (almost) no Over-Parameterization
.
NIPS, 2020.
The Implicit Bias of Depth: How Incremental Learning Drives Generalization
.
With Daniel Gissin and
Shai Shalev-Shwartz
.
ICLR, 2020.
Distribution Free Learning with Local Queries
.
With Galit Bary-Weisberg and
Shai Shalev-Shwartz
.
ALT, 2020.
ID3 Learns Juntas for Smoothed Product Distributions
.
With Alon Brutzkus and Eran Malach.
COLT, 2020.
2019
Generalization Bounds for Neural Networks via Approximate Description Length
.
With Elad Granot.
NIPS, 2019. Spotlight.
Learning without Interaction Requires Separation
.
With
Vitaly Feldman
.
NIPS, 2019.
Competitive ratio versus regret minimization: achieving the best of both worlds
.
With
Yishay Mansour
.
ALT, 2019.
Learning Rules-First Classifiers
.
With
Deborah Cohen
,
Amir Globerson
and
Gal Elidan
.
AISTAT, 2019. Oral Presentation
2017
SGD Learns the Conjugate Kernel Class of the Network
.
NIPS, 2017.
Depth Separation for Neural Networks
.
COLT, 2017.
Sketching and Neural Networks
.
With Nevena Lazic,
Yoram Singer
and
Kunal Talwar
.
ICLR Workshop, 2017.
2016
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
.
With
Roy Frostig
and
Yoram Singer
.
NIPS, 2016.
Complexity theoretic limitations on learning DNF's
.
With
Shai Shalev-Shwartz
.
COLT, 2016.
Complexity theoretic limitations on learning halfspaces
.
STOC, 2016.
2015
Strongly Adaptive Online Learning
.
With
Alon Gonen
and
Shai Shalev-Shwartz
.
ICML, 2015.
A PTAS for Agnostically Learning Halfspaces
.
COLT, 2015.
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
.
With
Michael Schapira
and Gal Shahaf.
STOC, 2015. Invited to SICOMP.
2014
Learning Economic Parameters from Revealed Preferences
.
With
Maria-Florina Balcan
,
Ruta Mehta
,
Ruth Urner
and
Vijay V. Vazirani
.
WINE, 2014.
Optimal Learners for Multiclass Problems
.
With
Shai Shalev-Shwartz
.
COLT, 2014.
The complexity of learning halfspaces using generalized linear methods
.
With
Nati Linial
and
Shai Shalev-Shwartz
.
COLT, 2014. Best student paper.
From average case complexity to improper learning complexity
.
With
Nati Linial
and
Shai Shalev-Shwartz
.
STOC, 2014.
2013
More data speeds up training time in learning halfspaces over sparse vectors
.
With
Nati Linial
and
Shai Shalev-Shwartz
.
NIPS, 2013. Spotlight.
The price of bandit information in multiclass online classification
.
With Tom Halbertal.
COLT, 2013.
On the practically interesting instances of MAXCUT
.
With Yonatan Bilu,
Nati Linial
and
Michael Saks
.
STACS, 2013.
2011-2012
Tight Products and Graph Expansion
.
With
Nati Linial
.
Journal of Graph Theory, 2012.
Multiclass Learning Approaches: A Theoretical Comparison with Implications
.
With
Sivan Sabato
and
Shai Shalev-Shwartz
.
NIPS, 2012. Spotlight.
Multiclass Learnability and the ERM principle
.
With
Sivan Sabato
,
Shai Ben-David
and
Shai Shalev-Shwartz
.
COLT, 2011. Best student paper.
JMLR, 2015
Unpublished manuscripts
Random Features for Compositional Kernels
.
With
Roy Frostig
, Vineet Gupta and
Yoram Singer
.
Behavior-Based Machine-Learning: A Hybrid Approach for Predicting Human Decision Making
.
With
Gali Noti
, Effi Levi and Yoav Kolumbus.
Clustering is difficult only when it does not matter
.
With
Nati Linial
and
Michael Saks
.