Interactive and probabilistic proof-checking (Q1577488): Difference between revisions

@@ Property / cites work @@
+Statistical zero-knowledge languages can be recognized in two rounds
+Normal rank
@@ Property / cites work @@
+Q4542552
@@ Property / cites work: Q4542552 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Probabilistic checking of proofs
@@ Property / cites work: Probabilistic checking of proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4527016
@@ Property / cites work: Q4527016 / rank @@
+Normal rank
@@ Property / cites work @@
+Non-deterministic exponential time has two-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Efficient probabilistically checkable proofs and applications to approximations
+Normal rank
@@ Property / cites work @@
+Improved non-approximability results
@@ Property / cites work: Improved non-approximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Q5750398
@@ Property / cites work: Q5750398 / rank @@
+Normal rank
@@ Property / cites work @@
+Does co-NP have short interactive proofs ?
@@ Property / cites work: Does co-NP have short interactive proofs ? / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542539
@@ Property / cites work: Q4542539 / rank @@
+Normal rank
@@ Property / cites work @@
+The random oracle hypothesis is false
@@ Property / cites work: The random oracle hypothesis is false / rank @@
+Normal rank
@@ Property / cites work @@
+Two prover protocols
@@ Property / cites work: Two prover protocols / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of multi-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Are there interactive protocols for co-NP languages?
+Normal rank
@@ Property / cites work @@
+Q3413440
@@ Property / cites work: Q3413440 / rank @@
+Normal rank
@@ Property / cites work @@
+Modern cryptography, probabilistic proofs and pseudo-randomness
+Normal rank
@@ Property / cites work @@
+Q4542514
@@ Property / cites work: Q4542514 / rank @@
+Normal rank
@@ Property / cites work @@
+Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
+Normal rank
@@ Property / cites work @@
+The Knowledge Complexity of Interactive Proof Systems
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Q4526964
@@ Property / cites work: Q4526964 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Q4871218
@@ Property / cites work: Q4871218 / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228522
@@ Property / cites work: Q4228522 / rank @@
+Normal rank
@@ Property / cites work @@
+Games against nature
@@ Property / cites work: Games against nature / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4224935
@@ Property / cites work: Q4224935 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3392273
@@ Property / cites work: Q3392273 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542548
@@ Property / cites work: Q4542548 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0168-0072(00)00017-8
+Normal rank
@@ Property / OpenAlex ID @@
+W1996183456
@@ Property / OpenAlex ID: W1996183456 / rank @@
+Normal rank