Does co-NP have short interactive proofs ?
From MaRDI portal
Publication:1108004
DOI10.1016/0020-0190(87)90232-8zbMath0653.68037OpenAlexW2077202644WikidataQ56959258 ScholiaQ56959258MaRDI QIDQ1108004
Stathis Zachos, Ravi B. Boppana, Johan T. Håstad
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90232-8
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Algorithms for Group Isomorphism via Group Extensions and Cohomology, Stathis Zachos at 70!, The random oracle hypothesis is false, The knowledge complexity of quadratic residuosity languages, An approach to parallel algorithm design, On the complexity of interactive proofs with bounded communication, The complexity of generating test instances, On the power of multi-prover interactive protocols, Succinct non-interactive arguments via linear interactive proofs, The QAP-polytope and the graph isomorphism problem, New invariants for the graph isomorphism problem, A one-round, two-prover, zero-knowledge protocol for NP, On the (In)Security of SNARKs in the Presence of Oracles, Interactive Oracle Proofs, Zero-Knowledge Interactive Proof Systems for New Lattice Problems, On the hardness of computing the permanent of random matrices, Fully parallelized multi-prover protocols for NEXP-time, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Graph isomorphism for graph classes characterized by two forbidden induced subgraphs, Probabilistic quantifiers and games, Graph isomorphism is in the low hierarchy, Relativized Arthur-Merlin versus Merlin-Arthur games, Are there interactive protocols for co-NP languages?, On the complexity of graph reconstruction, Zero knowledge and circuit minimization, Statistical difference beyond the polarizing regime, Solvable black-box group problems are low for PP, Practical proofs of knowledge without relying on theoretical proofs of membership on languages, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes, The final nail in the coffin of statistically-secure obfuscator, Which languages have 4-round zero-knowledge proofs?, The hunting of the SNARK, Indistinguishability obfuscation, On the Power of Statistical Zero Knowledge, A discrete logarithm implementation of perfect zero-knowledge blobs, ON HIGHER ARTHUR-MERLIN CLASSES, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Practic zero-knowledge proofs: Giving hints and using deficiencies, On relationships between statistical zero-knowledge proofs, The complexity of local dimensions for constructible sets, Structure Versus Hardness Through the Obfuscation Lens, The reachability problem for finite cellular automata, A framework for non-interactive instance-dependent commitment schemes (NIC), Beating the generator-enumeration bound for \(p\)-group isomorphism, A language-dependent cryptographic primitive, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, On the expression complexity of equivalence and isomorphism of primitive positive formulas, Graph isomorphism is low for PP, Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects, Graph Isomorphism is in SPP, On zero error algorithms having oracle access to one query, Complexity classes of equivalence problems revisited, Abstract Storage Devices, Error-bounded probabilistic computations between MA and AM, On Basing Private Information Retrieval on NP-Hardness, One-message statistical Zero-Knowledge Proofs and space-bounded verifier, Nearly linear time isomorphism algorithms for some nonabelian group classes, The Complexity of Zero Knowledge, A note on the distribution of the distance from a lattice, On best-possible obfuscation, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, On hiding information from an oracle, Probabilistic complexity classes and lowness, Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More), On the power of interaction, Permutation Groups and the Graph Isomorphism Problem, Hybrid commitments and their applications to zero-knowledge proof systems, $$P\mathop{ =}\limits^{?}NP$$, Graph isomorphism is low for PP, Generalized lowness and highness and probabilistic complexity classes, The counting complexity of group-definable languages, On the limits of nonapproximability of lattice problems, Interactive and probabilistic proof-checking, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., On succinct arguments and witness encryption from groups, How much randomness is needed to convert MA protocols to AM protocols?, Statistical zero-knowledge languages can be recognized in two rounds, Relativized perfect zero knowledge is not BPP, The remote set problem on lattices, Randomness in interactive proofs
Cites Work
- A low and a high hierarchy within NP
- Some observations on the probabilistic algorithms and NP-hard problems
- The polynomial-time hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Computational Complexity of Probabilistic Turing Machines
- The knowledge complexity of interactive proof-systems
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
