DocumentCode
2200627
Title
On proving lower bounds for circuit size
Author
Karchmer, M.
Author_Institution
Dept. of Math., MIT, Cambridge, MA, USA
fYear
1993
fDate
18-21 May 1993
Firstpage
112
Lastpage
118
Abstract
A.A. Razborov´s (1989) generalized approximation method, which has the potential of giving tight lower bounds for circuit size, is considered. The method is described in a more intuitive fashion, and its analogy with the ultraproduct construction in model theory is made explicit. The method is extended so that it can be used to lower bound nondeterministic circuit size. Using the proposed framework, a new proof for the exponential monotone size lower bound for the clique function is presented
Keywords
computational complexity; circuit size; clique function; generalized approximation method; lower bound nondeterministic circuit size; lower bounds proving; model theory; ultraproduct construction; Algebra; Approximation methods; Boolean functions; Circuits; Contracts; Ducts; Filters; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location
San Diego, CA
Print_ISBN
0-8186-4070-7
Type
conf
DOI
10.1109/SCT.1993.336535
Filename
336535
Link To Document