BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Bruno Loff (University of Lisbon)
DTSTART:20240605T130000Z
DTEND:20240605T140000Z
DTSTAMP:20260423T021148Z
UID:FLAT/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/5/">The
  hardness of decision tree complexity</a>\nby Bruno Loff (University of Li
 sbon) as part of One FLAT World Seminar\n\n\nAbstract\nIn the world of for
 mal languages\, we have always been interested in the problem of finding t
 he smallest “algorithm” for deciding a given language. Moore’s algor
 ithm for DFA minimization is a standard part of a first course in theory o
 f computing. Jiang and Ravikumar have shown\, on the other hand\, that NFA
  minimization is PSPACE-hard.\n\nWe will discuss a related problem for the
  computational model of deterministic decision trees. Let $f$\nbe a Boolea
 n function given as either a truth table or as a circuit. In both of these
  cases\, how difficult is it to find the smallest complexity of a decision
  tree for computing $f$? (This is commonly known as the “query complexit
 y” of $f$). We will show that this problem is NC_1-hard and PSPACE-hard\
 , respectively. The second bound is tight\, and the first bound is close t
 o being tight.\n
LOCATION:https://researchseminars.org/talk/FLAT/5/
END:VEVENT
END:VCALENDAR