88 citations
- University of AmsterdamNL11 papers
- College of Western IdahoUS3 papers
- Vrije Universiteit AmsterdamNL3 papers
- Universidad Pública de Navarra (UPNA)ES2 papers
- University of CambridgeGB2 papers
- University of TwenteNL2 papers
- Berkeley CollegeUS1 paper
- Eindhoven University of TechnologyNL1 paper
- Goethe University FrankfurtDE1 paper
- Institute for Advanced StudyUS1 paper
- Laboratoire de Recherche en InformatiqueFR1 paper
- Lomonosov Moscow State UniversityRU1 paper
5 papers · 2 filters
Quantum Algorithms for Matching and Network Flows
Andris Ambainis, Robert Spalek
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time…
Entanglement in Interactive Proof Systems with Binary Answers
Stephanie Wehner
If two classical provers share an entangled state, the resulting interactive proof system is significantly weakened [quant-ph/0404076]. We show that for the case where the verifier…
Lower Bounds on Matrix Rigidity via a Quantum Argument
Ronald de Wolf
The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix woul…
Implications of Superstrong Nonlocality for Cryptography
Harry Buhrman, Matthias Christandl, Falk Unger +2
Non-local boxes are hypothetical ``machines'' that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/CHSH inequalities than is possible withi…
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has b…