Pages that link to "Item:Q685724"

The following pages link to Non-deterministic exponential time has two-prover interactive protocols (Q685724):

Displaying 50 items.

• Bounds on 2-query locally testable codes with affine tests (Q280942) (← links)
• A self-tester for linear functions over the integers with an elementary proof of correctness (Q315532) (← links)
• Model-checking hierarchical structures (Q414908) (← links)
• Combinatorial PCPs with efficient verifiers (Q483706) (← links)
• The complexity of debate checking (Q493647) (← links)
• Improved approximation algorithms for projection games (Q513283) (← links)
• Symmetric LDPC codes and local testing (Q519972) (← links)
• Average-case intractability vs. worst-case intractability (Q598182) (← links)
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
• PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
• Locally random reductions: Improvements and applications (Q676825) (← links)
• Arithmetization: A new method in structural complexity theory (Q685721) (← links)
• Non-deterministic exponential time has two-prover interactive protocols (Q685724) (← links)
• Avoiding simplicity is complex (Q693072) (← links)
• Model independent approach to probabilistic models (Q831149) (← links)
• Quantum information and the PCP theorem (Q835644) (← links)
• Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
• On being incoherent without being very hard (Q1198954) (← links)
• The complexity of the max word problem and the power of one-way interactive proof systems (Q1312183) (← links)
• Self-testing/correcting with applications to numerical problems (Q1317490) (← links)
• PSPACE is provable by two provers in one round (Q1318475) (← links)
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029) (← links)
• The power of adaptiveness and additional queries in random-self- reductions (Q1332664) (← links)
• The random oracle hypothesis is false (Q1333397) (← links)
• On the power of multi-prover interactive protocols (Q1341733) (← links)
• Probabilistically checkable proofs and their consequences for approximation algorithms (Q1344618) (← links)
• A note on PCP vs. MIP (Q1350618) (← links)
• On proving that a graph has no large clique: A connection with Ramsey theory (Q1351164) (← links)
• Fully parallelized multi-prover protocols for NEXP-time (Q1356878) (← links)
• The hardness of approximate optima in lattices, codes, and systems of linear equations (Q1356888) (← links)
• Quantum multi-prover interactive proof systems with limited prior entanglement. (Q1401955) (← links)
• Spot-checkers (Q1577018) (← links)
• Interactive and probabilistic proof-checking (Q1577488) (← links)
• Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
• Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
• Fast approximate PCPs for multidimensional bin-packing problems (Q1767978) (← links)
• Multi-prover encoding schemes and three-prover proof systems (Q1816732) (← links)
• Uniform generation of NP-witnesses using an NP-oracle (Q1854397) (← links)
• PSPACE has constant-round quantum interactive proof systems (Q1870552) (← links)
• One complexity theorist's view of quantum computing (Q1870556) (← links)
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (Q1872705) (← links)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
• Algebraic testing and weight distributions of codes. (Q1874387) (← links)
• The complexity of approximating a nonlinear program (Q1906280) (← links)
• Simulating BPP using a general weak random source (Q1923854) (← links)
• 2-transitivity is insufficient for local testability (Q1947041) (← links)
• Probabilistic verification of proofs in calculuses (Q1977920) (← links)
• Parallelization of entanglement-resistant multi-prover interactive proofs (Q2015158) (← links)
• Sumcheck arguments and their applications (Q2120101) (← links)