The robustness of LWPP and WPP, with an application to graph reconstruction

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/

zbMATH Keywords

reconstruction conjecturestructural complexity theorylegitimate deck problemPP-lownessrobustness of counting classes

Mathematics Subject Classification ID

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