On polynomial representations of boolean functions related to some number theoretic problems

Erion Plaku, Igor E. Shparlinski

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

1 Citation (Scopus)

Abstract

We say a polynomial P over ZM strongly M-represents a Boolean function F if F(x) ≡ P(x) (mod M) for all x ∈ {0, 1}n. Similarly, P one-sidedly M-represents F if F(x) = 0 ⇐⇒ P(x) ≡ 0 (mod M) for all x ∈ {0, 1}n. Lower bounds are obtained on the degree and the number of monomials of polynomials over ZM, which strongly or one-sidedly M-represent the Boolean function deciding if a given nbit integer is square-free. Similar lower bounds are also obtained for polynomials over the reals which provide a threshold representation of the above Boolean function.

Original languageEnglish
Title of host publicationFST TCS 2001: Foundations of Software Technology and Theoretical Computer Science
Subtitle of host publication21st Conference Bangalore, India, December 13–15, 2001 Proceedings
EditorsRamesh Hariharan, V. Vinay, Madhavan Mukund
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages305-316
Number of pages12
ISBN (Electronic)9783540452942
ISBN (Print)3540430024, 9783540430025
DOIs
Publication statusPublished - Dec 2001
Event21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS - 2001 - Bangalore, India
Duration: 13 Dec 200115 Dec 2001

Publication series

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

Other

Other21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS - 2001
Country/TerritoryIndia
CityBangalore
Period13/12/0115/12/01

Fingerprint

Dive into the research topics of 'On polynomial representations of boolean functions related to some number theoretic problems'. Together they form a unique fingerprint.

Cite this