Pages that link to "Item:Q3158513"
From MaRDI portal
The following pages link to Proof verification and the hardness of approximation problems (Q3158513):
Displayed 49 items.
- Testing juntas (Q598252) (← links)
- The full Steiner tree problem (Q702772) (← links)
- Approximation algorithms for general packing problems and their application to the multicast congestion problem (Q925266) (← links)
- Inapproximability results for combinatorial auctions with submodular utility functions (Q943868) (← links)
- Complete partitions of graphs (Q949754) (← links)
- Approximating the selected-internal Steiner tree (Q995588) (← 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)
- Fast approximate PCPs for multidimensional bin-packing problems (Q1767978) (← links)
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example (Q1771343) (← 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)
- Testing of matrix-poset properties (Q2460630) (← links)
- Constrained sequence alignment: A general model and the hardness results (Q2462385) (← links)
- From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization (Q2465055) (← links)
- Finding edge-disjoint paths in networks: an ant colony optimization algorithm (Q2466394) (← links)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \) (Q2475406) (← links)
- Inapproximability results for the lateral gene transfer problem (Q2479568) (← links)
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms (Q2490259) (← links)
- Complexity results on restricted instances of a paint shop problem for words (Q2492209) (← links)
- TSP with bounded metrics (Q2495398) (← links)
- On the severity of Braess's paradox: designing networks for selfish users is hard (Q2496322) (← links)
- Parameterized computation and complexity: a new approach dealing with NP-hardness (Q2576825) (← links)
- What can be efficiently reduced to the Kolmogorov-random strings? (Q2576937) (← links)
- Genus characterizes the complexity of certain graph problems: Some tight results (Q2641866) (← links)
- (Q2741527) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- Succinct NP Proofs from an Extractability Assumption (Q3507432) (← links)
- Expander graphs and their applications (Q3514498) (← links)
- New construction for a QMA complete three-local Hamiltonian (Q3529790) (← links)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP (Q3608306) (← links)
- Polylogarithmic two-round argument systems (Q3612244) (← links)
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD (Q4528764) (← links)
- Simple analysis of graph tests for linearity and PCP (Q4800393) (← links)
- The Complexity of Zero Knowledge (Q5458822) (← links)
- CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM (Q5714670) (← links)
- On the advantage over a random assignment (Q5894908) (← links)
- Linear-consistency testing. (Q5946056) (← links)