Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

DOI10.1145/2799645zbMath1347.68160OpenAlexW2247361196MaRDI QIDQ2828212

Or Meir, Oded Goldreich

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2799645

zbMATH Keywords

MAEXPP/polyPCPIPRPNPBPPENENEXPZK

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• BPP and the polynomial hierarchy
• Robust algorithms: a different approach to oracles
• On helping by robust oracle machines
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Proof verification and the hardness of approximation problems
• The learnability of quantum states
• Probabilistic checking of proofs
• Computing with Very Weak Random Sources
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Foundations of Cryptography
• Tiny families of functions with random properties: A quality-size trade-off for hashing
• Tally languages and complexity classes
• ON HELPING AND INTERACTIVE PROOF SYSTEMS
• Oblivious Symmetric Alternation
• Computational Complexity