Links und Funktionen

Sie sind hier: Startseite / Lehre / WS 2009/10 / Oberseminar / Arist Kojevnikov: On Circuit Complexity of MOD-functions


Arist Kojevnikov: On Circuit Complexity of MOD-functions

30.10.2009 14:15
Wann 14:15 15:45 30.10.2009
von bis
Wo Z1.09 (neu: L109)
Termin übernehmen vCal

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.