Viewing profile — through_17

Tension between machine learning and cryptography has been studied since at least the late 80's. Example classical result: Kearns and Valiant, "Cryptographic Limitations on Learnin…

"I can’t conceive of any sense in which songs or finger movements aren’t retrieved by the brain." And that's the issue, isn't it? I think he's using "retrieve" to mean something mu…

Yeah, a lot of the work on average-case SAT is directly informed by what industrial benchmarks look like. Further from "core complexity," a lot of the work on machine learning prim…

Let me clarify: average-case does not just mean "over the uniform distribution", though that is of course one distribution of inputs we can study (mostly with applications to crypt…

"the particular work" he is referencing is computational complexity theory; a long-running attempt to mathematically characterize which problems can be efficiently solved with comp…

One reason is that a generic derandomization of BPP would derandomize polynomial identity testing (PIT), an important problem mentioned in the article. Even a very weak derandomiza…

Your sketch is correct, but what you're describing is not derandomization. It is "accuracy amplification" by repeating the test. Each round of the test uses more random bits, right…

Yes, the article is being a little vague with quantifiers. Let L be a language. L is in BPP if there exist a probabilistic, polynomial time TM such that: For every input x in L, M …

Work on determining the relationships between complexity classes is mostly theoretical. I've outlined some of the frontier of this work regarding BPP in another comment. There are …

The article lists what we'd like to know, but the research frontiers for each class are also interesting. In each case, how far are we from our objectives? I'll sketch a little bit…