3 Search Results for "Balodis, Kaspars"


Document
Track A: Algorithms, Complexity and Games
Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems

Authors: Serge Gaspers and Jerry Zirui Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
Let U be a universe on n elements, let k be a positive integer, and let ℱ be a family of (implicitly defined) subsets of U. We consider the problems of partitioning U into k sets from ℱ, covering U with k sets from ℱ, and packing k non-intersecting sets from ℱ into U. Classically, these problems can be solved via inclusion-exclusion in 2ⁿ n^O(1) time [Andreas Björklund et al., 2009]. Quantumly, there are faster algorithms for graph coloring with running time O(1.9140ⁿ) [Kazuya Shimizu and Ryuhei Mori, 2022] and for Set Cover with a small number of sets with running time O(1.7274ⁿ |ℱ|^O(1)) [Andris Ambainis et al., 2019]. In this paper, we give a quantum speedup for Set Partition, Set Cover, and Set Packing whenever there is a classical enumeration algorithm that lends itself to a quadratic quantum speedup, which, for any subinstance on a set X ⊆ U, enumerates at least one member of a k-partition, k-cover, or k-packing (if one exists) restricted to (or projected onto, in the case of k-cover) the set X in c^|X| n^O(1) time with c < 2. Our bounded-error quantum algorithm runs in time (2+c)^{n/2} n^O(1) for Set Partition, Set Cover, and Set Packing. It is obtained by combining three algorithms that have the best running time for some values of c. When c ≤ 1.147899, our algorithm is slightly faster than (2+c)^{n/2} n^O(1); when c approaches 1, it matches the O(1.7274ⁿ |ℱ|^O(1)) running time of [Andris Ambainis et al., 2019] for Set Cover when |ℱ| is subexponential in n. For covering, packing, and partitioning into maximal independent sets, maximal cliques, maximal bicliques, maximal cluster graphs, maximal triangle-free graphs, maximal cographs, maximal claw-free graphs, maximal trivially-perfect graphs, maximal threshold graphs, maximal split graphs, maximal line graphs, and maximal induced forests, we obtain bounded-error quantum algorithms with running times ranging from O(1.8554ⁿ) to O(1.9629ⁿ). Packing and covering by maximal induced matchings can be done quantumly in O(1.8934ⁿ) time. For Graph Coloring (covering with k maximal independent sets), we further improve the running time to O(1.7956ⁿ) by leveraging faster algorithms for coloring with a small number of colors to better balance our divide-and-conquer steps. For Domatic Number (packing k minimal dominating sets), we obtain a O((2-ε)ⁿ) running time for some ε > 0. Several of our results should be of interest to proponents of classical computing: - We present an inclusion-exclusion algorithm with running time O^*(∑_{i=0}^⌊αn⌋ binom(n,i)), which determines, for each X ⊆ U of size at most α n, 0 ≤ α ≤ 1, whether (X,ℱ) has a k-cover, k-partition, or k-packing. This running time is best-possible, up to polynomial factors. - We prove that for any linear-sized vertex subset X ⊆ V of a graph G = (V,E), the number of minimal dominating sets of G that are subsets of X is O((2-ε)^|X|) for some ε > 0.

Cite as

Serge Gaspers and Jerry Zirui Li. Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ICALP.2024.69,
  author =	{Gaspers, Serge and Li, Jerry Zirui},
  title =	{{Quantum Algorithms for Graph Coloring and Other Partitioning, Covering, and Packing Problems}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{69:1--69:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.69},
  URN =		{urn:nbn:de:0030-drops-202124},
  doi =		{10.4230/LIPIcs.ICALP.2024.69},
  annote =	{Keywords: Graph algorithms, quantum algorithms, graph coloring, domatic number, set cover, set partition, set packing}
}
Document
A Note About Claw Function with a Small Range

Authors: Andris Ambainis, Kaspars Balodis, and Jānis Iraids

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


Abstract
In the claw detection problem we are given two functions f:D → R and g:D → R (|D| = n, |R| = k), and we have to determine if there is exist x,y ∈ D such that f(x) = g(y). We show that the quantum query complexity of this problem is between Ω(n^{1/2}k^{1/6}) and O(n^{1/2+ε}k^{1/4}) when 2 ≤ k < n.

Cite as

Andris Ambainis, Kaspars Balodis, and Jānis Iraids. A Note About Claw Function with a Small Range. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 6:1-6:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2021.6,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis},
  title =	{{A Note About Claw Function with a Small Range}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{6:1--6:5},
  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.6},
  URN =		{urn:nbn:de:0030-drops-140013},
  doi =		{10.4230/LIPIcs.TQC.2021.6},
  annote =	{Keywords: collision, claw, quantum query complexity}
}
Document
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Authors: Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the Dyck_{k,n} problem. We prove a lower bound of Ω(c^k √n), showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising Õ(√n) query quantum algorithm was recently constructed by Aaronson et al. [Scott Aaronson et al., 2018]. Their proof does not give rise to a general algorithm. When k is not a constant, Dyck_{k,n} is not context-free. We give an algorithm with O(√n(log n)^{0.5k}) quantum queries for Dyck_{k,n} for all k. This is better than the trival upper bound n for k = o({log(n)}/{log log n}). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n^{1.5-ε}) for the directed 2D grid and Ω(n^{2-ε}) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

Cite as

Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.MFCS.2020.8,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis and Khadiev, Kamil and K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Shen, Yixin and Smotrovs, Juris and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-126774},
  doi =		{10.4230/LIPIcs.MFCS.2020.8},
  annote =	{Keywords: Quantum query complexity, Quantum algorithms, Dyck language, Grid path}
}
  • Refine by Author
  • 2 Ambainis, Andris
  • 2 Balodis, Kaspars
  • 2 Iraids, Jānis
  • 1 Gaspers, Serge
  • 1 Khadiev, Kamil
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum query complexity
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Dyck language
  • 1 Graph algorithms
  • 1 Grid path
  • 1 Quantum algorithms
  • 1 Quantum query complexity
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2024