School of Technology and Computer Science Seminars

Quantum Exact Learning of k-sparse Functions and Improved Chang's Lemma for Sparse Boolean Functions

by Sourav Chakraborty (Indian Statistical Institute (ISI), Kolkata, West Bengal, India)

Friday, September 20, 2019 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Abstract: 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 Θ(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(k1.5(logk)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.

This result appears in paper ``Two new results about quantum exact learning" (ICALP 2019) written jointly with Srinivasan Arunachalam, Troy Lee, Manaswi Paraashar and Ronald de Wolf.
Organised by Arkadev Chattopadhyay