Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound

Speaker: Alexander Belov , MIT

Date: Wednesday, March 12, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Patrice Macaluso, , macaluso@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/421.

Speaker URL: None

Speaker Photo:
None

Reminders to: toc@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Patrice Macaluso at Monday, March 10, 2014 at 4:38 PM.