Timeline for What is the complexity of distinguishing a true Fourier spectra from a fake one?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 13, 2013 at 22:25 | comment | added | Scott Aaronson | Gil: Not really! You then get an unrelativized promise problem in BQP, which we don't know to be in PH. Certainly, you could simulate the "random" case of the oracle problem by replacing f and g by pseudorandom functions (computed in time that's a larger polynomial than the PH machine has available). The hard part is, how do you simulate the "forrelated" case of the oracle problem (where f is close to the Fourier transform of g)? I.e., how do you provide small circuits for such f and g that don't "give the entire game away"? (A similar issue occurs with Simon's problem.) | |
| Jan 5, 2013 at 21:58 | history | bounty ended | Gil Kalai | ||
| Jan 5, 2013 at 21:58 | comment | added | Gil Kalai | Is more known when f is in P? | |
| Jan 5, 2013 at 20:43 | comment | added | Scott Aaronson | It's a slight variant, but I believe it's not hard to prove equivalent. First, certainly if you can solve Fourier Checking then you can also solve Gharibi's problem (just run the FC algorithm separately for g and h). For the converse, if you can solve Gharibi's problem, then given an instance of FC, name the second FC function either "g" or "h" uniformly at random, and set the other of the two (respectively h or g) to be a random function. If the Gharibi algorithm always picks the original function from the FC instance, that's evidence that the instance was forrelated rather than random. | |
| Jan 4, 2013 at 20:23 | comment | added | vzn | is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours? | |
| Jan 4, 2013 at 1:05 | history | answered | Scott Aaronson | CC BY-SA 3.0 |