Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
Date: Wednesday, March 12, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn
Contact: Patrice Macaluso, , firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/421.
Speaker URL: None
TALK: Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
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(k1/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.
Created by Patrice Macaluso at Monday, March 10, 2014 at 4:38 PM.