69 citations · 336 across the 41 of their papers we have counts for
5 papers · 1 filter
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
Amit Daniely, Michael Schapira, Gal Shahaf
Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinator…
A PTAS for Agnostically Learning Halfspaces
Amit Daniely
We present a PTAS for agnostically learning halfspaces w.r.t. the uniform distribution on the dimensional sphere. Namely, we show that for every there is an algorithm tha…
Learning Economic Parameters from Revealed Preferences
Maria-Florina Balcan, Amit Daniely, Ruta Mehta +2
A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a utility function from revealed prefer…
Optimal Learners for Multiclass Problems
Amit Daniely, Shai Shalev-Shwartz
The fundamental theorem of statistical learning states that for binary classification problems, any Empirical Risk Minimization (ERM) learning rule has close to optimal sample comp…
Complexity theoretic limitations on learning DNF's
Amit Daniely, Shai Shalev-Shwatz
Using the recently developed framework of [Daniely et al, 2014], we show that under a natural assumption on the complexity of refuting random K-SAT formulas, learning DNF formulas…