
When Hardness of Approximation Meets Hardness of Learning
A supervised learning algorithm has access to a distribution of labeled ...
read it

Learning Parities with Neural Networks
In recent years we see a rapidly growing line of research which shows le...
read it

Proving the Lottery Ticket Hypothesis: Pruning is All You Need
The lottery ticket hypothesis (Frankle and Carbin, 2018), states that a ...
read it

Learning Boolean Circuits with Neural Networks
Training neuralnetworks is computationally hard. However, in practice t...
read it

On the Optimality of Trees Generated by ID3
Since its inception in the 1980s, ID3 has become one of the most success...
read it

ID3 Learns Juntas for Smoothed Product Distributions
In recent years, there are many attempts to understand popular heuristic...
read it

Decoupling Gating from Linearity
ReLU neuralnetworks have been in the focus of many recent theoretical w...
read it

Is Deeper Better only when Shallow is Good?
Understanding the power of depth in feedforward neural networks is an o...
read it

A Provably Correct Algorithm for Deep Learning that Actually Works
We describe a layerbylayer algorithm for training deep convolutional n...
read it
Eran Malach
is this you? claim profile