BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/996
DTSTAMP:20230914T125946Z
SUMMARY:Quantum Exact Learning of k-sparse Functions and Improved Chang's L
 emma for Sparse Boolean Functions
DESCRIPTION:Speaker: Sourav Chakraborty (Indian Statistical Institute (ISI)
 \nKolkata\, West Bengal\, India)\n\nAbstract: \nAbstract: We consider the
  problem of exact learning of $k$-Fourier sparse Boolean functions. In the
  classical setting the query complexity\,  Haviv-Regev (CCC'15) shows th
 at\, for learning a function is $\\Theta(nk)$\, when the function to be le
 arnt takes an $n$ bits string and outputs one bit.  In the quantum query 
 we show how to exactly learn a $k$-Fourier-sparse n-bit Boolean function f
 rom $O(k^1.5 (log k)^2)$ uniform quantum samples from that function. \n\n
 Our main tool is an improvement of Chang’s lemma for sparse Boolean func
 tions of high Fourier rank.\nThis result appears in paper ``Two new result
 s about quantum exact learning" (ICALP 2019) written jointly with Srinivas
 an Arunachalam\, Troy Lee\, Manaswi Paraashar and Ronald de Wolf.\n
URL:https://www.tcs.tifr.res.in/web/events/996
DTSTART;TZID=Asia/Kolkata:20190920T161500
DTEND;TZID=Asia/Kolkata:20190920T171500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR