frisby
11
3
frisby has not written any posts yet.
Confirming that efficiently finding a small circuit (you don't actually need further restrictions than size) based on its values on a fixed collection of test inputs is known to imply --- see this paper.
This is a fact worth knowing and a lucid explanation --- thanks for writing this!
I know it's not the main point of the post, but I found myself a little lost when you talked about complexity theory; I would be interested to hear more details. In particular:
what are the definitions of these classes? Are these decision problems in the usual sense, or is this a statement about learning theory? I haven't been able to either track down a definition of e.g. "NP-invertible" or invent one that would make sense --- if this is a renamed-version of something people have studied I would be curious... (read more)
A couple small notes / clarifications about the results in this post:
- Theorem 1 could be equivalently stated "For any constant c, the family of size-nc circuits is Verifiably Acceptable". (If G is parameterized by descriptions that can be evaluated in polynomial time, then you can wlog think of G as a subfamily of polynomial-sized circuits.)
- It's worth emphasizing that while x∗ (the location of the backdoor) is chosen uniformly random here, both g (the function we'd like to distill, but can only access as a black-box) and f (the untrusted distilled model handed to us) can be arbitrary functions (as long as they have small circuits). So, while we're thinking of g as coming from "nature", in the model as stated we can consider the adversary as
... (read more)