Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

Prague, Czech Republic July 16-July 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2006.12

21st Annual IEEE Conference on Compu ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Michal Koucky Articles by Clemens Lautemann Articles by Sebastian Poloczek Articles by Denis Therien

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.