scientific article; zbMATH DE number 512803

MaRDI QIDQ4281496zbMATH OpenFDO

Authors Anne Condon

Publication date 7 April 1994

zbMATH Keywords

space bounded interactive proof systems

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of interactive proofs with bounded communication
• scientific article; zbMATH DE number 66620
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• scientific article; zbMATH DE number 4106274

Cited in

(17)

• An application of quantum finite automata to interactive proof systems
• Space bounded computations: Review and new separation results
• Efficient rational proofs for space bounded computations
• Affine automata verifiers
• Simple proofs of space-time and rational proofs of storage
• Constant-space quantum interactive proofs against multiple provers
• Tight proofs of space and replication
• Interactive proofs with quantum finite automata
• A framework for space complexity in algebraic proof systems
• On the complexity of interactive proofs with bounded communication
• scientific article; zbMATH DE number 176510 (Why is no real title available?)
• scientific article; zbMATH DE number 1024045 (Why is no real title available?)
• Verifiable stream computation and Arthur-Merlin communication
• On the virtue of succinct proofs
• Term Rewriting and Applications
• Classical and quantum Merlin-Arthur automata
• \(\mathrm{P}\) has polynomial-time finite-state verifiers

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4281496)