New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
type: Item
instance of: scholarly article
title: New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
zbMATH Open document ID: 1059.68043
author: Vikraman Arvind
author: Johannes Köbler
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1910835
zbMATH Keywords: lowness
zbMATH Keywords: self-reducible set
zbMATH Keywords: interactive proof system
zbMATH Keywords: probabilistic class
zbMATH Keywords: function class
zbMATH Keywords: program checker.
MaRDI profile type: Publication
full work available at URL: jcss.2002.1835
OpenAlex ID: W1988254244
cites work: Q4370034
cites work: Q4525694
cites work: Bounded Round Interactive Proofs in Finite Groups
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Oracles and queries that are sufficient for exact learning
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Self-reducibility
cites work: Designing programs that check their work
cites work: Quantitative Relativizations of Complexity Classes
cites work: Q4258566
cites work: Q4218419
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: Q4336270
cites work: Q4273947
cites work: Q4218123
cites work: New Collapse Consequences of NP Having Small Circuits
cites work: Circuit size relative to pseudorandom oracles
cites work: Hardness vs randomness
cites work: Q4298260
cites work: Relativized Arthur-Merlin versus Merlin-Arthur games
cites work: A low and a high hierarchy within NP
cites work: Probabilistic complexity classes and lowness
cites work: A taxonomy of complexity classes of functions
DOI: 10.1006/JCSS.2002.1835
description: scientific article; zbMATH DE number 1910835