NDLI: The garden-hose model

Please wait, while we are loading the content...

Massive online teaching to bounded learners

Can theories be tested?: a cryptographic treatment of forecast testing

Is privacy compatible with truthfulness?

On the possibilities and limitations of pseudodeterministic algorithms

Towards an optimal query efficient PCP?

Approaching utopia: strong truthfulness and externality-resistant mechanisms

Reachability in graph timelines

A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games

An equational approach to secure multi-party computation

Time hierarchies for sampling distributions

Catch them if you can: how to serve impatient users

New affine-invariant codes from lifting

Learning mixtures of spherical gaussians: moment methods and spectral decompositions

Multiplicative updates in coordination games and the theory of evolution

Differentially private data analysis of social networks via restricted sensitivity

Evasiveness through a circuit lens

A characterization of approximation resistance for even k-partite CSPs

Parametric digital auctions

Runtime guarantees for regression problems

Adversary lower bound for the k-sum problem

Publicly verifiable proofs of sequential work

Properties and applications of boolean function composition

Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints

H-wise independence

Low-weight halfspaces for sparse boolean vectors

Making evolution rigorous: the error threshold

Characterizing the sample complexity of private learners

The garden-hose model

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction

Learning and incentives in user-generated content: multi-armed bandits with endogenous arms

An energy complexity model for algorithms

Stronger methods of making quantum interactive proofs perfectly complete

On the power of nonuniformity in proofs of security

Pseudo-partitions, transversality and locality: a combinatorial characterization for the space measure in algebraic proof systems

Robust optimization in the presence of uncertainty

Sparse extractor families for all the entropy

Learnability of DNF with representation-specific queries

On the convergence of the Hegselmann-Krause system

Barriers in cryptography with weak, correlated and leaky sources

Space-bounded communication complexity

On the power of many one-bit provers

Welfare maximization and the supermodular degree

Streaming computations with a loquacious prover

Active self-assembly of algorithmic shapes and patterns in polylogarithmic time

Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract

Competing provers protocols for circuit evaluation

Sorting noisy data with partial information

On the power of conditional samples in distribution testing

Resource-based corruptions and the combinatorics of hidden diversity

The garden-hose model

Content Provider	ACM Digital Library
Author	Schaffner, Christian Fehr, Serge Speelman, Florian Buhrman, Harry
Abstract	We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function $f:\{0,1\}^{n}$ x $\{0,1\}^{n}$ -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ $\{0,1\}^{n}$ and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ $\{0,1\}^{n}.$ Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y). We prove almost-linear lower bounds on the garden-hose complexity for concrete functions like inner product, majority, and equality, and we show the existence of functions with exponential garden-hose complexity. Furthermore, we show a connection to classical complexity theory by proving that all functions computable in log-space have polynomial garden-hose complexity. We consider a randomized variant of the garden-hose complexity, where Alice and Bob hold pre-shared randomness, and a quantum variant, where Alice and Bob hold pre-shared quantum entanglement, and we show that the randomized garden-hose complexity is within a polynomial factor of the deterministic garden-hose complexity. Examples of (partial) functions are given where the quantum garden-hose complexity is logarithmic in n while the classical garden-hose complexity can be lower bounded by $n^{c}$ for constant c>0. Finally, we show an interesting connection between the garden-hose model and the (in)security of a certain class of quantum position-verification schemes.
Starting Page	145
Ending Page	158
Page Count	14
File Format	PDF
ISBN	9781450318594
DOI	10.1145/2422436.2422455
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-01-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Communication complexity Garden-hose model Position-based quantum cryptography
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The garden-hose model.

The Garden-Hose Game and Application to Position-Based Quantum Cryptography

The garden-hose game: A new model of computation, and application to position-based quantum cryptography (2011)

New Bounds for the Garden-Hose Model

Position-Based Quantum Cryptography and the Garden-Hose Game

On the riddle of coding equality function in the garden hose model

The Garden-Hose Model

The Garden Hose Complexity for the Equality Function

The Garden Hose Complexity for the Equality Function (2013)

The garden-hose model

Similar Documents

The garden-hose model.

The Garden-Hose Game and Application to Position-Based Quantum Cryptography

The garden-hose game: A new model of computation, and application to position-based quantum cryptography (2011)

New Bounds for the Garden-Hose Model

Position-Based Quantum Cryptography and the Garden-Hose Game

On the riddle of coding equality function in the garden hose model

The Garden-Hose Model

The Garden Hose Complexity for the Equality Function

The Garden Hose Complexity for the Equality Function (2013)

The garden-hose model