Document Open Access Logo

Hardness Amplification of Optimization Problems

Authors Elazar Goldenberg, Karthik C. S.

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.1.pdf
  • Filesize: 472 kB
  • 13 pages

Document Identifiers

Author Details

Elazar Goldenberg
  • The Academic College of Tel Aviv Yaffo, Israel
Karthik C. S.
  • Tel Aviv University, Israel

Funding

  • Karthik C. S.: Most of this work was done while the author was a student at Weizmann Institute of Science and was supported by Irit Dinur’s ERC-CoG grant 772839. This work also received support from the Israel Science Foundation (grant number 552/16) and the Len Blavatnik and the Blavatnik Family foundation.

Acknowledgements

We would like to thank Amir Abboud, Irit Dinur, and Eylon Yogev for discussions and comments.

Cite AsGet BibTex

Elazar Goldenberg and Karthik C. S.. Hardness Amplification of Optimization Problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.1

Abstract

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem Π is direct product feasible if it is possible to efficiently aggregate any k instances of Π and form one large instance of Π such that given an optimal feasible solution to the larger instance, we can efficiently find optimal feasible solutions to all the k smaller instances. Given a direct product feasible optimization problem Π, our hardness amplification theorem may be informally stated as follows: If there is a distribution D over instances of Π of size n such that every randomized algorithm running in time t(n) fails to solve Π on 1/α(n) fraction of inputs sampled from D, then, assuming some relationships on α(n) and t(n), there is a distribution D' over instances of Π of size O(n⋅α(n)) such that every randomized algorithm running in time t(n)/poly(α(n)) fails to solve Π on 99/100 fraction of inputs sampled from D'. As a consequence of the above theorem, we show hardness amplification of problems in various classes such as NP-hard problems like Max-Clique, Knapsack, and Max-SAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • hardness amplification
  • average case complexity
  • direct product
  • optimization problems
  • fine-grained complexity
  • TFNP

Metrics

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

Related Versions

References

  1. Amir Abboud. Personal communication, 2019. Google Scholar
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 375-388, 2016. URL: https://doi.org/10.1145/2897518.2897653.
  3. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. URL: https://doi.org/10.1007/BF01275486.
  4. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case Fine-grained Hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 483-496, New York, NY, USA, 2017. ACM. URL: https://doi.org/10.1145/3055399.3055466.
  5. Andrej Bogdanov and Alon Rosen. Input Locality and Hardness Amplification. J. Cryptology, 26(1):144-171, 2013. URL: https://doi.org/10.1007/s00145-011-9117-y.
  6. Andrej Bogdanov and Luca Trevisan. Average-Case Complexity. Foundations and Trends in Theoretical Computer Science, 2(1), 2006. URL: https://doi.org/10.1561/0400000004.
  7. Andrej Bogdanov and Luca Trevisan. On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  8. Joshua Buresh-Oppenheim, Valentine Kabanets, and Rahul Santhanam. Uniform Hardness Amplification in NP via Monotone Codes. Electronic Colloquium on Computational Complexity (ECCC), 13(154), 2006. URL: http://eccc.hpi-web.de/eccc-reports/2006/TR06-154/index.html.
  9. Jin-yi Cai, Aduri Pavan, and D. Sivakumar. On the Hardness of Permanent. In STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, pages 90-99, 1999. URL: https://doi.org/10.1007/3-540-49116-3_8.
  10. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A Duality between Clause Width and Clause Density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 252-260, 2006. URL: https://doi.org/10.1109/CCC.2006.6.
  11. Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch87.
  12. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ECCC, 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
  13. Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 534-543, 2002. URL: https://doi.org/10.1145/509907.509985.
  14. Uriel Feige and Joe Kilian. Two-Prover Protocols - Low Error at Affordable Rates. SIAM J. Comput., 30(1):324-346, 2000. URL: https://doi.org/10.1137/S0097539797325375.
  15. Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman. Security Preserving Amplification of Hardness. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 318-326, 1990. URL: https://doi.org/10.1109/FSCS.1990.89550.
  16. Oded Goldreich and Guy N. Rothblum. Worst-case to Average-case reductions for subclasses of P. Electronic Colloquium on Computational Complexity (ECCC), 24:130, 2017. URL: https://eccc.weizmann.ac.il/report/2017/130.
  17. Oded Goldreich and Guy N. Rothblum. Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 77-88, 2018. URL: https://doi.org/10.1109/FOCS.2018.00017.
  18. Parikshit Gopalan and Venkatesan Guruswami. Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci., 77(1):107-121, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.008.
  19. Alexander Healy, Salil P. Vadhan, and Emanuele Viola. Using Nondeterminism to Amplify Hardness. SIAM J. Comput., 35(4):903-931, 2006. URL: https://doi.org/10.1137/S0097539705447281.
  20. Russell Impagliazzo. Hard-Core Distributions for Somewhat Hard Problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 538-545, 1995. URL: https://doi.org/10.1109/SFCS.1995.492584.
  21. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New Direct-Product Testers and 2-Query PCPs. SIAM J. Comput., 41(6):1722-1768, 2012. URL: https://doi.org/10.1137/09077299X.
  22. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Preliminary version in CCC'99. URL: https://doi.org/10.1006/jcss.2000.1727.
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Preliminary version in FOCS'98. URL: https://doi.org/10.1006/jcss.2001.1774.
  24. Russell Impagliazzo and Avi Wigderson. P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220-229, 1997. URL: https://doi.org/10.1145/258533.258590.
  25. Marvin Künnemann. On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 56:1-56:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.56.
  26. Richard J. Lipton. New Directions In Testing. In Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, pages 191-202, 1989. URL: https://doi.org/10.1090/dimacs/002/13.
  27. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR, abs/1607.02986, 2016. URL: http://arxiv.org/abs/1607.02986.
  28. Ryan O'Donnell. Hardness amplification within _NP. J. Comput. Syst. Sci., 69(1):68-94, 2004. URL: https://doi.org/10.1016/j.jcss.2004.01.001.
  29. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. URL: https://doi.org/10.1006/jcss.2000.1730.
  30. Luca Trevisan. List-Decoding Using The XOR Lemma. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 126-135, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238187.
  31. Luca Trevisan. On uniform amplification of hardness in NP. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 31-38, 2005. URL: https://doi.org/10.1145/1060590.1060595.
  32. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity, 16(4):331-364, 2007. URL: https://doi.org/10.1007/s00037-007-0233-x.
  33. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM, 65(5):27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  34. Andrew Chi-Chih Yao. Theory and Applications of Trapdoor Functions (Extended Abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
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 Imprint Privacy Contact