2026-07-21T19:38:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11686 2024-03-06T10:48:27Z ddc:004 open_access

Hardness Amplification of Optimization Problems Goldenberg, Elazar Karthik C. S. hardness amplification average case complexity direct product optimization problems fine-grained complexity TFNP 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elazar Goldenberg and Karthik C. S. 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.1 urn:nbn:de:0030-drops-116863 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.1 eng https://creativecommons.org/licenses/by/3.0/legalcode