Document Open Access Logo

A Faster Algorithm for Pigeonhole Equal Sums

Authors Ce Jin , Hongxun Wu

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2024.94.pdf
  • Filesize: 0.77 MB
  • 11 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Subset Sum
  • Pigeonhole
  • PPP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2024.94

Author Details

Ce Jin
  • MIT, Cambridge, MA, USA
Hongxun Wu
  • University of California Berkeley, CA, USA

Funding

  • Jin, Ce: Supported by NSF grants CCF-2129139 and CCF-2127597. Work done while visiting the Simons Institute for the Theory of Computing.
  • Wu, Hongxun: Supported by Avishay Tal’s Sloan Research Fellowship, NSF CAREER Award CCF-2145474, and Jelani Nelson’s ONR grant N00014-18-1-2562.

Acknowledgements

We thank Ryan Williams for useful discussions.

References

  1. 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, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 6:1-6:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ESA.2022.6.
  2. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset sum in the absence of concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 48-61. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.48.
  3. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense subset sum may be the hardest. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), volume 47 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.13.
  4. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Sharper upper bounds for unbalanced uniquely decodable code pairs. IEEE Trans. Inf. Theory, 64(2):1368-1373, 2018. URL: https://doi.org/10.1109/TIT.2017.2688378.
  5. Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, and Aviad Rubinstein. Reductions in PPP. Inf. Process. Lett., 145:48-52, 2019. URL: https://doi.org/10.1016/j.ipl.2018.12.009.
  6. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas. Faster space-efficient algorithms for subset sum, k-sum, and related problems. SIAM J. Comput., 47(5):1755-1777, 2018. URL: https://doi.org/10.1137/17M1158203.
  7. Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element distinctness, frequency moments, and sliding windows. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 290-299, 2013. URL: https://doi.org/10.1109/FOCS.2013.39.
  8. Anja Becker, Jean-Sébastien Coron, and Antoine Joux. Improved generic algorithms for hard knapsacks. In Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pages 364-385. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20465-4_21.
  9. Xavier Bonnetain, Rémi Bricout, André Schrottenloher, and Yixin Shen. Improved classical and quantum algorithms for subset-sum. In Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II, volume 12492 of Lecture Notes in Computer Science, pages 633-666. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64834-3_22.
  10. Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete distributions. Algorithmica, 79(2):484-508, 2017. URL: https://doi.org/10.1007/S00453-016-0205-0.
  11. Lijie Chen, Ce Jin, R. Ryan Williams, and Hongxun Wu. Truly low-space element distinctness and subset sum via pseudorandom hash functions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1661-1678, 2022. URL: https://doi.org/10.1137/1.9781611977073.67.
  12. Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Average-case subset balancing problems. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 743-778. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.33.
  13. Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio. Subset sum in time 2^n/2 / poly(n). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA, volume 275 of LIPIcs, pages 39:1-39:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.39.
  14. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. Journal of the ACM, 21(2):277-292, 1974. URL: https://doi.org/10.1145/321812.321823.
  15. Nick Howgrave-Graham and Antoine Joux. New generic algorithms for hard knapsacks. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 235-256. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_12.
  16. Xin Lyu and Weihao Zhu. Time-space tradeoffs for element distinctness and set intersection via pseudorandomness. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5243-5281. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch190.
  17. Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, and Karol Węgrzycki. Equal-subset-sum faster than the meet-in-the-middle. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 73:1-73:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.73.
  18. Jesper Nederlof. A short note on merlin-arthur protocols for subset sum. Inf. Process. Lett., 118:15-16, 2017. URL: https://doi.org/10.1016/j.ipl.2016.09.002.
  19. Jesper Nederlof and Karol Węgrzycki. Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1670-1683. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451024.
  20. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80063-7.
  21. Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. PPP-completeness with connections to cryptography. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 148-158. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00023.
  22. Henk C. A. van Tilborg. An upper bound for codes in a two-access binary erasure channel (corresp.). IEEE Trans. Inf. Theory, 24(1):112-116, 1978. URL: https://doi.org/10.1109/TIT.1978.1055814.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact