18 Search Results for "Magniez, Frédéric"


Document
Invited Talk
Quantum Distributed Computing: Potential and Limitations (Invited Talk)

Authors: François Le Gall

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
The subject of this talk is quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. In the first part of the talk I survey recent results [Taisuke Izumi and François Le Gall, 2019; Taisuke Izumi et al., 2020; François Le Gall and Frédéric Magniez, 2018; François Le Gall et al., 2019; Xudong Wu and Penghui Yao, 2022] and some older results [Michael Ben-Or and Avinatan Hassidim, 2005; Seiichiro Tani et al., 2012] that show the potential of quantum distributed algorithms. In the second part I present our recent work [Xavier Coiteux-Roy et al., 2023] showing the limitations of quantum distributed algorithms for approximate graph coloring. Finally, I mention interesting and important open questions in quantum distributed computing.

Cite as

François Le Gall. Quantum Distributed Computing: Potential and Limitations (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.OPODIS.2023.2,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{Quantum Distributed Computing: Potential and Limitations}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.2},
  URN =		{urn:nbn:de:0030-drops-194925},
  doi =		{10.4230/LIPIcs.OPODIS.2023.2},
  annote =	{Keywords: Quantum computing, distributed algorithms, CONGEST model, LOCAL model}
}
Document
Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs

Authors: Yassine Hamoudi and Frédéric Magniez

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
We study the problem of finding K collision pairs in a random function f : [N] → [N] by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using S qubits of memory must perform a number T of queries that satisfies the tradeoff T³ S ≥ Ω(K³N). Classically, the same question has only been settled recently by Dinur [Dinur, 2020], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener [Oorschot and Wiener, 1999] achieves the optimal time-space tradeoff of T² S = Θ(K² N). Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry’s recording query technique [Zhandry, 2019] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time-space tradeoff T² S ≥ Ω(N³) for sorting N numbers on a quantum computer, which was first obtained by Klauck, Špalek and de Wolf [Klauck et al., 2007].

Cite as

Yassine Hamoudi and Frédéric Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 1:1-1:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hamoudi_et_al:LIPIcs.TQC.2021.1,
  author =	{Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.1},
  URN =		{urn:nbn:de:0030-drops-139961},
  doi =		{10.4230/LIPIcs.TQC.2021.1},
  annote =	{Keywords: Quantum computing, query complexity, lower bound, time-space tradeoff}
}
Document
A Framework of Quantum Strong Exponential-Time Hypotheses

Authors: Harry Buhrman, Subhasree Patro, and Florian Speelman

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in P. As an example, we provide a conditional quantum time lower bound of Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover. Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds.

Cite as

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19,
  author =	{Buhrman, Harry and Patro, Subhasree and Speelman, Florian},
  title =	{{A Framework of Quantum Strong Exponential-Time Hypotheses}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19},
  URN =		{urn:nbn:de:0030-drops-136642},
  doi =		{10.4230/LIPIcs.STACS.2021.19},
  annote =	{Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis}
}
Document
Track A: Algorithms, Complexity and Games
Quantum Distributed Complexity of Set Disjointness on a Line

Authors: Frédéric Magniez and Ashwin Nayak

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
Given x,y ∈ {0,1}ⁿ, Set Disjointness consists in deciding whether x_i = y_i = 1 for some index i ∈ [n]. We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d. Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(log n) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2. We call this problem "Set Disjointness on a Line". Set Disjointness on a Line was introduced by Le Gall and Magniez [Le Gall and Magniez, 2018] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(log n) qubits. In this work, we prove an unconditional lower bound of Ω̃(∛{n d²} + √n) rounds for Set Disjointness on a Line with d + 1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ω̃ (∛{nδ²} + √n) on the number of rounds required for computing the diameter δ of any n-node network with quantum messages of size O(log n) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles 𝒪_x and 𝒪_y, respectively. The restriction is that the algorithm is required to alternately make d queries to 𝒪_x and d queries to 𝒪_y, with input-independent computation in between queries. The model reflects a "switching delay" of d queries between a "round" of queries to x and the following "round" of queries to y. The technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to this query model. We provide an algorithm for Set Disjointness in this query model with query complexity that matches the round lower bound stated above, up to a polylogarithmic factor. In this sense, the round lower bound we show for Set Disjointness on a Line is optimal.

Cite as

