On Approximation Algorithms for # P
From MaRDI portal
On Approximation Algorithms for P
Recommendations
Cited in
(59)- Relativized alternation and space-bounded computation
- Graph isomorphism is in the low hierarchy
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Probabilistic complexity classes and lowness
- On relationships between approximate and probabilistic complexity classes
- Locating P/poly optimally in the extended low hierarchy
- On randomized versus deterministic computation
- A q-analog of approximation inclusion-exclusion
- Optimal proof systems imply complete sets for promise classes
- Semantics and complexity of abduction from default theories
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Approximate counting in SMT and value estimation for probabilistic programs
- Enumerative counting is hard
- Parameterized random complexity
- Model counting with error-correcting codes
- Amplification with one \textsf{NP} oracle query
- Completeness, approximability and exponential time results for counting problems with easy decision version
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- On the de-randomization of space-bounded approximate counting problems
- Lower bounds for non-black-box zero knowledge
- Dimension, entropy rates, and compression
- The complexity of estimating min-entropy
- On the hardness of approximate reasoning
- The Approximability of the Binary Paintshop Problem
- scientific article; zbMATH DE number 6381654 (Why is no real title available?)
- The relative exponential time complexity of approximate counting satisfying assignments
- The relative exponential time complexity of approximate counting satisfying assignments
- The computational complexity of linear optics
- On Parameterized Approximability
- scientific article; zbMATH DE number 4066859 (Why is no real title available?)
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- Quantum-walk speedup of backtracking algorithms
- A chasm between identity and equivalence testing with conditional queries
- On randomized versus deterministic computation
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- Randomness buys depth for approximate counting
- Edge estimation with independent set oracles
- On Pseudodeterministic Approximation Algorithms.
- Quantum lower bounds for approximate counting via Laurent polynomials
- On the parameterized complexity of approximate counting
- ANALYSIS OF QUANTUM FUNCTIONS
- One-Way Functions and (Im)perfect Obfuscation
- Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
- On the computational power of DNA
- Counting vertices of integral polytopes defined by facets
- Almost optimal query algorithm for hitting set using a subset query
- Approximating the chromatic polynomial of a graph
- Approximation algorithms for \(k\)-hurdle problems
- On computing small variable disjunction branch-and-bound trees
- Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
- A qubit, a coin, and an advice string walk into a relational problem
- Non-adaptive edge counting and sampling via bipartite independent set queries
- A tight analysis and near-optimal instances of the algorithm of Anderson and Woll
- On the complexity of counting in the polynomial hierarchy
- A note on enumerative counting
- On triangle estimation using tripartite independent set queries
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- On the complexity of ranking
- The parameterized complexity of probability amplification
This page was built for publication: On Approximation Algorithms for # P
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718150)
