Quantum Exact Learning of k-sparse functions and improved Chang's Lemma for sparse Boolean functions

Sourav Chakraborty, Associate Professor, Indian Statistical Institute
Chaired by
Dr MEEL, Kuldeep Singh, Sung Kah Kay Assistant Professor, School of Computing

  05 Dec 2019 Thursday, 02:00 PM to 04:00 PM

 MR1, COM1-03-19

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 that, for learning a function is $\Theta(nk)$, when the function to be learnt 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 from $O(k^1.5 (log k)^2)$ uniform quantum samples from that function.

Our main tool is an improvement of Chang's lemma for sparse Boolean functions of high Fourier rank.

Sourav Chakraborty is an Associate Professor in Computer Science at the Indian Statistical Institute, Kolkata, India. He finished his bachelors in Mathematics from Chennai Mathematical Institute in 2003 and then went on to do his Master's (in 2005) and Phd (in 2008) in Computer Science from University of Chicago under the guidance of Prof. Laszlo Babai. After doing one year of postdoc at Technion, Israel and one year of postdoc at CWI Amsterdam he joined Chennai Mathematical Institute in 2010. He joined Indian Statistical Institute in 2018. His main area of interest is Theoretical Computer Science with special focus on property testing, Fourier Analysis of Boolean functions and graph algorithms. Recently he has been trying to use property testing techniques in other more applied areas.