Pages that link to "Item:Q5248498"
From MaRDI portal
The following pages link to Efficient probabilistically checkable proofs and applications to approximations (Q5248498):
Displayed 35 items.
- 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)
- 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 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)
- Approximation algorithms and hardness results for labeled connectivity problems (Q2426652) (← links)
- Maximum agreement and compatible supertrees (Q2466022) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2) (Q3541815) (← links)
- Robust locally testable codes and products of codes (Q5486320) (← links)
- Hardness of approximate two-level logic minimization and PAC learning with membership queries (Q5920702) (← links)
- Linear-consistency testing. (Q5946056) (← links)