BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Shravas Rao (Northwestern University)
DTSTART:20211027T170000Z
DTEND:20211027T180000Z
DTSTAMP:20260423T021009Z
UID:TCSPlus/31
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/31/"
 >Degree vs. Approximate Degree and Quantum Implications of Huang's Sensiti
 vity Theorem</a>\nby Shravas Rao (Northwestern University) as part of TCS+
 \n\n\nAbstract\nBased on the recent breakthrough of Huang (2019)\, we show
  that for any total Boolean function $f$\,\n\n-  The degree of $f$ is at m
 ost quadratic in the approximate degree of $f$. This is optimal as witness
 ed by the OR function.\n\n- The deterministic query complexity of $f$ is a
 t most quartic in the quantum query complexity of $f$. This matches the kn
 own separation (up to log factors) due to Ambainis\, Balodis\, Belovs\, Le
 e\, Santha\, and Smotrovs (2017).\n\nWe apply these results to resolve the
  quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show tha
 t if f is a nontrivial monotone graph property of an $n$-vertex graph spec
 ified by its adjacency matrix\, then $Q(f)=\\Omega(n)$\, which is also opt
 imal. We also show that the approximate degree of any read-once formula on
  n variables is $\\Theta(\\sqrt{n})$.\n\nBased on joint work with Scott Aa
 ronson\, Shalev Ben-David\, Robin Kothari\, and Avishay Tal.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/31/
END:VEVENT
END:VCALENDAR