ﻻ يوجد ملخص باللغة العربية
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.
In this paper, we study quantum query complexity of the following rather natural tripartite generalisations (in the spirit of the 3-sum problem) of the hidden shift and the set equality problems, which we call the 3-shift-sum and the 3-matching-sum p
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $epsilon$, getting the optimal constant factors in the leading terms in a number of different models. In the ran
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificate
Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find th
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof