Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Basel
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106915 |