Circuit complexity of testing square-free numbers

Anna Bernasconi; Igor Shparlinski

Circuit complexity of testing square-free numbers

Anna Bernasconi, Igor Shparlinski

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-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 language	English
Title of host publication	STACS 99
Subtitle of host publication	16th annual symposium on theoretical aspects of computer science : proceedings
Editors	Christoph Meinel, Sophie Tison
Place of Publication	Berlin ; Heidelberg ; New York
Publisher	Springer, Springer Nature
Pages	47-56
Number of pages	10
Volume	1563
ISBN (Print)	354065691X, 9783540656913
Publication status	Published - 1999
Event	16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 - Trier, Germany Duration: 4 Mar 1999 → 6 Mar 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1563
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999
Country/Territory	Germany
City	Trier
Period	4/03/99 → 6/03/99

Cite this

Bernasconi, A., & Shparlinski, I. (1999). Circuit complexity of testing square-free numbers. In C. Meinel, & S. Tison (Eds.), STACS 99: 16th annual symposium on theoretical aspects of computer science : proceedings (Vol. 1563, pp. 47-56). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1563). Springer, Springer Nature.

Bernasconi, Anna ; Shparlinski, Igor. / Circuit complexity of testing square-free numbers. STACS 99: 16th annual symposium on theoretical aspects of computer science : proceedings. editor / Christoph Meinel ; Sophie Tison. Vol. 1563 Berlin ; Heidelberg ; New York : Springer, Springer Nature, 1999. pp. 47-56 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{da3a071d1e5a454faaa2b5d338a34392,

title = "Circuit complexity of testing square-free numbers",

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.",

author = "Anna Bernasconi and Igor Shparlinski",

year = "1999",

language = "English",

isbn = "354065691X",

volume = "1563",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "47--56",

editor = "Christoph Meinel and Sophie Tison",

booktitle = "STACS 99",

address = "United States",

note = "16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 ; Conference date: 04-03-1999 Through 06-03-1999",

}

Bernasconi, A & Shparlinski, I 1999, Circuit complexity of testing square-free numbers. in C Meinel & S Tison (eds), STACS 99: 16th annual symposium on theoretical aspects of computer science : proceedings. vol. 1563, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1563, Springer, Springer Nature, Berlin ; Heidelberg ; New York, pp. 47-56, 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999, Trier, Germany, 4/03/99.

Circuit complexity of testing square-free numbers. / Bernasconi, Anna; Shparlinski, Igor.
STACS 99: 16th annual symposium on theoretical aspects of computer science : proceedings. ed. / Christoph Meinel; Sophie Tison. Vol. 1563 Berlin ; Heidelberg ; New York: Springer, Springer Nature, 1999. p. 47-56 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1563).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Circuit complexity of testing square-free numbers

AU - Bernasconi, Anna

AU - Shparlinski, Igor

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957073688&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:84957073688

SN - 354065691X

SN - 9783540656913

VL - 1563

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 47

EP - 56

BT - STACS 99

A2 - Meinel, Christoph

A2 - Tison, Sophie

PB - Springer, Springer Nature

CY - Berlin ; Heidelberg ; New York

T2 - 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999

Y2 - 4 March 1999 through 6 March 1999

ER -

Bernasconi A, Shparlinski I. Circuit complexity of testing square-free numbers. In Meinel C, Tison S, editors, STACS 99: 16th annual symposium on theoretical aspects of computer science : proceedings. Vol. 1563. Berlin ; Heidelberg ; New York: Springer, Springer Nature. 1999. p. 47-56. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Circuit complexity of testing square-free numbers

Abstract

Publication series

Other

Other files and links

Fingerprint

Cite this