Pages that link to "Item:Q3158513"

The following pages link to Proof verification and the hardness of approximation problems (Q3158513):

Displaying 50 items.

• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
• Cryptography with constant input locality (Q1037233) (← links)
• On the hardness of approximating max-satisfy (Q1045886) (← links)
• Testing algebraic geometric codes (Q1047829) (← links)
• Approximating maximum independent sets by excluding subgraphs (Q1196452) (← links)
• Non-approximability of weighted multiple sequence alignment. (Q1401267) (← links)
• Quantum multi-prover interactive proof systems with limited prior entanglement. (Q1401955) (← links)
• Spot-checkers (Q1577018) (← links)
• Interactive and probabilistic proof-checking (Q1577488) (← links)
• A randomized approximation scheme for metric MAX-CUT (Q1604207) (← links)
• Bottleneck bichromatic full Steiner trees (Q1628678) (← links)
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (Q1631680) (← links)
• The traveling salesman problem on grids with forbidden neighborhoods (Q1680496) (← links)
• The hunting of the SNARK (Q1698394) (← links)
• Sparsification and subexponential approximation (Q1702300) (← links)
• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems (Q1730018) (← links)
• Fast approximate PCPs for multidimensional bin-packing problems (Q1767978) (← links)
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example (Q1771343) (← links)
• Submodular unsplittable flow on trees (Q1801021) (← links)
• Steiner trees in uniformly quasi-bipartite graphs. (Q1853068) (← links)
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. (Q1854505) (← links)
• Differential approximation for optimal satisfiability and related problems (Q1869721) (← links)
• One complexity theorist's view of quantum computing (Q1870556) (← links)
• Algebraic testing and weight distributions of codes. (Q1874387) (← links)
• Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
• On the approximability of clique and related maximization problems (Q1877696) (← links)
• Fast approximate probabilistically checkable proofs (Q1881217) (← links)
• Inapproximability results for equations over finite groups (Q1884871) (← links)
• Exponential inapproximability of selecting a maximum volume sub-matrix (Q1939669) (← links)
• Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials (Q1944393) (← links)
• A case of depth-3 identity testing, sparse factorization and duality (Q1947039) (← links)
• 2-transitivity is insufficient for local testability (Q1947041) (← links)
• Connected facility location via random facility sampling and core detouring (Q1959419) (← links)
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) (Q2018136) (← links)
• The Chinese deliveryman problem (Q2025136) (← links)
• Smooth and strong PCPs (Q2029773) (← links)
• On succinct arguments and witness encryption from groups (Q2096510) (← links)
• Spartan: efficient and general-purpose zkSNARKs without trusted setup (Q2104239) (← links)
• A PCP of proximity for real algebraic polynomials (Q2117096) (← links)
• Subquadratic SNARGs in the random oracle model (Q2120100) (← links)
• On regularity of Max-CSPs and Min-CSPs (Q2122790) (← links)
• Bayesian agency: linear versus tractable contracts (Q2124461) (← links)
• Succinct non-interactive arguments via linear interactive proofs (Q2136170) (← links)
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs (Q2163394) (← links)
• Real-time, constant-space, constant-randomness verifiers (Q2164756) (← links)
• Approximation algorithms for clustering with dynamic points (Q2168849) (← links)
• A PCP theorem for interactive proofs and applications (Q2170038) (← links)
• Succinct arguments in the quantum random oracle model (Q2175929) (← links)
• Linear-size constant-query IOPs for delegating computation (Q2175951) (← links)
• On the (In)security of Kilian-based SNARGs (Q2175953) (← links)