Communication complexity of some number theoretic functions

Igor E. Shparlinski

doi:10.1016/j.aml.2006.05.024

Communication complexity of some number theoretic functions

Igor E. Shparlinski^*

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	872-875
Number of pages	4
Journal	Applied Mathematics Letters
Volume	20
Issue number	8
DOIs	https://doi.org/10.1016/j.aml.2006.05.024
Publication status	Published - Aug 2007

Access to Document

10.1016/j.aml.2006.05.024

Cite this

@article{9933ec3c6d264fe48f6811bd332e991c,

title = "Communication complexity of some number theoretic functions",

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

author = "Shparlinski, {Igor E.}",

year = "2007",

month = aug,

doi = "10.1016/j.aml.2006.05.024",

language = "English",

volume = "20",

pages = "872--875",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - Communication complexity of some number theoretic functions

AU - Shparlinski, Igor E.

PY - 2007/8

Y1 - 2007/8

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

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

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

U2 - 10.1016/j.aml.2006.05.024

DO - 10.1016/j.aml.2006.05.024

M3 - Article

AN - SCOPUS:34047109109

VL - 20

SP - 872

EP - 875

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 8

ER -

Communication complexity of some number theoretic functions

Abstract

Access to Document

Other files and links

Fingerprint

Cite this