Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-169 | 9th December 2014 21:12

Lower Bounds for Monotone Counting Circuits

RSS-Feed




TR14-169
Authors: Stasys Jukna
Publication: 9th December 2014 21:12
Downloads: 1090
Keywords: 


Abstract:

A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities given by their coefficients). A circuit decides f if it has the same 0-1 roots as f.

We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and can be exponentially easier to decide than to count them. Then we give general lower bounds on the size of counting circuits.



ISSN 1433-8092 | Imprint