[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

The Garden Hose Complexity for the Equality Function

  • Conference paper
Algorithmic Aspects in Information and Management (AAIM 2014)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8546))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-Based Quantum Cryptography: Impossibility and Constructions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 429–446. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  2. Buhrman, H., Fehr, S., Schaffner, C.: Position-Based Quantum Cryptography. ERCIM News 2011(85), 16–17 (2011)

    Google Scholar 

  3. Buhrman, H., Fehr, S., Schaffner, C., Speelman, F.: The garden-hose model. In: ITCS, pp. 145–158 (2013)

    Google Scholar 

  4. Chandran, N., Goyal, V., Moriarty, R., Ostrovsky, R.: Position Based Cryptography. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 391–407. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  5. Margalit, O., Matsliah, A.: Mage - the CDCL SAT solver developed and used by IBM for formal verification. Personal Communication (2012), http://ibm.co/P7qNpC

  6. Orellana, R.C., Orrison, M.E., Rockmore, D.N.: Rooted trees and iterated wreath products of cyclic groups. Advances in Applied Mathematics 33(3), 531–547 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Pfeiffer, G., Merkwitz, T.: GAP Data Library “Tables of Marks”, http://www.gap-system.org/Datalib/tom.html

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, National Chiao Tung University, 1001 University Road, Hsinchu, 300, Taiwan

    Well Y. Chiu

  2. Department of Computer Science, Rutgers, The State University of New Jersey, 110 Frelinghuysen Road, Piscataway, NJ, 08854, USA

    Mario Szegedy & Yixin Xu

  3. Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA, 94043, USA

    Chengu Wang

Authors
  1. Well Y. Chiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mario Szegedy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chengu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yixin Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computing Science, Simon Fraser University, V5A 1S6, Burnaby, BC, Canada

    Qianping Gu  & Pavol Hell  & 

  2. Department of Computer Science, University of Regina, S4S 0A2, Regina, SK, Canada

    Boting Yang

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Chiu, W.Y., Szegedy, M., Wang, C., Xu, Y. (2014). The Garden Hose Complexity for the Equality Function. In: Gu, Q., Hell, P., Yang, B. (eds) Algorithmic Aspects in Information and Management. AAIM 2014. Lecture Notes in Computer Science, vol 8546. Springer, Cham. https://doi.org/10.1007/978-3-319-07956-1_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-07956-1_11

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-07955-4

  • Online ISBN: 978-3-319-07956-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation