Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Better Boosting of Communication Oracles, or Not
 
conference paper

Better Boosting of Communication Oracles, or Not

Harms, Nathaniel  
•
Riazanov, Artur  
Barman, Siddharth
•
Lasota, Slawomir
December 5, 2024
Leibniz International Proceedings in Informatics, LIPIcs
44 IARCS Conference on Foundations of Software Technology and Theoretical Computer Science

Suppose we have a two-party communication protocol for f which allows the parties to make queries to an oracle computing g; for example, they may query an Equality oracle. To translate this protocol into a randomized protocol, we must replace the oracle with a randomized subroutine for solving g. If q queries are made, the standard technique requires that we boost the error of each subroutine down to O(1/q), leading to communication complexity which grows as q log q. For which oracles g can this naïve boosting technique be improved? We focus on the oracles which can be computed by constant-cost randomized protocols, and show that the naïve boosting strategy can be improved for the Equality oracle but not the 1-Hamming Distance oracle. Two surprising consequences are (1) a new example of a problem where the cost of computing k independent copies grows superlinear in k, drastically simplifying the only previous example due to Blais & Brody (CCC 2019); and (2) a new proof that Equality is not complete for the class of constant-cost randomized communication (Harms, Wild, & Zamaraev, STOC 2022; Hambardzumyan, Hatami, & Hatami, Israel Journal of Mathematics 2022).

  • Details
  • Metrics
Type
conference paper
DOI
10.4230/LIPIcs.FSTTCS.2024.25
Scopus ID

2-s2.0-85213118876

Author(s)
Harms, Nathaniel  

École Polytechnique Fédérale de Lausanne

Riazanov, Artur  

École Polytechnique Fédérale de Lausanne

Editors
Barman, Siddharth
•
Lasota, Slawomir
Date Issued

2024-12-05

Publisher

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Published in
Leibniz International Proceedings in Informatics, LIPIcs
ISBN of the book

9783959773553

Book part number

323

Article Number

25

Subjects

communication complexity

•

error reduction

•

oracles

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL5  
Event nameEvent acronymEvent placeEvent date
44 IARCS Conference on Foundations of Software Technology and Theoretical Computer Science

Gandhinagar, India

2024-12-16 - 2024-12-18

FunderFunding(s)Grant NumberGrant URL

NSERC

SERI

MB22.00026

Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/245012
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés