37 citations · 101 across the 43 of their papers we have counts for
9 papers · 1 filter
On the power of adaptivity in statistical adversaries
Guy Blanc, Jane Lange, Ali Malik +1
We study a fundamental question concerning adversarial noise models in statistical problems where the algorithm receives i.i.d. draws from a distribution . The definit…
Tradeoffs for small-depth Frege proofs
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall p…
Provably efficient, succinct, and precise explanations
Guy Blanc, Jane Lange, Li-Yang Tan
We consider the problem of explaining the predictions of an arbitrary blackbox model : given query access to and an instance , output a small set of 's features that i…
Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao +1
We give an -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over . Even in the…
Sharper bounds on the Fourier concentration of DNFs
Victor Lecomte, Li-Yang Tan
In 1992 Mansour proved that every size- DNF formula is Fourier-concentrated on coefficients. We improve this to where is the read num…
Decision tree heuristics can fail, even in the smoothed setting
Guy Blanc, Jane Lange, Mingda Qiao +1
Greedy decision tree learning heuristics are mainstays of machine learning practice, but theoretical justification for their empirical success remains elusive. In fact, it has long…