Pages that link to "Item:Q4230321"

The following pages link to Probabilistic checking of proofs; a new characterization of NP (Q4230321):

Displaying 50 items.

• A branch and cut solver for the maximum stable set problem (Q491210) (← links)
• PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
• Approximate solution of NP optimization problems (Q672315) (← links)
• On approximating the longest path in a graph (Q679451) (← links)
• A well-characterized approximation problem (Q688442) (← links)
• Pseudo-Boolean optimization (Q697569) (← links)
• A note on unique games (Q845686) (← links)
• Statistical analysis of financial networks (Q957122) (← links)
• The ideal membership problem and polynomial identity testing (Q963063) (← links)
• Bounding queries in the analytic polynomial-time hierarchy (Q1274987) (← links)
• Integer programming as a framework for optimization and approximability (Q1276163) (← links)
• Zero knowledge and the chromatic number (Q1276168) (← links)
• Extracting randomness: A survey and new constructions (Q1305929) (← links)
• The hardness of approximation: Gap location (Q1332662) (← links)
• A short note on the approximability of the maximum leaves spanning tree problem (Q1336751) (← links)
• On the power of multi-prover interactive protocols (Q1341733) (← links)
• Theorems for a price: Tomorrow's semi-rigorous mathematical culture (Q1343655) (← links)
• The death of proof? Semi-rigorous mathematics? You've got to be kidding! (Q1343656) (← links)
• Probabilistically checkable proofs and their consequences for approximation algorithms (Q1344618) (← links)
• A note on PCP vs. MIP (Q1350618) (← links)
• The hardness of approximate optima in lattices, codes, and systems of linear equations (Q1356888) (← links)
• MNP: A class of NP optimization problems (Q1368182) (← links)
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function (Q1375058) (← links)
• Approximating the independence number via the \(\vartheta\)-function (Q1380939) (← links)
• Some APX-completeness results for cubic graphs (Q1566710) (← links)
• Annealed replication: A new heuristic for the maximum clique problem (Q1613385) (← links)
• Ramsey theory and integrality gap for the independent set problem (Q1667206) (← links)
• Derandomized graph products (Q1842777) (← links)
• The inapproximability of non-NP-hard optimization problems. (Q1853546) (← links)
• On weighted vs unweighted versions of combinatorial optimization problems (Q1854428) (← links)
• Bounded queries, approximations, and the Boolean hierarchy (Q1854449) (← links)
• The complexity of approximating a nonlinear program (Q1906280) (← links)
• Efficient checking of polynomials and proofs and the hardness of approximation problems (Q1906841) (← links)
• Simulating BPP using a general weak random source (Q1923854) (← links)
• Improved non-approximability results for minimum vertex cover with density constraints (Q1960657) (← links)
• Probabilistic verification of proofs in calculuses (Q1977920) (← links)
• Boosting verifiable computation on encrypted data (Q2055689) (← links)
• ZK-PCPs from leakage-resilient secret sharing (Q2159466) (← links)
• Solving the maximum duo-preservation string mapping problem with linear programming (Q2440161) (← links)
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy (Q2456368) (← links)
• Clique-detection models in computational biochemistry and genomics (Q2491763) (← links)
• Mining market data: a network approach (Q2499151) (← links)
• On maximum planar induced subgraphs (Q2500525) (← links)
• Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits (Q2799088) (← links)
• A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems (Q2883604) (← links)
• Proof verification and the hardness of approximation problems (Q3158513) (← links)
• Probabilistic checking of proofs (Q3841041) (← links)
• On limited versus polynomial nondeterminism (Q4259986) (← links)
• (Q4440437) (← links)
• How NP got a new definition: A survey of probabilistically checkable proofs (Q4549231) (← links)