Document Open Access Logo

On the Fine-Grained Complexity of Parity Problems

Authors Amir Abboud, Shon Feller, Oren Weimann

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.5.pdf
  • Filesize: 0.79 MB
  • 19 pages

Document Identifiers

Author Details

Amir Abboud
  • IBM Almaden Research Center, San Jose, CA, USA
Shon Feller
  • University of Haifa, Israel
Oren Weimann
  • University of Haifa, Israel

Funding

  • Feller, Shon: Supported in part by Israel Science Foundation grant 592/17.
  • Weimann, Oren: Supported in part by Israel Science Foundation grant 592/17.

Cite As Get BibTex

Amir Abboud, Shon Feller, and Oren Weimann. On the Fine-Grained Complexity of Parity Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.5

Abstract

We consider the parity variants of basic problems studied in fine-grained complexity. We show that finding the exact solution is just as hard as finding its parity (i.e. if the solution is even or odd) for a large number of classical problems, including All-Pairs Shortest Paths (APSP), Diameter, Radius, Median, Second Shortest Path, Maximum Consecutive Subsums, Min-Plus Convolution, and 0/1-Knapsack.
A direct reduction from a problem to its parity version is often difficult to design. Instead, we revisit the existing hardness reductions and tailor them in a problem-specific way to the parity version. Nearly all reductions from APSP in the literature proceed via the (subcubic-equivalent but simpler) Negative Weight Triangle (NWT) problem. Our new modified reductions also start from NWT or a non-standard parity variant of it. We are not able to establish a subcubic-equivalence with the more natural parity counting variant of NWT, where we ask if the number of negative triangles is even or odd. Perhaps surprisingly, we justify this by designing a reduction from the seemingly-harder Zero Weight Triangle problem, showing that parity is (conditionally) strictly harder than decision for NWT.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • All-pairs shortest paths
  • Fine-grained complexity
  • Diameter
  • Distance product
  • Min-plus convolution
  • Parity problems

Metrics

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

Related Versions

References

  1. Amir Abboud. Fine-grained reductions and quantum speedups for dynamic programming. In 46th ICALP, pages 8:1-8:13, 2019. Google Scholar
  2. Amir Abboud, Vincent Cohen-Addad, and Philip N Klein. New hardness results for planar graph problems in p and an algorithm for sparsest cut. In 52nd STOC, 2020. To appear. Google Scholar
  3. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In 26th SODA, pages 1681-1697, 2015. Google Scholar
  4. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th FOCS, pages 434-443. IEEE, 2014. Google Scholar
  5. Vikraman Arvind and Piyush P Kurur. Graph isomorphism is in spp. In 43rd FOCS, pages 743-750, 2002. Google Scholar
  6. Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. Tight hardness results for maximum weight rectangles. In 43rd ICALP, pages 81:1-81:13, 2016. Google Scholar
  7. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In 28th SODA, pages 2215-2229, 2017. Google Scholar
  8. Richard Beigel, Harry Buhrman, and Lance Fortnow. Np might not be as easy as detecting unique solutions. In 30th STOC, pages 203-208, 1998. Google Scholar
  9. Enric Boix-Adserà, Matthew Brennan, and Guy Bresler. The average-case complexity of counting cliques in erdős-rényi hypergraphs. In 60th FOCS, pages 1256-1280, 2019. Google Scholar
  10. Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. Subcubic equivalences between graph centrality measures and complementary problems. CoRR, abs/1905.08127, 2019. URL: http://arxiv.org/abs/1905.08127.
  11. Charles Bouillaguet and Claire Delaplace. Faster algorithms for the sparse random 3XOR problem. Preprint, 2019. URL: https://hal.archives-ouvertes.fr/hal-02306917.
  12. Charles Bouillaguet, Claire Delaplace, and Pierre-Alain Fouque. Revisiting and improving algorithms for the 3xor problem. IACR Transactions on Symmetric Cryptology, pages 254-276, 2018. Google Scholar
  13. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. Google Scholar
  14. Karl Bringmann. Approximating subset sum is equivalent to min-plus-convolution. CoRR, abs/1912.12529, 2019. URL: http://arxiv.org/abs/1912.12529.
  15. Radu Curticapean. Counting problems in parameterized complexity. In 13th IPEC 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  16. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, 2016. Google Scholar
  17. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min,+)-convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. Google Scholar
  18. Holger Dell. Fine-grained complexity classification of counting problems. https://simons.berkeley.edu/talks/holger-dell-2016-03-28, 2016. URL: https://simons.berkeley.edu/talks/holger-dell-2016-03-28.
  19. Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 281-288, 2018. Google Scholar
  20. Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. Fine-grained I/O complexity via reductions: New lower bounds, faster algorithms, and a time hierarchy. In 9th ITCS, pages 34:1-34:23, 2018. Google Scholar
  21. Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A subquadratic algorithm for 3XOR. CoRR, abs/1804.11086, 2018. URL: http://arxiv.org/abs/1804.11086.
  22. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892-922, 2004. Google Scholar
  23. Lance Fortnow. Counting complexity. Complexity theory retrospective II, pages 81-107, 1997. Google Scholar
  24. Anka Gajentaan and Mark H. Overmars. On a class of o(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  25. Oded Goldreich and Guy N. Rothblum. Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems. In 59th FOCS, pages 77-88, 2018. Google Scholar
  26. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM, 65(4):22:1-22:25, 2018. Google Scholar
  27. Zahra Jafargholi and Emanuele Viola. 3xor,3sum, triangles. Algorithmica, 74(1):326-343, 2016. Google Scholar
  28. James King. A survey of 3SUM-hard problems. Preprint, 2019. URL: http://www.ccs.neu.edu/home/viola/classes/papers/King04Survey3sum.pdf.
  29. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In 27th SODA, pages 1272-1287. SIAM, 2016. Google Scholar
  30. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In 44th ICALP, pages 21:1-21:15, 2017. Google Scholar
  31. Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. On lower bounds for the maximum consecutive subsums problem and the (min,+)-convolution. In 11th ISIT, pages 1807-1811, 2014. Google Scholar
  32. Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams. Public-key cryptography in the fine-grained setting. In 39th CRYPTO, pages 605-635, 2019. Google Scholar
  33. Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic triangles, intermediate matrix products, and convolutions. In 11th ITCS, pages 53:1-53:18, 2020. Google Scholar
  34. Christos H Papadimitriou and Stathis K Zachos. Two remarks on the power of counting. In Theoretical Computer Science, volume 145, pages 269-276, 1983. Google Scholar
  35. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In 42nd STOC, pages 603-610, 2010. Google Scholar
  36. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In 45th STOC, pages 515-524, 2013. Google Scholar
  37. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In 12th ESA, pages 580-591, 2004. Google Scholar
  38. Barna Saha. Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems. In 6th FOCS, pages 118-135, 2015. Google Scholar
  39. Tadao Takaoka. Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electr. Notes Theor. Comput. Sci., 61:191-200, 2002. Google Scholar
  40. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. Google Scholar
  41. Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189-201, 1979. Google Scholar
  42. Leslie G Valiant. Accidental algorthims. In 47th FOCS, pages 509-517, 2006. Google Scholar
  43. Leslie G Valiant. Some observations on holographic algorithms. computational complexity, 27(3):351-374, 2018. Google Scholar
  44. Leslie G Valiant and Vijay V Vazirani. Np is as easy as detecting unique solutions. In 17th STOC, pages 458-463, 1985. Google Scholar
  45. Maria Isabel González Vasco and Mats Näslund. A survey of hard core functions. Cryptography and Computational Number Theory, 20:227-255, 2001. Google Scholar
  46. Ryan Williams. Counting solutions to polynomial systems via reductions. In 1st SOSA, pages 6:1-6:15, 2018. Google Scholar
  47. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965-1985, 2018. Google Scholar
  48. Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In 25th SODA, pages 1867-1877, 2014. Google Scholar
  49. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In ICM, 2018. Invited talk. Google Scholar
  50. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. In 41st STOC, pages 455-464, 2009. Google Scholar
  51. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact