Pages that link to "Item:Q4388899"
From MaRDI portal
The following pages link to Free Bits, PCPs, and Nonapproximability---Towards Tight Results (Q4388899):
Displayed 50 items.
- Local correction of juntas (Q437678) (← links)
- Randomly colouring graphs (a combinatorial view) (Q458462) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Improved approximation algorithms for projection games (Q513283) (← links)
- On the approximability of robust spanning tree problems (Q620950) (← links)
- Algorithmic and hardness results for the colorful components problems (Q747623) (← links)
- A note on unique games (Q845686) (← links)
- The longest common subsequence problem for arc-annotated sequences (Q876717) (← links)
- Approximation algorithms for Hamming clustering problems (Q876719) (← links)
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring (Q891178) (← links)
- Inapproximability and approximability of minimal tree routing and coloring (Q935848) (← links)
- Partition into cliques for cubic graphs: Planar case, complexity and approximation (Q947111) (← links)
- The 0-1 inverse maximum stable set problem (Q955316) (← links)
- Approximating maximum satisfiable subsystems of linear equations of bounded width (Q963367) (← links)
- Simple ingredients leading to very efficient heuristics for the maximum clique problem (Q1009196) (← links)
- Why greed works for shortest common superstring problem (Q1038476) (← links)
- Priority algorithms for graph optimization problems (Q1041242) (← links)
- On the hardness of approximating max-satisfy (Q1045886) (← links)
- Zero knowledge and the chromatic number (Q1276168) (← links)
- On the hardness of efficiently approximating maximal non-\(L\) submatrices. (Q1418978) (← links)
- Interactive and probabilistic proof-checking (Q1577488) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- Approximation and hardness results for the max \(k\)-uncut problem (Q1630990) (← links)
- Optimal approximation algorithms for maximum distance-bounded subgraph problems (Q1635712) (← links)
- Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems (Q1751224) (← links)
- The approximability of non-Boolean satisfiability problems and restricted integer programming (Q1770383) (← links)
- Designing small keyboards is hard (Q1770399) (← links)
- The complexity of Boolean constraint satisfaction local search problems (Q1777392) (← links)
- On the span in channel assignment problems: Bounds, computing and counting (Q1810659) (← links)
- On weighted vs unweighted versions of combinatorial optimization problems (Q1854428) (← links)
- Algebraic testing and weight distributions of codes. (Q1874387) (← links)
- Towards optimal lower bounds for clique and chromatic number. (Q1874411) (← links)
- Inapproximability results for equations over finite groups (Q1884871) (← links)
- Computational aspects of the 2-dimension of partially ordered sets (Q1884957) (← links)
- On regularity of Max-CSPs and Min-CSPs (Q2122790) (← links)
- New tools and connections for exponential-time approximation (Q2272598) (← links)
- Distributed computing with advice: information sensitivity of graph coloring (Q2377267) (← links)
- Solving the weighted MAX-SAT problem using the dynamic convexized method (Q2439524) (← links)
- An ant-based algorithm for coloring graphs (Q2467354) (← links)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \) (Q2475406) (← links)
- Inapproximability and approximability of maximal tree routing and coloring (Q2498986) (← links)
- Approximating the minimum clique cover and other hard problems in subtree filament graphs (Q2506362) (← links)
- Column subset selection problem is UG-hard (Q2637653) (← links)
- Maximum cut-clique problem: ILS heuristics and a data analysis application (Q2806429) (← links)
- Three-Player Entangled XOR Games are NP-Hard to Approximate (Q2816299) (← links)
- A Characterization of Graphs with Fractional Total Chromatic Number Equal to (Q2840543) (← links)
- Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring (Q2885476) (← links)
- Strong Inapproximability of the Shortest Reset Word (Q2946340) (← links)
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete (Q2954372) (← links)
- Approximation and Hardness Results for the Max k-Uncut Problem (Q2958303) (← links)