Frédéric Magniez and Ashwin Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 82:1-82:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{magniez_et_al:LIPIcs.ICALP.2020.82,
  author =	{Magniez, Fr\'{e}d\'{e}ric and Nayak, Ashwin},
  title =	{{Quantum Distributed Complexity of Set Disjointness on a Line}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{82:1--82:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.82},
  URN =		{urn:nbn:de:0030-drops-124892},
  doi =		{10.4230/LIPIcs.ICALP.2020.82},
  annote =	{Keywords: Quantum distributed computing, Set Disjointness, communication complexity, query complexity}
}
Document
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model

Authors: Taisuke Izumi, François Le Gall, and Frédéric Magniez

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

Cite as

Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 23:1-23:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{izumi_et_al:LIPIcs.STACS.2020.23,
  author =	{Izumi, Taisuke and Le Gall, Fran\c{c}ois and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.23},
  URN =		{urn:nbn:de:0030-drops-118840},
  doi =		{10.4230/LIPIcs.STACS.2020.23},
  annote =	{Keywords: Quantum computing, distributed computing, CONGEST model}
}
Document
Quantum Walk Sampling by Growing Seed Sets

Authors: Simon Apers

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as O~(m^(1/3) delta^(-1/3)), with m the number of edges and delta the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for st-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an n-node graph in time O~(2^(n/3)), surpassing the Omega(2^(n/2)) barrier set by index erasure.

Cite as

Simon Apers. Quantum Walk Sampling by Growing Seed Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 9:1-9:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{apers:LIPIcs.ESA.2019.9,
  author =	{Apers, Simon},
  title =	{{Quantum Walk Sampling by Growing Seed Sets}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.9},
  URN =		{urn:nbn:de:0030-drops-111300},
  doi =		{10.4230/LIPIcs.ESA.2019.9},
  annote =	{Keywords: Quantum algorithms, Quantum walks, Connectivity, Graph theory}
}
Document
Quantum Algorithms for Classical Probability Distributions

Authors: Aleksandrs Belovs

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We study quantum algorithms working on classical probability distributions. We formulate four different models for accessing a classical probability distribution on a quantum computer, which are derived from previous work on the topic, and study their mutual relationships. Additionally, we prove that quantum query complexity of distinguishing two probability distributions is given by their inverse Hellinger distance, which gives a quadratic improvement over classical query complexity for any pair of distributions. The results are obtained by using the adversary method for state-generating input oracles and for distinguishing probability distributions on input strings.

Cite as

Aleksandrs Belovs. Quantum Algorithms for Classical Probability Distributions. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 16:1-16:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{belovs:LIPIcs.ESA.2019.16,
  author =	{Belovs, Aleksandrs},
  title =	{{Quantum Algorithms for Classical Probability Distributions}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{16:1--16:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.16},
  URN =		{urn:nbn:de:0030-drops-111370},
  doi =		{10.4230/LIPIcs.ESA.2019.16},
  annote =	{Keywords: quantum query complexity, quantum adversary method, distinguishing probability distributions, Hellinger distance}
}
Document
Track A: Algorithms, Complexity and Games
Quantum Chebyshev’s Inequality and Applications

Authors: Yassine Hamoudi and Frédéric Magniez

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we consider the approximation of the frequency moments F_k of order k >= 3 in the multi-pass streaming model with updates (turnstile model). We design a P-pass quantum streaming algorithm with memory M satisfying a tradeoff of P^2 M = O~(n^{1-2/k}), whereas the best classical algorithm requires P M = Theta(n^{1-2/k}). Then, we study the problem of estimating the number m of edges and the number t of triangles given query access to an n-vertex graph. We describe optimal quantum algorithms that perform O~(sqrt{n}/m^{1/4}) and O~(sqrt{n}/t^{1/6} + m^{3/4}/sqrt{t}) queries respectively. This is a quadratic speed-up compared to the classical complexity of these problems. For this purpose we develop a new quantum paradigm that we call Quantum Chebyshev’s inequality. Namely we demonstrate that, in a certain model of quantum sampling, one can approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependence is quadratic. Our algorithm subsumes a previous result of Montanaro [Montanaro, 2015]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [Brassard et al., 2002] and of previous quantum algorithms for the mean estimation problem. We show that this speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. Finally, we develop a new technique called "variable-time amplitude estimation" that reduces the dependence of our algorithm on the sample preparation time.

Cite as

Yassine Hamoudi and Frédéric Magniez. Quantum Chebyshev’s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 69:1-69:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{hamoudi_et_al:LIPIcs.ICALP.2019.69,
  author =	{Hamoudi, Yassine and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Quantum Chebyshev’s Inequality and Applications}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{69:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.69},
  URN =		{urn:nbn:de:0030-drops-106458},
  doi =		{10.4230/LIPIcs.ICALP.2019.69},
  annote =	{Keywords: Quantum algorithms, approximation algorithms, sublinear-time algorithms, Monte Carlo method, streaming algorithms, subgraph counting}
}
Document
Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge

Authors: Shalev Ben-David and Robin Kothari

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)


Abstract
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. Using this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. We also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. Lastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.

Cite as

Shalev Ben-David and Robin Kothari. Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.TQC.2019.2,
  author =	{Ben-David, Shalev and Kothari, Robin},
  title =	{{Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.2},
  URN =		{urn:nbn:de:0030-drops-103944},
  doi =		{10.4230/LIPIcs.TQC.2019.2},
  annote =	{Keywords: Quantum query complexity, quantum algorithms}
}
Document
Streaming Communication Protocols

Authors: Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. Input arrives as a stream, spread between several agents across a network. Each agent has a bounded memory, which can be updated upon receiving a new bit, or a message from another agent. We provide tight tradeoffs between the necessary resources, i.e. communication between agents and memory, for some of the canonical problems from communication complexity by proving a strong general lower bound technique. Second, we analyze the Approximate Matching problem and show that the complexity of this problem (i.e. the achievable approximation ratio) in the one-way variant of our model is strictly different both from the streaming complexity and the one-way communication complexity thereof.

Cite as

Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez. Streaming Communication Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 130:1-130:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{boczkowski_et_al:LIPIcs.ICALP.2017.130,
  author =	{Boczkowski, Lucas and Kerenidis, Iordanis and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Streaming Communication Protocols}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{130:1--130:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.130},
  URN =		{urn:nbn:de:0030-drops-74404},
  doi =		{10.4230/LIPIcs.ICALP.2017.130},
  annote =	{Keywords: Networks, Communication Complexity, Streaming Algorithms}
}
Document
Extended Learning Graphs for Triangle Finding

Authors: Titouan Carette, Mathieu Laurière, and Frédéric Magniez

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of O(n^(5/4)) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with m >= n^(5/4) edges, we get a query complexity of O(n^(11/12) m^(1/6) sqrt(log n)), which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when m >= n^(3/2). We also obtain an algorithm with query complexity O(n^(5/6) (m log n)^(1/6) + d_2 sqrt(n)) where d_2 is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall based on the MNRS quantum walk framework [SICOMP'11].

Cite as

Titouan Carette, Mathieu Laurière, and Frédéric Magniez. Extended Learning Graphs for Triangle Finding. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 20:1-20:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.STACS.2017.20,
  author =	{Carette, Titouan and Lauri\`{e}re, Mathieu and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Extended Learning Graphs for Triangle Finding}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.20},
  URN =		{urn:nbn:de:0030-drops-70132},
  doi =		{10.4230/LIPIcs.STACS.2017.20},
  annote =	{Keywords: Quantum query complexity, learning graphs, triangle finding}
}
Document
Stable Matching with Evolving Preferences

Authors: Varun Kanade, Nikos Leonardos, and Frédéric Magniez

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)


Abstract
We consider the problem of stable matching with dynamic preference lists. At each time-step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching, in terms of number of blocking pairs, at all time-steps. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly. We design an algorithm that in expectation and with high probability maintains a matching that has at most O((log n)^2 blocking pairs.

Cite as

Varun Kanade, Nikos Leonardos, and Frédéric Magniez. Stable Matching with Evolving Preferences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 36:1-36:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2016.36,
  author =	{Kanade, Varun and Leonardos, Nikos and Magniez, Fr\'{e}d\'{e}ric},
  title =	{{Stable Matching with Evolving Preferences}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.36},
  URN =		{urn:nbn:de:0030-drops-66597},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.36},
  annote =	{Keywords: Stable Matching, Dynamic Data}
}
Document
Streaming Property Testing of Visibly Pushdown Languages

Authors: Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
In the context of formal language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al., a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs of the language from those that are eps-far from it, while using the smallest possible memory (rather than limiting its number of input queries). Our main result is a streaming eps-property tester for visibly pushdown languages (V_{PL}) with memory space poly(log n /epsilon). Our construction is done in three steps. First, we simulate a visibly pushdown automaton in one pass using a stack of small height but whose items can be of linear size. In a second step, those items are replaced by small sketches. Those sketches rely on a notion of suffix-sampling we introduce. This sampling is the key idea for taking benefit of both streaming algorithms and property testers in the third step. Indeed, the last step relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. This tester can directly be used for streaming testing special cases of instances of V_{PL} that are already hard for both streaming algorithms and property testers. We then use it to decide the correctness of completed items, given their sketches, before removing them from the stack.

Cite as

Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming Property Testing of Visibly Pushdown Languages. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 43:1-43:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{francois_et_al:LIPIcs.ESA.2016.43,
  author =	{Fran\c{c}ois, Nathana\"{e}l and Magniez, Fr\'{e}d\'{e}ric and de Rougemont, Michel and Serre, Olivier},
  title =	{{Streaming Property Testing of Visibly Pushdown Languages}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.43},
  URN =		{urn:nbn:de:0030-drops-63559},
  doi =		{10.4230/LIPIcs.ESA.2016.43},
  annote =	{Keywords: Streaming Algorithm, Property Testing, Visibly Pushdown Languages}
}
Document
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester

Authors: Cedric Yen-Yu Lin and Han-Hsuan Lin

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
Inspired by the Elitzur-Vaidman bomb testing problem [Elitzur/Vaidman 1993], we introduce a new query complexity model, which we call bomb query complexity B(f). We investigate its relationship with the usual quantum query complexity Q(f), and show that B(f)=Theta(Q(f)^2). This result gives a new method to upper bound the quantum query complexity: we give a method of finding bomb query algorithms from classical algorithms, which then provide nonconstructive upper bounds on Q(f)=Theta(sqrt(B(f))). We subsequently were able to give explicit quantum algorithms matching our upper bound method. We apply this method on the single-source shortest paths problem on unweighted graphs, obtaining an algorithm with O(n^(1.5)) quantum query complexity, improving the best known algorithm of O(n^(1.5) * sqrt(log(n))) [Furrow, 2008]. Applying this method to the maximum bipartite matching problem gives an O(n^(1.75)) algorithm, improving the best known trivial O(n^2) upper bound.

Cite as

Cedric Yen-Yu Lin and Han-Hsuan Lin. Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 537-566, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.CCC.2015.537,
  author =	{Lin, Cedric Yen-Yu and Lin, Han-Hsuan},
  title =	{{Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{537--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.537},
  URN =		{urn:nbn:de:0030-drops-50635},
  doi =		{10.4230/LIPIcs.CCC.2015.537},
  annote =	{Keywords: Quantum Algorithms, Query Complexity, Elitzur-Vaidman Bomb Tester, Adversary Method, Maximum Bipartite Matching}
}
Document
Certifying Equality With Limited Interaction

Authors: Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
The EQUALITY problem is usually one’s first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on three subtle aspects. The first is to consider the expected communication cost (at a worst-case input) for a protocol that uses limited interaction—i.e., a bounded number of rounds of communication—and whose error probability is zero or close to it. The second is to treat the false negative error rate separately from the false positive error rate. The third is to consider the information cost of such protocols. We obtain asymptotically optimal rounds-versus-cost tradeoffs for EQUALITY: both expected communication cost and information cost scale as Theta(log log ... log n), with r-1 logs, where r is the number of rounds. These bounds hold even when the false negative rate approaches 1. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. We also provide some applications.

Cite as

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 545-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2014.545,
  author =	{Brody, Joshua and Chakrabarti, Amit and Kondapally, Ranganath and Woodruff, David P. and Yaroslavtsev, Grigory},
  title =	{{Certifying Equality With Limited Interaction}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{545--581},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.545},
  URN =		{urn:nbn:de:0030-drops-47229},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.545},
  annote =	{Keywords: equality, communication complexity, information complexity}
}
  • Refine by Author
  • 10 Magniez, Frédéric
  • 2 François, Nathanaël
  • 2 Hamoudi, Yassine
  • 2 Le Gall, François
  • 1 Apers, Simon
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Quantum computation theory
  • 3 Theory of computation → Quantum complexity theory
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Quantum query complexity
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 4 Streaming Algorithms
  • 3 Quantum computing
  • 2 CONGEST model
  • 2 Communication Complexity
  • 2 Quantum algorithms
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 4 2019
  • 3 2014
  • 2 2016
  • 2 2017
  • 2 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail