Circuit complexity of testing square-free numbers

Anna Bernasconi, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

10 Citations (Scopus)

Abstract

In this paper we extend the area of applications of the Abstract Harmonic Analysis to the field of Boolean function complexity. In particular, we extend the class of functions to which a spectral technique developed in a series of works of the first author can be applied. This extension allows us to prove that testing square-free numbers by unbounded fan-in circuits of bounded depth requires a superpolynomial size. This implies the same estimate for the integer factorization problem.

Original languageEnglish
Title of host publicationSTACS 99
Subtitle of host publication16th annual symposium on theoretical aspects of computer science : proceedings
EditorsChristoph Meinel, Sophie Tison
Place of PublicationBerlin ; Heidelberg ; New York
PublisherSpringer, Springer Nature
Pages47-56
Number of pages10
Volume1563
ISBN (Print)354065691X, 9783540656913
Publication statusPublished - 1999
Event16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 - Trier, Germany
Duration: 4 Mar 19996 Mar 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1563
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999
CountryGermany
CityTrier
Period4/03/996/03/99

Fingerprint

Dive into the research topics of 'Circuit complexity of testing square-free numbers'. Together they form a unique fingerprint.

Cite this