Title :
Circuit lower bounds via Ehrenfeucht-Fraisse games
Author :
Koucký, Michal ; Poloczek, Sebastian ; Lautemann, Clemens ; Thérien, Denis
Author_Institution :
Math. Inst., Prague
Abstract :
In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC0 circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC0 circuits
Keywords :
circuit complexity; computability; game theory; AC0 circuit; Ehrenfeucht-Fraisse game; circuit lower bound; first order formula; Complexity theory; Computational complexity; Computer science; Game theory; Heart; Logic circuits; Polynomials; Robustness;
Conference_Titel :
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location :
Prague
Print_ISBN :
0-7695-2596-2
DOI :
10.1109/CCC.2006.12
