Abstract
In this talk, I will report moderately exponential time satisfiability algorithms for (i) SYM*AND circuits with a slightly superpolynomial number of gates, (ii) THR*THR circuits with a subquadratic number of gates and (iii) XOR*AND*XOR*AND*XOR circuits with a nearly exponential number of gates. The first algorithm is based on backtracking and dynamic programming. The second and third algorithms are based on the polynomial method in Boolean circuit complexity.