Aarhus University Seal / Aarhus Universitets segl

On Modular Counting with Polynomials

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
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 Z_m of degree O(\sqrt n) 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.
Original languageEnglish
Title of host publication21st Annual IEEE Conference on Computational Complexity (CCC'06)
Number of pages8
PublisherIEEE Computer Society Press
Publication year2006
ISBN (print)0-7695-2596-2
Publication statusPublished - 2006
EventAnnual IEEE Conference on Computational Complexity (CCC'06) - Prague, Czech Republic
Duration: 16 Jul 200620 Jul 2006
Conference number: 21


ConferenceAnnual IEEE Conference on Computational Complexity (CCC'06)
LandCzech Republic

See relations at Aarhus University Citationformats

ID: 3630507