The robustness of LWPP and WPP, with an application to graph reconstruction
type: Item
instance of: scholarly article
title: The robustness of LWPP and WPP, with an application to graph reconstruction
zbMATH Open document ID: 1503.68074
author: Edith Hemaspaandra
author: Holger Spakowski
author: Osamu Watanabe
author: Lane A. Hemaspaandra
published in: Computational Complexity
publication date: 2021-05-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9633/
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7350835
zbMATH Keywords: structural complexity theory
zbMATH Keywords: robustness of counting classes
zbMATH Keywords: legitimate deck problem
zbMATH Keywords: PP-lowness
zbMATH Keywords: reconstruction conjecture
MaRDI profile type: Publication
OpenAlex ID: W3094798665
cites work: Graph isomorphism in quasipolynomial time [extended abstract]
cites work: The set of minimal words of a context-free language is context-free
cites work: Oracle Quantum Computing
cites work: Partial orders on words, minimal elements of regular languages, and state complexity
cites work: Q3975132
cites work: Graph reconstruction—a survey
cites work: A uniform approach to define complexity classes
cites work: The Boolean Hierarchy II: Applications
cites work: PP-lowness and a simple definition of AWPP
cites work: Gap-definable counting classes
cites work: An oracle builder's toolkit
cites work: Complexity limitations on quantum computation
cites work: Q4289278
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Threshold Computation and Cryptographic Security
cites work: Q4005200
cites work: Structural complexity theory: Recent surprises
cites work: Complexity results in graph reconstruction
cites work: Q5005153
cites work: The complexity theory companion
cites work: On some natural complete operators
cites work: Relativized Polynomial Time Hierarchies Having Exactly K Levels
cites work: Graph isomorphism is low for PP
cites work: Q4266533
cites work: On the complexity of graph reconstruction
cites work: Q4414312
cites work: Strong nondeterministic polynomial-time reducibilities
cites work: THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
cites work: Q3824449
cites work: Q3870936
cites work: A complexity theory for feasible closure properties
cites work: Upward separation for FewP and related classes
cites work: Approximate formulas for some functions of prime numbers
cites work: Immunity and Simplicity for Exact Counting and Other Counting Classes
cites work: A low and a high hierarchy within NP
cites work: Quantum and classical complexity classes: Separations, collapses, and closure properties
cites work: LWPP and WPP are not uniformly gap-definable
cites work: Q4131648
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: Q3259049
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: Counting Complexity of Solvable Black-Box Group Problems
cites work: The complexity of combinatorial problems with succinct input representation
cites work: On hardness of one-way functions
cites work: Complete sets and the polynomial-time hierarchy
DOI: 10.1007/S00037-020-00197-5
Recommended article: Q5005153
Recommended article: Robustness of random graphs based on graph spectra
Recommended article: Q5741889
Recommended article: The robust component structure of dense regular graphs and applications
Recommended article: On the Nash-Williams' lemma in graph reconstruction theory
Recommended article: Determining \(r\)- and \((r,s)\)-robustness of digraphs using mixed integer linear programming
Recommended article: Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
Recommended article: Q3824449
Recommended article: LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Recommended article: On the complexity of graph reconstruction