Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

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 AC/sup 0/ 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 AC/sup 0/ circuits.