72 citations · 399 across the 60 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
cs.LG2005★ 1 cited
Learning Unions of -Dimensional Rectangles
Alp Atici, Rocco A. Servedio
We consider the problem of learning unions of rectangles over the domain , in the uniform distribution membership query learning setting, where both b and n are "large". We…
cs.CC2005★ 22 cited
Every decision tree has an influential variable
Ryan O'Donnell, Michael Saks, Oded Schramm +1
We prove that for any decision tree calculating a boolean function , \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where is the probability that the…