On Pseudodeterministic Approximation Algorithms. (Q5005164): Difference between revisions

@@ label / en / label / en @@
+On Pseudodeterministic Approximation Algorithms.
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform generation of NP-witnesses using an NP-oracle
+Normal rank
@@ Property / cites work @@
+Oracles and queries that are sufficient for exact learning
+Normal rank
@@ Property / cites work @@
+Communication complexity of key agreement on small ranges
+Normal rank
@@ Property / cites work @@
+On the possibilities and limitations of pseudodeterministic algorithms
+Normal rank
@@ Property / cites work @@
+Bipartite Perfect Matching in Pseudo-Deterministic NC
+Normal rank
@@ Property / cites work @@
+Reproducibility and Pseudo-Determinism in Log-Space
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+New Collapse Consequences of NP Having Small Circuits
+Normal rank
@@ Property / cites work @@
+Pseudodeterministic constructions in subexponential time
+Normal rank
@@ Property / cites work @@
+\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
+Normal rank
@@ Property / cites work @@
+Circuit Lower Bounds for Merlin–Arthur Classes
@@ Property / cites work: Circuit Lower Bounds for Merlin–Arthur Classes / rank @@
+Normal rank
@@ Property / cites work @@
+On Approximation Algorithms for # P
@@ Property / cites work: On Approximation Algorithms for # P / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the circuit complexity of PP
@@ Property / cites work: A note on the circuit complexity of PP / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://dblp.uni-trier.de/db/conf/mfcs/mfcs2018.html#DixonPV18
+Normal rank
@@ Property / OpenAlex ID @@
+W2888826740
@@ Property / OpenAlex ID: W2888826740 / rank @@
+Normal rank
@@ Property / title @@
+On Pseudodeterministic Approximation Algorithms. (English)
+Normal rank