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$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.