The Experts below are selected from a list of 210 Experts worldwide ranked by ideXlab platform
Florian Speelman - One of the best experts on this subject based on the ideXlab platform.
-
ITCS - The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 nc 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.
-
The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 to {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 \in {0,1}^n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y \in {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.
-
position based quantum cryptography and the Garden Hose game
arXiv: Quantum Physics, 2012Co-Authors: Florian SpeelmanAbstract:We study position-based cryptography in the quantum setting. We examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. To this end, we define a new model of communication complexity, the Garden-Hose model, which enables us to prove upper bounds on the number of EPR pairs needed to attack such schemes. This model furthermore opens up a way to link the security of position-based quantum cryptography to traditional complexity theory.
Harry Buhrman - One of the best experts on this subject based on the ideXlab platform.
-
ITCS - The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 nc 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.
-
The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 to {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 \in {0,1}^n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y \in {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.
Serge Fehr - One of the best experts on this subject based on the ideXlab platform.
-
ITCS - The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 nc 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.
-
The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 to {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 \in {0,1}^n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y \in {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.
Christian Schaffner - One of the best experts on this subject based on the ideXlab platform.
-
ITCS - The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 nc 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.
-
The Garden-Hose model
Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13, 2013Co-Authors: Harry Buhrman, Christian Schaffner, Serge Fehr, Florian SpeelmanAbstract: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 to {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 \in {0,1}^n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y \in {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.
Daniel Evanko - One of the best experts on this subject based on the ideXlab platform.
-
microfluidics and a Garden Hose
Nature Methods, 2008Co-Authors: Daniel EvankoAbstract:Microfluidics devices are well known for their ability to perform complex manipulations on minute samples, but they can also be powerful tools for analyzing large sample volumes.
