4 Search Results for "Joux, Antoine"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.94
A Faster Algorithm for Pigeonhole Equal Sums

Authors: Ce Jin and Hongxun Wu

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

Abstract
An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search problem proposed by Papadimitriou (1994): given n positive integers w₁,… ,w_n of total sum ∑_{i = 1}ⁿ w_i < 2ⁿ-1, the task is to find two distinct subsets A, B ⊆ [n] such that ∑_{i ∈ A}w_i = ∑_{i ∈ B}w_i. Similar to the status of the Subset Sum problem, the best known algorithm for Pigeonhole Equal Sums runs in O^*(2^{n/2}) time, via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelhöfer, and Santha, 2022). Our main result is an improved algorithm for Pigeonhole Equal Sums in O^*(2^{0.4n}) time. We also give a polynomial-space algorithm in O^*(2^{0.75n}) time. Unlike many previous works in this area, our approach does not use the representation method, but rather exploits a simple structural characterization of input instances with few solutions.
Cite as

Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 94:1-94:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ICALP.2024.94,
  author =	{Jin, Ce and Wu, Hongxun},
  title =	{{A Faster Algorithm for Pigeonhole Equal Sums}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{94:1--94:11},
  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.94},
  URN =		{urn:nbn:de:0030-drops-202375},
  doi =		{10.4230/LIPIcs.ICALP.2024.94},
  annote =	{Keywords: Subset Sum, Pigeonhole, PPP}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.132
Integer Linear-Exponential Programming in NP by Quantifier Elimination

Authors: Dmitry Chistikov, Alessio Mansutti, and Mikhail R. Starchak

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

Abstract
This paper provides an NP procedure that decides whether a linear-exponential system of constraints has an integer solution. Linear-exponential systems extend standard integer linear programs with exponential terms 2^x and remainder terms (x mod 2^y). Our result implies that the existential theory of the structure (ℕ,0,1,+,2^(⋅),V_2(⋅,⋅), ≤) has an NP-complete satisfiability problem, thus improving upon a recent EXPSPACE upper bound. This theory extends the existential fragment of Presburger arithmetic with the exponentiation function x ↦ 2^x and the binary predicate V_2(x,y) that is true whenever y ≥ 1 is the largest power of 2 dividing x. Our procedure for solving linear-exponential systems uses the method of quantifier elimination. As a by-product, we modify the classical Gaussian variable elimination into a non-deterministic polynomial-time procedure for integer linear programming (or: existential Presburger arithmetic).
Cite as

Dmitry Chistikov, Alessio Mansutti, and Mikhail R. Starchak. Integer Linear-Exponential Programming in NP by Quantifier Elimination. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 132:1-132:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chistikov_et_al:LIPIcs.ICALP.2024.132,
  author =	{Chistikov, Dmitry and Mansutti, Alessio and Starchak, Mikhail R.},
  title =	{{Integer Linear-Exponential Programming in NP by Quantifier Elimination}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{132:1--132: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.132},
  URN =		{urn:nbn:de:0030-drops-202758},
  doi =		{10.4230/LIPIcs.ICALP.2024.132},
  annote =	{Keywords: decision procedures, integer programming, quantifier elimination}
}
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
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.3
Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk)

Authors: Antoine Joux

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

Abstract
The discrete logarithm problem is one of the few hard problems on which public-key cryptography can be based. It was introduced in the field by the famous Diffie-Hellman key exchange protocol. Initially, the cryptographic use of the problem was considered in prime fields, but was readily generalized to arbitrary finite fields and, later, to elliptic or higher genus curves. In this talk, we survey the key technical ideas that can be used to compute discrete logarithms, especially in the case of small characteristic finite fields. These ideas stem from about 40 years of research on the topic. They appeared along the long road that leads from the initial belief that this problem was hard enough for cryptographic purpose to the current state of the art where it can no longer be considered for cryptographic use. Indeed, after the recent developments started in 2012, we now have some very efficient practical algorithms to solve this problem. Unfortunately, these algorithms remain heuristic and one important direction for future research is to lift the remaining heuristic assumptions.
Cite as

Antoine Joux. Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{joux:LIPIcs.STACS.2017.3,
  author =	{Joux, Antoine},
  title =	{{Discrete Logarithms in Small Characteristic Finite Fields: a Survey of Recent Advances}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{3:1--3:1},
  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.3},
  URN =		{urn:nbn:de:0030-drops-70313},
  doi =		{10.4230/LIPIcs.STACS.2017.3},
  annote =	{Keywords: Cryptography, Discrete logarithms, Finite fields}
}
  • Refine by Author
  • 2 Joux, Antoine
  • 1 Allcock, Jonathan
  • 1 Chistikov, Dmitry
  • 1 Hamoudi, Yassine
  • 1 Jin, Ce
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Symbolic and algebraic algorithms
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Logic
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 Cryptography
  • 1 Discrete logarithms
  • 1 Finite fields
  • 1 PPP
  • 1 Pigeonhole
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2024
  • 1 2017
  • 1 2022

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact