scientific article; zbMATH DE number 7559068
From MaRDI portal
Publication:5090398
DOI10.4230/LIPIcs.ITCS.2019.25zbMath1499.68116MaRDI QIDQ5090398
Alessandro Chiesa, Igor Shinkar, Peter Manohar
Publication date: 18 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (1)
Cites Work
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Self-testing/correcting with applications to numerical problems
- On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
- On the Space Complexity of Linear Programming with Preprocessing
- Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Polynomial-Space Approximation of No-Signaling Provers
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- Computationally Sound Proofs
- How to delegate computations
- Delegation for bounded space
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- No-signaling linear PCPs
This page was built for publication:
