125 citations
- Université Paris-SudFR30 papers
- Centre National de la Recherche ScientifiqueFR23 papers
- Institut national de recherche en sciences et technologies du numériqueFR15 papers
- Université Paris CitéFR8 papers
- Centre Inria de SaclayFR7 papers
- Université Paris-SaclayFR6 papers
- Centre for Quantum TechnologiesSG4 papers
- Hungarian Academy of SciencesHU3 papers
- National University of SingaporeSG3 papers
- Développement Adaptation et VieillissementFR2 papers
- HUN-REN Institute for Computer Science and ControlHU2 papers
- Institut d'Astrophysique SpatialeFR2 papers
5 papers · 2 filters
Enhanced algorithms for Local Search
Yves F. Verhoeven
Let G=(V,E) be a finite graph, and f:V->N be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is…
On the black-box complexity of Sperner's Lemma
Katalin Friedl, Gabor Ivanyos, Miklos Santha +1
We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over ps…
Quantum multiparty communication complexity and circuit lower bounds
Iordanis Kerenidis
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show th…
Quantum entanglement enhances the capacity of bosonic channels with memory
Nicolas J. Cerf, Julien Clavareau, Chiara Macchiavello +1
The bosonic quantum channels have recently attracted a growing interest, motivated by the hope that they open a tractable approach to the generally hard problem of evaluating quant…
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…