Theory Seminar

Seminars
Postdoctoral Associate
Computer Science and Artificial Intelligence Laboratory (CSAIL)
Massachusetts Institute of Technology
Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
Friday, February 28, 2014 - 11:00am to 12:00pm
Blelloch-Skees Conference Room 8115 
Gates&Hillman Centers
Abstract:

In this talk, I describe some recent quantum algorithms for the problem of learning and testing juntas. For the main part of the talk, I study the following variant of the junta learning problem. We are given an oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined symmetric function h. The task is to identify the variables the function depends on. This is a generalization of the Bernstein-Vazirani problem (when h is the XOR function) and the (combinatorial) group testing problem (when h is the OR function). I describe an optimal quantum algorithm for the case when h is the OR or the EXACT-HALF function. For the case of the MAJORITY function, I obtain an upper bound of O(k^{1/4}). Additionally, I describe an application of these techniques for the problem of testing juntas, that is a joint work with Andris Ambainis, Oded Regev, and Ronald de Wolf.

***

Alexander Belov is a postdoctoral associate at MIT Computer Science and Artificial Intelligence Laboratory. He was born in Riga, Latvia, where he finished by undergraduate studies in computer science. Later he obtained his MMath at the University of Waterloo under the supervision of Ashwin Nayak, and his PhD at the University of Latvia under the supervision of Andris Ambainis. He mostly works in quantum algorithms with the emphasis on query complexity, quantum-walk-based algorithms, and lower bounds.