2026-07-22T17:54:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9643 2024-03-06T10:44:36Z ddc:004 open_access

On Pseudodeterministic Approximation Algorithms Dixon, Peter Pavan, A. Vinodchandran, N. V. Approximation Algorithms Circuit lower bounds Pseudodeterminism 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 NP-membership 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^k-size circuits. While we do not know how to design such an algorithm for the NP-membership 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Dixon and A. Pavan and N. V. Vinodchandran 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.61 urn:nbn:de:0030-drops-96431 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.61 eng https://creativecommons.org/licenses/by/3.0/legalcode