BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Guy Blanc (Stanford University)
DTSTART:20211208T180000Z
DTEND:20211208T190000Z
DTSTAMP:20260423T021010Z
UID:TCSPlus/34
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/34/"
 >Properly learning decision trees in almost polynomial time</a>\nby Guy Bl
 anc (Stanford University) as part of TCS+\n\n\nAbstract\nWe give an $n^{O(
 \\log\\log n)}$-time membership query algorithm for properly and agnostica
 lly learning decision trees under the uniform distribution over $\\{-1\,1\
 \}^n$. Even in the realizable setting\, the previous fastest runtime was $
 n^{O(\\log n)}$\, a consequence of a classic algorithm of Ehrenfeucht and 
 Haussler.  \n\nOur algorithm shares similarities with practical heuristics
  for learning decision trees\, which we augment with additional ideas to c
 ircumvent known lower bounds against these heuristics. To analyze our algo
 rithm\, we prove a new structural result for decision trees that strengthe
 ns a theorem of O'Donnell\, Saks\, Schramm\, and Servedio. While the OSSS 
 theorem says that every decision tree has an influential variable\, we sho
 w how every decision tree can be "pruned"  so that every variable in the r
 esulting tree is influential.\n\nJoint work with Jane Lange\, Mingda Qiao\
 , and Li-Yang Tan. To appear in FOCS 2021.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/34/
END:VEVENT
END:VCALENDAR