0000000000809552

AUTHOR

M. Koucky

showing 1 related works from this author

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

2006

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.

CombinatoricsDiscrete mathematicsComputer Science::Hardware ArchitectureClass (set theory)Computer Science::Emerging TechnologiesComputabilityGame complexityEhrenfeucht–Fraïssé gameCircuit complexityGame theoryLinear numberElectronic circuitMathematics21st Annual IEEE Conference on Computational Complexity (CCC'06)
researchProduct