scientific article; zbMATH DE number 1072538
From MaRDI portal
Publication:4359465
Recommendations
Cited in
(33)- On the IO-complexity and approximation languages
- Algorithms for the fixed point property
- No NP problems averaging over ranking of distributions are harder
- Generic-case complexity, decision problems in group theory, and random walks.
- Complete distributional problems, hard languages, and resource-bounded measure
- Complete on average Boolean satisfiability
- On the NP-isomorphism problem with respect to random instances
- Computational depth: Concept and applications
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
- Notes on Levin's theory of average-case complexity
- Average case complexity, revisited
- scientific article; zbMATH DE number 5081744 (Why is no real title available?)
- An efficient local search method for random 3-satisfiability
- Average-Case Complexity
- On the Average Case Complexity of Some P-complete Problems
- Matrix Transformation Is Complete for the Average Case
- scientific article; zbMATH DE number 1008511 (Why is no real title available?)
- scientific article; zbMATH DE number 1008518 (Why is no real title available?)
- scientific article; zbMATH DE number 1180007 (Why is no real title available?)
- scientific article; zbMATH DE number 1555929 (Why is no real title available?)
- Structure vs combinatorics in computational complexity
- The complexity of generating test instances
- scientific article; zbMATH DE number 7515768 (Why is no real title available?)
- Average-Case Completeness in Tag Systems
- Sets computable in polynomial time on average
- Reductions and convergence rates of average time
- A hard problem that is almost always easy
- Average-case complexity and decision problems in group theory.
- Generating Boolean lattices with few elements and exchanging session keys
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Generalized juntas and NP-hard sets
- Relations between average-case and worst-case complexity
- Frequency of correctness versus average polynomial time
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359465)
