- Quantum Algorithms for Lea...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in March 2014
Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
Date: Wednesday, March 26, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, email@example.com
Relevant URL: http://www.ilyaraz.org/acseminar/
Speaker URL: None
firstname.lastname@example.org , email@example.com
TALK: Algorithms and Complexity Seminar: Alexander Belov
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 Rebecca Yadegar at Tuesday, March 25, 2014 at 4:27 PM.