BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Avishay Tal (UC Berkeley)
DTSTART:20210317T170000Z
DTEND:20210317T180000Z
DTSTAMP:20260423T021007Z
UID:TCSPlus/22
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/22/"
 >Junta Distance Approximation with Sub-Exponential Queries</a>\nby Avishay
  Tal (UC Berkeley) as part of TCS+\n\n\nAbstract\nJoint Work with Vishnu I
 yer and Michael Whitmeyer\n\nA Boolean function $f:{0\,1}^n \\to {0\,1}$ i
 s called a k-junta if it depends only on k out of the n input bits. Junta 
 testing is the task of distinguishing between k-juntas and functions that 
 are far from k-juntas. A long line of work settled the query complexity of
  testing k-juntas\, which is O(k log(k)) [Blais\, STOC 2009\; Saglam\, FOC
 S 2018]. Suppose\, however\, that f is not a perfect k-junta but rather co
 rrelated with a k-junta. How well can we estimate this correlation? This q
 uestion was asked by De\, Mossel\, and Neeman [FOCS 2019]\, who gave an al
 gorithm for the task making ~exp(k) queries. We present an improved algori
 thm that makes ~exp(sqrt{k}) many queries. \n\nAlong the way\, we also giv
 e an algorithm\, making poly(k) queries\, that provides "implicit oracle a
 ccess" to the underlying k-junta. Our techniques are Fourier analytical an
 d introduce the notion of "normalized influences" that might be of indepen
 dent interest.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/22/
END:VEVENT
END:VCALENDAR