MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.