loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
ASCII Text
x 
 
Michal Koucky, Clemens Lautemann, Sebastian Poloczek, Denis Therien, "Circuit Lower Bounds via Ehrenfeucht-Fraisse Games," Computational Complexity, Annual IEEE Conference on, pp. 190-201, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.12,
author = {Michal Koucky and Clemens Lautemann and Sebastian Poloczek and Denis Therien},
title = {Circuit Lower Bounds via Ehrenfeucht-Fraisse Games},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {190-201},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.12},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Circuit Lower Bounds via Ehrenfeucht-Fraisse Games
SN - 1093-0159
SP190
EP201
A1 - Michal Koucky,
A1 - Clemens Lautemann,
A1 - Sebastian Poloczek,
A1 - Denis Therien,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Michal Koucky, Mathematical Institute, AS CR, Czech Republic
Clemens Lautemann, Johannes Gutenberg-Universitat, Germany
Sebastian Poloczek, Johannes Gutenberg-Universitat, Germany
Denis Therien, McGill University, Canada
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.
Citation:
Michal Koucky, Clemens Lautemann, Sebastian Poloczek, Denis Therien, "Circuit Lower Bounds via Ehrenfeucht-Fraisse Games," ccc, pp.190-201, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.