Dixon, Peter ;
Pavan, A. ;
Vinodchandran, N. V.
On Pseudodeterministic Approximation Algorithms
Abstract
We investigate the notion of pseudodeterminstic approximation algorithms. A randomized approximation algorithm A for a function f is pseudodeterministic if for every input x there is a unique value v so that A(x) outputs v with high probability, and v is a good approximation of f(x). We show that designing a pseudodeterministic version of Stockmeyer's well known approximation algorithm for the NPmembership counting problem will yield a new circuit lower bound: if such an approximation algorithm exists, then for every k, there is a language in the complexity class ZPP^{NP}_{tt} that does not have n^ksize circuits. While we do not know how to design such an algorithm for the NPmembership counting problem, we show a general result that any randomized approximation algorithm for a counting problem can be transformed to an approximation algorithm that has a constant number of influential random bits. That is, for most settings of these influential bits, the approximation algorithm will be pseudodeterministic.
BibTeX  Entry
@InProceedings{dixon_et_al:LIPIcs:2018:9643,
author = {Peter Dixon and A. Pavan and N. V. Vinodchandran},
title = {{On Pseudodeterministic Approximation Algorithms}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {61:161:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9643},
URN = {urn:nbn:de:0030drops96431},
doi = {10.4230/LIPIcs.MFCS.2018.61},
annote = {Keywords: Approximation Algorithms, Circuit lower bounds, Pseudodeterminism}
}
27.08.2018
Keywords: 

Approximation Algorithms, Circuit lower bounds, Pseudodeterminism 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 