Input-oblivious proof systems and a uniform complexity perspective on P/poly

DOI10.1145/2799645MaRDI QIDQ2828212zbMATH OpenOpenAlexWikidataFDO

Authors Oded Goldreich, Or Meir

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

BPPEEXPIPMANENEXPNPP/polyPCPRPZK

Mathematics Subject Classification ID

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

Recommendations

• Oblivious Symmetric Alternation
• scientific article; zbMATH DE number 4106274
• scientific article; zbMATH DE number 66620
• Interactive proof systems with polynomially bounded strategies
• scientific article; zbMATH DE number 2019634

Cites work

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

Cited in

(5)

• On Input Indistinguishable Proof Systems
• Oblivious Symmetric Alternation
• Even quantum advice is unlikely to solve \(\mathsf{PP}\)
• On exponential-time hypotheses, derandomization, and circuit lower bounds
• Oblivious complexity classes revisited: lower bounds and hierarchies

This page was built for publication: Input-oblivious proof systems and a uniform complexity perspective on P/poly

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