Abstract
In this talk, I will report satisfiability algorithms for (1) systems of degree-k polynomial equations over finite fields, (2) systems of polynomial equations over GF[2] and (3) bounded-depth unbounded-fan-in circuits with AND, OR, NOT, MOD p gates (ACC^0[p] circuits). (1), (2) and (3) are generalizations of the satisfiability problems of k-CNF, CNF and AC^0 respectively and the running time of each algorithm is still almost the same as that of the current best algorithm for each corresponding problem.
Joint work with Daniel Lokshtanov, Ramamohan Paturi and Ryan Williams.