On Pseudodeterministic Approximation Algorithms.
From MaRDI portal
Publication:5005164
DOI10.4230/LIPIcs.MFCS.2018.61MaRDI 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
68Qxx: Theory of computing
Related Items
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