Arist Kojevnikov: On Circuit Complexity of MOD-functions

In 1977, Stockemyer proved that any circuit over the full binary basis for a certain class of symmetric Boolean functions including all "x_1+...x_n = k mod m" functions (m > 2) contains at least 2.5n-c gates. He also showed an optimal circuit for x_1+...x_n = k mod 4 function.

In the talk, a very simple proof of a 7n/3-c lower bound for a class of functions represented by high degree polynomials over GF_2 will presented.

The key idea of this proof is a combined complexity measure which assigns different weights to gates of different types.

Also I will show how automatically prove (with help of SAT-solver) upper bounds for MOD-functions.

Based on joint work with Alexander S. Kulikov and Grigory Yaroslavtsev.