<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 08 Aug 2006 Czech Republic Publisher:IEEEJournal:21st Annual IEEE Conference on Computational Complexity (CCC'06)

Authors: Koucký, M. (Michal); Lautemann, C.; Poloczek, S.; Thérien, D.;

doi: 10.1109/ccc.2006.12

handle: 11104/0134828

Circuit Lower Bounds via Ehrenfeucht-Fraisse Games

- Summary
- Subjects
- Related research
  (8)
- Metrics

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 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.

Country

Czech Republic

Related Organizations

McGill University
Canada
Johannes Gutenberg University of Mainz
Germany
Czech Academy of Sciences
Czech Republic
Academy of Sciences Library
Czech Republic

Keywords

Ehrenfeucht-Fraisse games, AC0 circuits, lower-bounds

8 Research products, page 1 of 1

ALOGTIME and a conjecture of S.A. Cook
1992IsAmongTopNSimilarDocuments
Learnability beyond AC/sup 0/
2003IsAmongTopNSimilarDocuments
Towards uniform AC/sup 0/-isomorphisms
2002IsAmongTopNSimilarDocuments
Static dictionaries on AC/sup 0/ RAMs: query time θ(√log n/log log n) is necessary and sufficient
2002IsAmongTopNSimilarDocuments
Tree Canonization and Transitive Closure
2000IsAmongTopNSimilarDocuments
Ac$sup 227$ AND Th$sup 228$ PRODUCTION AS A FUNCTION OF TIME FOR VARIOUS VALUES OF NEUTRON FLUX. (Information Report)
1952IsAmongTopNSimilarDocuments
New nucleide actinium-231
1960IsAmongTopNSimilarDocuments
Communication complexity towards lower bounds on circuit depth
2001IsAmongTopNSimilarDocuments

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	13
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%