Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ decision trees.
- each decision tree has depth at most $log^k n$
Question 1:
Can we decide if $C$ is satisfiable faster than $O(2^n)$ ?
Question 2:
For a given epsilon, what is the fastest algorithm for approximating the probability $C$ accepts a uniformly sampled input?
Thanks!
