Pages that link to "Item:Q3158513"
From MaRDI portal
The following pages link to Proof verification and the hardness of approximation problems (Q3158513):
Displaying 50 items.
- Combinatorial PCPs with short proofs (Q260390) (← links)
- Bounds on 2-query locally testable codes with affine tests (Q280942) (← links)
- A natural family of optimization problems with arbitrarily small approximation thresholds (Q293457) (← links)
- Sparse approximation is provably hard under coherent dictionaries (Q340554) (← links)
- Reoptimization of constraint satisfaction problems with approximation resistant predicates (Q380664) (← links)
- On testing monomials in multivariate polynomials (Q391220) (← links)
- A closest vector problem arising in radiation therapy planning (Q411241) (← links)
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms (Q411835) (← links)
- Max-leaves spanning tree is APX-hard for cubic graphs (Q414465) (← links)
- New results for the longest haplotype reconstruction problem (Q423956) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- Theoretical formulation of finite-dimensional discrete phase spaces. I: Algebraic structures and uncertainty principles (Q436261) (← links)
- Colouring, constraint satisfaction, and complexity (Q458466) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Regular inference as vertex coloring (Q465248) (← links)
- Reoptimization of max \(k\)-cover: approximation ratio threshold (Q466363) (← links)
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field (Q466374) (← links)
- Combinatorial PCPs with efficient verifiers (Q483706) (← links)
- Approximating \(k\)-generalized connectivity via collapsing HSTs (Q491201) (← links)
- The complexity of debate checking (Q493647) (← links)
- New inapproximability bounds for TSP (Q494069) (← links)
- Shorter arithmetization of nondeterministic computations (Q496013) (← links)
- Unrelated parallel machine scheduling -- perspectives and progress (Q505093) (← links)
- Improved approximation algorithms for projection games (Q513283) (← links)
- Limitations of incremental dynamic programming (Q517805) (← links)
- Best-order streaming model (Q534570) (← links)
- Testing juntas (Q598252) (← links)
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR (Q603915) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- On the hardness of learning intersections of two halfspaces (Q619909) (← links)
- Computing bond orders in molecule graphs (Q631782) (← links)
- Derandomized parallel repetition via structured PCPs (Q645129) (← links)
- PCP characterizations of NP: toward a polynomially-small error-probability (Q649097) (← links)
- Structure of polynomial-time approximation (Q692893) (← links)
- Towards lower bounds on locally testable codes via density arguments (Q693000) (← links)
- The full Steiner tree problem (Q702772) (← links)
- The checkpoint problem (Q714790) (← links)
- Fair and efficient cake division with connected pieces (Q776236) (← links)
- Model independent approach to probabilistic models (Q831149) (← links)
- Quantum information and the PCP theorem (Q835644) (← links)
- Hard constraint satisfaction problems have hard gaps at location 1 (Q837178) (← links)
- A note on unique games (Q845686) (← links)
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing (Q848846) (← 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)
- Packing trees in communication networks (Q1016048) (← links)
- Efficient approximation of Min Set Cover by moderately exponential algorithms (Q1019736) (← links)
- Approximation algorithms for the weighted independent set problem in sparse graphs (Q1028454) (← links)
