Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)

Melissa Antonelli, Arnaud Durand, Rui Li

The paper proposes an implicit (i.e., machine-independent) complexity approach to studying computation by polynomial-size, constant-depth circuits with gates counting modulo a cons…