DocumentCode :
2345869
Title :
On modular counting with polynomials
Author :
Hansen, Kristoffer Arnsfelt
Author_Institution :
Dept. of Comput. Sci., Aarhus Univ.
fYear :
0
fDate :
0-0 0
Lastpage :
212
Abstract :
For any integers m and l, where m has r sufficiently large (depending on l) factors, that are powers of r distinct primes, we give a construction of a (symmetric) polynomial over Zm of degree O(rradicn) that is a generalized representation (commonly also called weak representation) of the MODl function. We give a detailed study of the case when m has exactly two distinct prime factors, and classify the minimum possible degree for a symmetric representing polynomial
Keywords :
Boolean functions; computational complexity; polynomials; generalized representation; modular counting; prime factor; symmetric polynomial; weak representation; Boolean functions; Circuits; Computational complexity; Computer science; Polynomials; Protocols; Robustness; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location :
Prague
ISSN :
1093-0159
Print_ISBN :
0-7695-2596-2
Type :
conf
DOI :
10.1109/CCC.2006.29
Filename :
1663738
Link To Document :
بازگشت