The garden hose complexity for the equality function

DOI10.1007/978-3-319-07956-1_11MaRDI QIDQ5251639zbMATH OpenOpenAlexFDO

Authors Well Y. Chiu, Chengu Wang, Yixin Xu, Mario Szegedy

Publication date 20 May 2015

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.7222

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Permutation groups (20B99) Communication complexity, information complexity (68Q11)

Abstract: The garden hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman [BFSS13] to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of O. Margalit and A. Matsliah[MM12] with the help of a new approach and of our handmade simulated annealing based solver. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of garden hose permutation groups. Then, exploiting this new concept, we get even further, although several interesting open problems remain.

Recommendations

• The garden-hose model
• New bounds for the garden-hose model
• Equality, revisited
• scientific article; zbMATH DE number 1769898
• Quantum multiparty communication complexity and circuit lower bounds

Cited in

(4)

• The garden-hose model
• Communication memento: memoryless communication complexity
• Quantum cryptography beyond quantum key distribution
• New bounds for the garden-hose model

This page was built for publication: The garden hose complexity for the equality function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251639)