Randomness-optimal characterization of two NP proof systems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1256635
- Nondeterministic functions and the existence of optimal proof systems
- Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
- Randomisation and derandomisation in descriptive complexity theory
- Randomisation and derandomisation in descriptive complexity theory
- On optimal algorithms and optimal proof systems
- Rigorous results for random (2+p)-SAT
- Probabilistic checking of proofs
- On characterizations of randomized computation using plain Kolmogorov complexity
- On characterizations of randomized computation using plain Kolmogorov complexity
Cited in
(12)- Randomness in interactive proofs
- Input-oblivious proof systems and a uniform complexity perspective on P/poly
- Perfect Non-interactive Zero Knowledge for NP
- Randomness-efficient non-interactive zero knowledge
- Non-interactive zero-knowledge: A low randomness characterization of NP
- Round complexity versus randomness complexity in interactive proofs
- Derandomization in Cryptography
- Advances in Cryptology - CRYPTO 2003
- Nondeterministic seedless oritatami systems and hardness of testing their equivalence
- On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
- Cryptography in the multi-string model
- Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs
This page was built for publication: Randomness-optimal characterization of two NP proof systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4440437)
