Name
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 byAC0 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^0 circuits. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/CCC.2006.12 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
circuit lower bounds,ehrenfeucht-fraisse game,ehrenfeucht-fraisse games,byac0 circuit,functions expressible,general ac,lower bound,order formula,linear number,first order,game theory,circuit complexity,computability | Discrete mathematics,Circuit complexity,First order,Computability,Game theory,Electronic circuit,Mathematics,Ehrenfeucht–Fraïssé game,Game complexity | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-2596-2 | 6 |
PageRank | References | Authors |
0.53 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michal Koucky | 1 | 77 | 6.06 |
| Clemens Lautemann | 2 | 369 | 40.31 |
| Sebastian Poloczek | 3 | 6 | 0.53 |
| Denis Therien | 4 | 20 | 2.02 |