Define $\mathcal{F}(G) = \{ f : \{0, 1\}^n \rightarrow \{0, 1\} \mid G \leq Aut(f) \}$. Note that all functions can be computed on $n$ bits with circuits of size $2^n/n$. On the other hand, we don't care about the string, per-say, for a function in $\mathcal{F}(G)$, we just care about what orbit it's in. We call the number of orbits of $G$. If we got that as input, by that same upper bound, we know that we can build a circuit for this function of size something like $\frac{|\{0, 1\}^n/G|}{log_2|\{0, 1\}^n/G|}$. This is not an upper bound, but is clearly a good candidate for one intuitively. The obvious question here is whether we can always get circuits of this size, and Babai, Beals, and Takacsi-Nagy show in Symmetry and Complexity an upper size bound of $|\{0, 1\}^n/G|$, showing that we can get roughly to where we'd naively expect. As well, they show a lower bound which shows that the candidate upper bound I proposed would be tight, in that there are functions in $\mathcal{F}(G)$ which cannot be computed by circuits of size less than or equal to half of my candidate upper bound.

All of this, of course, implies that functions which are approximately symmetric, lets say they are constant on at least a $1 - \epsilon$ fraction of the bits, that we can compute our function with circuit size $|\{0, 1\}^n/G| + \epsilon n 2^n$ (I think you could do better than that $n2^n$, its just the naive thing). Now, can you find a (hopefully natural) family of functions $\{f_n\}$ such that they are very far from being symmetric under all families of groups but also easy to non-uniformly recognize.

To make this concrete, I'll specialize it: I'm curious if you can find a function family which is at least a constant fraction $\epsilon_0$ away from being symmetric to all group families (infinitely often, if you must) but is computable by subexponential size non-uniform circuits?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.