Elrazik, Reyad Abed ;
Robere, Robert ;
Schuster, Assaf ;
Yehuda, Gal
Pseudorandom SelfReductions for NPComplete Problems
Abstract
A language L is randomselfreducible if deciding membership in L can be reduced (in polynomial time) to deciding membership in L for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random selfreductions. Feigenbaum and Fortnow showed that NPcomplete languages are not nonadaptively randomselfreducible unless the polynomialtime hierarchy collapses, giving suggestive evidence that NP may not admit random selfreductions. Hirahara and Santhanam introduced a weakening of random selfreductions that they called pseudorandom selfreductions, in which a language L is reduced to a distribution that is computationally indistinguishable from the uniform distribution. They then showed that the Minimum Circuit Size Problem (MCSP) admits a nonadaptive pseudorandom selfreduction, and suggested that this gave further evidence that distinguished MCSP from standard NPComplete problems.
We show that, in fact, the Clique problem admits a nonadaptive pseudorandom selfreduction, assuming the planted clique conjecture. More generally we show the following. Call a property of graphs π hereditary if G ∈ π implies H ∈ π for every induced subgraph of G. We show that for any infinite hereditary property π, the problem of finding a maximum induced subgraph H ∈ π of a given graph G admits a nonadaptive pseudorandom selfreduction.
BibTeX  Entry
@InProceedings{elrazik_et_al:LIPIcs.ITCS.2022.65,
author = {Elrazik, Reyad Abed and Robere, Robert and Schuster, Assaf and Yehuda, Gal},
title = {{Pseudorandom SelfReductions for NPComplete Problems}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {65:165:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15661},
URN = {urn:nbn:de:0030drops156615},
doi = {10.4230/LIPIcs.ITCS.2022.65},
annote = {Keywords: computational complexity, pseudorandomness, worstcase to averagecase, self reductions, planted clique, hereditary graph family}
}
25.01.2022
Keywords: 

computational complexity, pseudorandomness, worstcase to averagecase, self reductions, planted clique, hereditary graph family 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 