14 Search Results for "Hamoudi, Yassine"

Document
DOI: 10.4230/LIPIcs.STACS.2026.57
Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach

Authors: Antoine Joux and Karol Węgrzycki

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Lagarias and Odlyzko (J.ACM 1985) proposed a polynomial-time algorithm for solving "almost all" instances of the Subset Sum problem with n integers of size Ω(Γ_LO), where log₂(Γ_LO) > n² log₂(γ) and γ is a parameter of the lattice basis reduction (γ > √{4/3} for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone of cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm that solves "almost all" instances of Subset Sum with integers of size Ω(√{Γ_LO}) after a single call to lattice reduction. Additionally, our approach allows solving the Subset Sum problem for multiple targets, whereas the previous method could handle only one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem, leveraging lattice reduction to solve a linear system modulo a suitably large prime. By analyzing the lengths of the LLL-reduced basis vectors of both the primal and dual lattices simultaneously, we show that density guarantees can be improved.
Cite as

Antoine Joux and Karol Węgrzycki. Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{joux_et_al:LIPIcs.STACS.2026.57,
  author =	{Joux, Antoine and W\k{e}grzycki, Karol},
  title =	{{Improving Lagarias-Odlyzko Algorithm for Average-Case Subset Sum: Modular Arithmetic Approach}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.57},
  URN =		{urn:nbn:de:0030-drops-255462},
  doi =		{10.4230/LIPIcs.STACS.2026.57},
  annote =	{Keywords: Average-Case Analysis, Subset Sum, Lattice Reduction, LLL}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.51
Quantum Approximate k-Minimum Finding

Authors: Minbo Gao, Zhengfeng Ji, and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum k-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum k-minimum finding algorithm that works with approximate values for all k ≥ 1, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for k = 1. As practical applications, we present efficient quantum algorithms for identifying the k smallest expectation values among multiple observables and for determining the k lowest ground state energies of a Hamiltonian with a known eigenbasis.
Cite as

Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum Approximate k-Minimum Finding. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2025.51,
  author =	{Gao, Minbo and Ji, Zhengfeng and Wang, Qisheng},
  title =	{{Quantum Approximate k-Minimum Finding}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.51},
  URN =		{urn:nbn:de:0030-drops-245192},
  doi =		{10.4230/LIPIcs.ESA.2025.51},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Quantum Minimum Finding}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.86
New Algorithms for Pigeonhole Equal Subset Sum

Authors: Ce Jin, Ryan Williams, and Stan Zhang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the Pigeonhole Equal Subset Sum problem, which is a total-search variant of the Subset Sum problem introduced by Papadimitriou (1994): we are given a set of n positive integers {w₁,…,w_n} with the additional restriction that ∑_{i=1}^n w_i < 2ⁿ - 1, and want to find two different subsets A,B ⊆ [n] such that ∑_{i∈A} w_i = ∑_{i∈B} w_i. Very recently, Jin and Wu (ICALP 2024) gave a randomized algorithm solving Pigeonhole Equal Subset Sum in O^*(2^{0.4n}) time, beating the classical meet-in-the-middle algorithm with O^*(2^{n/2}) runtime. In this paper, we refine Jin and Wu’s techniques to improve the runtime even further to O^*(2^{n/3}).
Cite as

Ce Jin, Ryan Williams, and Stan Zhang. New Algorithms for Pigeonhole Equal Subset Sum. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 86:1-86:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ESA.2025.86,
  author =	{Jin, Ce and Williams, Ryan and Zhang, Stan},
  title =	{{New Algorithms for Pigeonhole Equal Subset Sum}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{86:1--86:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.86},
  URN =		{urn:nbn:de:0030-drops-245541},
  doi =		{10.4230/LIPIcs.ESA.2025.86},
  annote =	{Keywords: pigeonhole principle, subset sums}
}
Document
DOI: 10.4230/LIPIcs.TQC.2025.7
Uniformity Testing When You Have the Source Code

Authors: Clément L. Canonne, Robin Kothari, and Ryan O'Donnell

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on [d] or ε-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is ε-far from it. For both problems, the previous best known upper bound was O(min{d^{1/3}/ε²,d^{1/2}/ε}). Here we improve the upper bound to O(min{d^{1/3}/ε^{4/3}, d^{1/2}/ε}), which we conjecture is optimal.
Cite as

Clément L. Canonne, Robin Kothari, and Ryan O'Donnell. Uniformity Testing When You Have the Source Code. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.TQC.2025.7,
  author =	{Canonne, Cl\'{e}ment L. and Kothari, Robin and O'Donnell, Ryan},
  title =	{{Uniformity Testing When You Have the Source Code}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.7},
  URN =		{urn:nbn:de:0030-drops-240561},
  doi =		{10.4230/LIPIcs.TQC.2025.7},
  annote =	{Keywords: distribution testing, uniformity testing, quantum algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.61
How to Compute the Volume in Low Dimension?

Authors: Arjan Cornelissen, Simon Apers, and Sander Gribling

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, and computational geometry. In particular, determining the query complexity of volume estimation to a membership oracle has been a longstanding open question. Most of the previous work focuses on the high-dimensional limit. In this work, we tightly characterize the deterministic, randomized and quantum query complexity of this problem in the high-precision limit, i.e., when the dimension is constant.
Cite as

Arjan Cornelissen, Simon Apers, and Sander Gribling. How to Compute the Volume in Low Dimension?. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cornelissen_et_al:LIPIcs.ICALP.2025.61,
  author =	{Cornelissen, Arjan and Apers, Simon and Gribling, Sander},
  title =	{{How to Compute the Volume in Low Dimension?}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{61:1--61:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.61},
  URN =		{urn:nbn:de:0030-drops-234381},
  doi =		{10.4230/LIPIcs.ICALP.2025.61},
  annote =	{Keywords: Query complexity, computational geometry, quantum computing, volume estimation, high-precision limit}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.13
Quantum Speedup for Sampling Random Spanning Trees

Authors: Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
Cite as

Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu. Quantum Speedup for Sampling Random Spanning Trees. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ICALP.2025.13,
  author =	{Apers, Simon and Gao, Minbo and Ji, Zhengfeng and Liu, Chenghua},
  title =	{{Quantum Speedup for Sampling Random Spanning Trees}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.13},
  URN =		{urn:nbn:de:0030-drops-233907},
  doi =		{10.4230/LIPIcs.ICALP.2025.13},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Random Spanning Trees}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.14
The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions

Authors: Huck Bennett, Surendra Ghentiyala, and Noah Stephens-Davidowitz

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We show a number of connections between two types of search problems: (1) the problem of finding an L-wise multicollision in the output of a function; and (2) the problem of finding two codewords in a code (or two vectors in a lattice) that are within distance d of each other. Specifically, we study these problems in the total regime, in which L and d are chosen so that such a solution is guaranteed to exist, though it might be hard to find. In more detail, we study the total search problem in which the input is a function 𝒞 : [A] → [B] (represented as a circuit) and the goal is to find L ≤ ⌈A/B⌉ distinct elements x_1,…, x_L ∈ A such that 𝒞(x_1) = ⋯ = 𝒞(x_L). The associated complexity classes Polynomial Multi-Pigeonhole Principle ((A,B)-PMPP^L) consist of all problems that reduce to this problem. We show close connections between (A,B)-PMPP^L and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding two distinct codewords or lattice points that are close to each other) are in (A,B)-PMPP^L, with a more-or-less smooth tradeoff between the distance d and the parameters A, B, and L. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that the computational problems associated with some bounds on the minimum distance of codes are actually hard for these classes (for codes represented by arbitrary circuits). In fact, we show that finding two vectors within a certain distance d is actually hard for the important (and well-studied) class PWPP = (B²,B)-PMPP² in essentially all parameter regimes for which an efficient algorithm is not known, so that our hardness results are essentially tight. In fact, for some d (depending on the block length, message length, and alphabet size), we obtain both hardness and containment. We therefore completely settle the complexity of this problem for such parameters and add coding problems to the short list of problems known to be complete for PWPP. We also study (A,B)-PMPP^L as an interesting family of complexity classes in its own right, and we uncover a rich structure. Specifically, we use recent techniques from the cryptographic literature on multicollision-resistant hash functions to (1) show inclusions of the form (A,B)-PMPP^L ⊆ (A',B')-PMPP^L' for certain non-trivial parameters; (2) black-box separations between such classes in different parameter regimes; and (3) a non-black-box proof that (A,B)-PMPP^L ∈ FP if (A',B')-PMPP^L' ∈ FP for yet another parameter regime. We also show that (A,B)-PMPP^L lies in the recently introduced complexity class Polynomial Long Choice for some parameters.
Cite as

Huck Bennett, Surendra Ghentiyala, and Noah Stephens-Davidowitz. The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bennett_et_al:LIPIcs.ITCS.2025.14,
  author =	{Bennett, Huck and Ghentiyala, Surendra and Stephens-Davidowitz, Noah},
  title =	{{The More the Merrier! On Total Coding and Lattice Problems and the Complexity of Finding Multicollisions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.14},
  URN =		{urn:nbn:de:0030-drops-226424},
  doi =		{10.4230/LIPIcs.ITCS.2025.14},
  annote =	{Keywords: Multicollisions, Error-correcting codes, Lattices}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.95
Toward Separating QMA from QCMA with a Classical Oracle

Authors: Mark Zhandry

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds.
Cite as

Mark Zhandry. Toward Separating QMA from QCMA with a Classical Oracle. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 95:1-95:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhandry:LIPIcs.ITCS.2025.95,
  author =	{Zhandry, Mark},
  title =	{{Toward Separating QMA from QCMA with a Classical Oracle}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{95:1--95:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.95},
  URN =		{urn:nbn:de:0030-drops-227230},
  doi =		{10.4230/LIPIcs.ITCS.2025.95},
  annote =	{Keywords: Quantum, Oracle Separations, QMA, QCMA}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.64
Improved Quantum Boosting

Authors: Adam Izdebski and Ronald de Wolf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity [Srinivasan Arunachalam and Reevu Maity, 2020] gave the first quantum improvement for boosting, by combining Freund and Schapire’s AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner’s hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio’s SmoothBoost algorithm [Servedio, 2003].
Cite as

Adam Izdebski and Ronald de Wolf. Improved Quantum Boosting. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{izdebski_et_al:LIPIcs.ESA.2023.64,
  author =	{Izdebski, Adam and de Wolf, Ronald},
  title =	{{Improved Quantum Boosting}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.64},
  URN =		{urn:nbn:de:0030-drops-187178},
  doi =		{10.4230/LIPIcs.ESA.2023.64},
  annote =	{Keywords: Learning theory, Boosting algorithms, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.6
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Authors: Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Subset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains a subset whose elements sum to a target value m. The best known classical and quantum algorithms run in time Õ(2^{n/2}) and Õ(2^{n/3}), respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus p, our data structure can be constructed in time O(np), after which queries can be made in time O(n) to the lists of subsets summing to any value modulo p. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an O(2^{0.504n}) quantum algorithm for Shifted-Sums. This provides a notable improvement on the best known O(2^{0.773n}) classical running time established by Mucha et al. [Mucha et al., 2019]. We also study Pigeonhole Equal-Sums, a variant of Equal-Sums where the existence of a solution is guaranteed by the pigeonhole principle. For this problem we give faster classical and quantum algorithms with running time Õ(2^{n/2}) and Õ(2^{2n/5}), respectively.
Cite as

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{allcock_et_al:LIPIcs.ESA.2022.6,
  author =	{Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh\"{o}fer, Felix and Santha, Miklos},
  title =	{{Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.6},
  URN =		{urn:nbn:de:0030-drops-169444},
  doi =		{10.4230/LIPIcs.ESA.2022.6},
  annote =	{Keywords: Quantum algorithm, classical algorithm, dynamic programming, representation technique, subset-sum, equal-sum, shifted-sum}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.50
Quantum Sub-Gaussian Mean Estimator

Authors: Yassine Hamoudi

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We present a new quantum algorithm for estimating the mean of a real-valued random variable obtained as the output of a quantum computation. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples needed to estimate the mean of a heavy-tailed distribution with a sub-Gaussian error rate. This result subsumes (up to logarithmic factors) earlier works on the mean estimation problem that were not optimal for heavy-tailed distributions [Brassard et al., 2002; Brassard et al., 2011], or that require prior information on the variance [Heinrich, 2002; Montanaro, 2015; Hamoudi and Magniez, 2019]. As an application, we obtain new quantum algorithms for the (ε,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.
Cite as

Yassine Hamoudi. Quantum Sub-Gaussian Mean Estimator. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 50:1-50:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hamoudi:LIPIcs.ESA.2021.50,
  author =	{Hamoudi, Yassine},
  title =	{{Quantum Sub-Gaussian Mean Estimator}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{50:1--50:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.50},
  URN =		{urn:nbn:de:0030-drops-146318},
  doi =		{10.4230/LIPIcs.ESA.2021.50},
  annote =	{Keywords: Quantum algorithm, statistical analysis, mean estimator, sub-Gaussian estimator, (\epsilon,\delta)-approximation, lower bound}
}
Document
DOI: 10.4230/LIPIcs.TQC.2021.1
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.69
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
DOI: 10.4230/LIPIcs.MFCS.2018.14
Simultaneous Multiparty Communication Protocols for Composed Functions

Authors: Yassine Hamoudi

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
The Number On the Forehead (NOF) model is a multiparty communication game between k players that collaboratively want to evaluate a given function F : X_1 x *s x X_k - > Y on some input (x_1,...,x_k) by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player i sees all of it except x_i (as if x_i is written on the forehead of player i). In the Simultaneous Message Passing (SMP) model, the players have the extra condition that they cannot speak to each other, but instead send information to a referee. The referee does not know the players' inputs, and cannot give any information back. At the end, the referee must be able to recover F(x_1,...,x_k) from what she obtained from the players. A central open question in the simultaneous NOF model, called the log n barrier, is to find a function which is hard to compute when the number of players is polylog(n) or more (where the x_i's have size poly(n)). This has an important application in circuit complexity, as it could help to separate ACC^0 from other complexity classes [Håstad and Goldmann, 1991; Babai et al., 2004]. One of the candidates for breaking the log n barrier belongs to the family of composed functions. The input to these functions in the k-party NOF model is represented by a k x (t * n) boolean matrix M, whose row i is the number x_i on the forehead of player i and t is a block-width parameter. A symmetric composed function acting on M is specified by two symmetric n- and kt-variate functions f and g (respectively), that output f o g(M) = f(g(B_1),...,g(B_n)) where B_j is the j-th block of width t of M. As the majority function Maj is conjectured to be outside of ACC^0, Babai et. al. [Babai et al., 1995; Babai et al., 2004] suggested to study the composed function Maj o Maj_t, with t large enough, for breaking the log n barrier (where Maj_t outputs 1 if at least kt/2 bits of the input block are set to 1). So far, it was only known that block-width t = 1 is not enough for Maj o Maj_t to break the log n barrier in the simultaneous NOF model [Babai et al., 2004] (Chattopadhyay and Saks [Chattopadhyay and Saks, 2014] found an efficient protocol for t <= polyloglog(n), but it requires randomness to be simultaneous). In this paper, we extend this result to any constant block-width t > 1 by giving a deterministic simultaneous protocol of cost 2^O(2^t) log^(2^(t+1))(n) for any symmetric composed function f o g (which includes Maj o Maj_t) when there are more than 2^Omega(2^t) log n players.
Cite as

Yassine Hamoudi. Simultaneous Multiparty Communication Protocols for Composed Functions. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamoudi:LIPIcs.MFCS.2018.14,
  author =	{Hamoudi, Yassine},
  title =	{{Simultaneous Multiparty Communication Protocols for Composed Functions}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.14},
  URN =		{urn:nbn:de:0030-drops-95969},
  doi =		{10.4230/LIPIcs.MFCS.2018.14},
  annote =	{Keywords: Communication complexity, Number On the Forehead model, Simultaneous Message Passing, Log n barrier, Symmetric Composed functions}
}
  • Refine by Type
  • 14 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 1 2023
  • 1 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 5 Hamoudi, Yassine
  • 2 Apers, Simon
  • 2 Gao, Minbo
  • 2 Ji, Zhengfeng
  • 2 Joux, Antoine
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Quantum computation theory
  • 4 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Quantum complexity theory
  • 2 Theory of computation → Quantum query complexity
  • 1 Computing methodologies → Machine learning
  • Show More...

  • Refine by Keyword
  • 2 Quantum Algorithms
  • 2 Quantum Computing
  • 2 Quantum algorithm
  • 2 Quantum computing
  • 2 lower bound
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact