Pages that link to "Item:Q5248498"

The following pages link to Efficient probabilistically checkable proofs and applications to approximations (Q5248498):

Displaying 50 items.

• A self-tester for linear functions over the integers with an elementary proof of correctness (Q315532) (← links)
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm (Q498420) (← links)
• Derandomized parallel repetition via structured PCPs (Q645129) (← links)
• Approximate solution of NP optimization problems (Q672315) (← links)
• Primal-dual approximation algorithms for integral flow and multicut in trees (Q679443) (← links)
• Approximating the tree and tour covers of a graph (Q688437) (← links)
• A well-characterized approximation problem (Q688442) (← links)
• Approximating cost-based abduction is NP-hard (Q814635) (← links)
• Fault detection tests for stuck-at faults on parity counter inputs (Q895069) (← links)
• Hardness of approximating the minimum solutions of linear Diophantine equations (Q1022600) (← links)
• Testing algebraic geometric codes (Q1047829) (← links)
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems (Q1274926) (← links)
• Zero knowledge and the chromatic number (Q1276168) (← links)
• Reconstructing a history of recombinations from a set of sequences (Q1281773) (← links)
• The minimum feature set problem (Q1338270) (← 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)
• The hardness of approximate optima in lattices, codes, and systems of linear equations (Q1356888) (← links)
• The complexity and approximability of finding maximum feasible subsystems of linear relations (Q1367542) (← links)
• MNP: A class of NP optimization problems (Q1368182) (← links)
• Approximating covering integer programs with multiplicity constraints (Q1406040) (← links)
• Interactive and probabilistic proof-checking (Q1577488) (← links)
• Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
• Annealed replication: A new heuristic for the maximum clique problem (Q1613385) (← links)
• The complexity of probabilistic lobbying (Q1662102) (← links)
• The approximability of non-Boolean satisfiability problems and restricted integer programming (Q1770383) (← links)
• On the domination search number (Q1811076) (← links)
• The inapproximability of non-NP-hard optimization problems. (Q1853546) (← links)
• On weighted vs unweighted versions of combinatorial optimization problems (Q1854428) (← links)
• Algebraic testing and weight distributions of codes. (Q1874387) (← links)
• Scheduling of conditional executed jobs on unrelated processors (Q1897352) (← links)
• Almost optimal set covers in finite VC-dimension (Q1906049) (← links)
• The complexity of approximating a nonlinear program (Q1906280) (← links)
• A computationally intractable problem on simplicial complexes (Q1917045) (← links)
• Improved non-approximability results for minimum vertex cover with density constraints (Q1960657) (← links)
• Easy capacitated facility location problems, with connections to lot-sizing (Q1984675) (← links)
• Subquadratic SNARGs in the random oracle model (Q2120100) (← links)
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem (Q2165784) (← links)
• Timetabling with passenger routing (Q2260893) (← links)
• Approximating multidimensional subset sum and Minkowski decomposition of polygons (Q2364904) (← links)
• Low-degree test with polynomially small error (Q2410685) (← links)
• Approximation algorithms and hardness results for labeled connectivity problems (Q2426652) (← links)
• Maximum agreement and compatible supertrees (Q2466022) (← links)
• Three-player entangled XOR games are NP-hard to approximate (Q2816299) (← links)
• Maximizing Polynomials Subject to Assignment Constraints (Q3012829) (← links)
• Short Locally Testable Codes and Proofs (Q3088191) (← links)
• On Khot’s unique games conjecture (Q3109809) (← links)
• On Dinur’s proof of the PCP theorem (Q3430210) (← links)
• Breaking the ε-Soundness Bound of the Linearity Test over GF(2) (Q3541815) (← links)
• Bicriteria Network Design Problems (Q4216149) (← links)