through_17

5 ms·

1.
by through_17 4y ago
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 Learning Boolean Formula and Finite Automata." Rough
2.
by through_17 8y ago
"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 much closer to what a digit
3.
by through_17 8y ago
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 primitives is also directly informed by instances from
4.
by through_17 8y ago
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 cryptography). Average-case complexity can be studied
5.
by through_17 8y ago
"the particular work" he is referencing is computational complexity theory; a long-running attempt to mathematically characterize which problems can be efficiently solved with computers and which cannot. I work in complexity theor
6.
by through_17 8y ago
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 derandomization of PIT would imply circuit lower bounds, and these seem
7.
by through_17 8y ago
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? So you're converting more random bit
8.
by through_17 8y ago
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 on x outputs YES with probability close to one. For every in
9.
by through_17 8y ago
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 two broad classes of exceptions that I know of: * Where
10.
by through_17 8y ago
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 of the situation for BPP below. Simple constructi