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. Communication Complexity of Collision
 
conference paper

Communication Complexity of Collision

Göös, Mika  
•
Jain, Siddhartha  
2022
Leibniz International Proceedings in Informatics (LIPIcs)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each x_i and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021). LIPIcs, Vol. 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 19:1-19:9

  • Details
  • Metrics
Type
conference paper
DOI
10.4230/lipics.approx/random.2022.19
Author(s)
Göös, Mika  
Jain, Siddhartha  
Date Issued

2022

Publisher

Leibniz-Zentrum für Informatik

Published in
Leibniz International Proceedings in Informatics (LIPIcs)
ISBN of the book

978-3-95977-249-5

Volume

245

Start page

19:1

End page

19:9

Subjects

Collision

•

Communication complexity

•

Lifting

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL5  
Event nameEvent placeEvent date
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

University of Illinois, Urbana-Champaign, USA (Virtual Conference)

September 19-21, 2022

Available on Infoscience
January 17, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/193986
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