The robustness of LWPP and WPP, with an application to graph reconstruction
From MaRDI portal
Publication:2027204
DOI10.1007/s00037-020-00197-5zbMath1503.68074OpenAlexW3094798665MaRDI QIDQ2027204
Holger Spakowski, Edith Hemaspaandra, Osamu Watanabe, Hemaspaandra, Lane A.
Publication date: 25 May 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9633/
reconstruction conjecturestructural complexity theorylegitimate deck problemPP-lownessrobustness of counting classes
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Partial orders on words, minimal elements of regular languages, and state complexity
- Complexity results in graph reconstruction
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- On some natural complete operators
- The complexity of combinatorial problems with succinct input representation
- On hardness of one-way functions
- A uniform approach to define complexity classes
- Graph isomorphism is low for PP
- Relative complexity of checking and evaluating
- Complete sets and the polynomial-time hierarchy
- Gap-definable counting classes
- Upward separation for FewP and related classes
- The set of minimal words of a context-free language is context-free
- An oracle builder's toolkit
- PP-lowness and a simple definition of AWPP
- Complexity limitations on quantum computation
- A complexity theory for feasible closure properties
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- LWPP and WPP are not uniformly gap-definable
- Approximate formulas for some functions of prime numbers
- Parity, circuits, and the polynomial-time hierarchy
- Complexity Measures for Public-Key Cryptosystems
- The Boolean Hierarchy II: Applications
- THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Graph reconstruction—a survey
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- On the complexity of graph reconstruction
- Threshold Computation and Cryptographic Security
- Oracle Quantum Computing
- Counting Complexity of Solvable Black-Box Group Problems
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Structural complexity theory: Recent surprises
- Graph isomorphism in quasipolynomial time [extended abstract]
- The complexity theory companion
This page was built for publication: The robustness of LWPP and WPP, with an application to graph reconstruction
