Goldenberg, Elazar ;
Karthik C. S.,
Hardness Amplification of Optimization Problems
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 NPhard problems like MaxClique, Knapsack, and MaxSAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium.
BibTeX  Entry
@InProceedings{goldenberg_et_al:LIPIcs:2020:11686,
author = {Elazar Goldenberg and Karthik C. S.},
title = {{Hardness Amplification of Optimization Problems}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {1:11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11686},
URN = {urn:nbn:de:0030drops116863},
doi = {10.4230/LIPIcs.ITCS.2020.1},
annote = {Keywords: hardness amplification, average case complexity, direct product, optimization problems, finegrained complexity, TFNP}
}
06.01.2020
Keywords: 

hardness amplification, average case complexity, direct product, optimization problems, finegrained complexity, TFNP 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 