Communication complexity of some number theoretic functions

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

We show that the communication complexity of the parity of the sum of binary digits of x + y is at least 0.085667 ... n + O (1) where x and y are n-bit integers. We also obtain a nontrivial (but weaker) lower bound on the parity of the total number of prime divisors of x + y counted with multiplicity.

Original languageEnglish
Pages (from-to)872-875
Number of pages4
JournalApplied Mathematics Letters
Volume20
Issue number8
DOIs
Publication statusPublished - Aug 2007

Fingerprint Dive into the research topics of 'Communication complexity of some number theoretic functions'. Together they form a unique fingerprint.

Cite this