6533b834fe1ef96bd129de62

RESEARCH PRODUCT

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

C. LautemannDenis ThérienM. KouckyS. Poloczek

subject

CombinatoricsDiscrete mathematicsComputer Science::Hardware ArchitectureClass (set theory)Computer Science::Emerging TechnologiesComputabilityGame complexityEhrenfeucht–Fraïssé gameCircuit complexityGame theoryLinear numberElectronic circuitMathematics

description

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.

yearjournalcountryeditionlanguage
2006-08-0821st Annual IEEE Conference on Computational Complexity (CCC'06)
https://doi.org/10.1109/ccc.2006.12