On Pseudodeterministic Approximation Algorithms.

DOI10.4230/LIPIcs.MFCS.2018.61OpenAlexW2888826740MaRDI QIDQ5005164

N. V. Vinodchandran, A. Pavan, Peter B. Dixon

Publication date: 4 August 2021

Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2018.html#DixonPV18

zbMATH Keywords

approximation algorithmscircuit lower boundspseudodeterminism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Front Matter, Table of Contents, Preface, Conference Organization

Cites Work

• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Uniform generation of NP-witnesses using an NP-oracle
• Oracles and queries that are sufficient for exact learning
• A note on the circuit complexity of PP
• On the possibilities and limitations of pseudodeterministic algorithms
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Circuit-size lower bounds and non-reducibility to sparse sets
• Circuit Lower Bounds for Merlin–Arthur Classes
• On Approximation Algorithms for # P
• New Collapse Consequences of NP Having Small Circuits
• Communication complexity of key agreement on small ranges
• Pseudodeterministic constructions in subexponential time
• Bipartite Perfect Matching in Pseudo-Deterministic NC
• Reproducibility and Pseudo-Determinism in Log-Space
• Computational Complexity

This page was built for publication: On Pseudodeterministic Approximation Algorithms.