Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-051 | 16th October 1995 00:00

VC Dimension in Circuit Complexity

RSS-Feed




TR95-051
Authors: Pascal Koiran
Publication: 23rd October 1995 10:52
Downloads: 3473
Keywords: 


Abstract:

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the same function in a few other computation models: circuits of AND/OR gates,
threshold circuits, and circuits of piecewise-rational gates.



ISSN 1433-8092 | Imprint