Talks
Fall 2015

Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates

Thursday, October 1st, 2015, 10:45 am11:30 am

Add to Calendar

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.