Given a permutation group $G \leq S_n$, can you construct non-uniformly a circuit computing a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log|\{0, 1\}^n/G_n|)}$ with size $O_n(\frac{|\{0, 1\}^n / G_n|}{log|\{0, 1\}^n/G_n|})$ such that the fibers of $f$ are the orbits of $\{0, 1\}^n$ under $G$?
$\begingroup$
$\endgroup$
0
Add a comment
|