Free Bits, PCPs, and Nonapproximability---Towards Tight Results
From MaRDI portal
Publication:4388899
DOI10.1137/S0097539796302531zbMath0912.68041MaRDI QIDQ4388899
Madhu Sudan, Mihir Bellare, Oded Goldreich
Publication date: 10 May 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
Algebraic testing and weight distributions of codes., Towards optimal lower bounds for clique and chromatic number., On regularity of Max-CSPs and Min-CSPs, Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring, Inapproximability results for equations over finite groups, Computational aspects of the 2-dimension of partially ordered sets, Approximation and hardness results for the max \(k\)-uncut problem, Simple analysis of graph tests for linearity and PCP, Cube vs. Cube Low Degree Test., Optimal approximation algorithms for maximum distance-bounded subgraph problems, Distributed computing with advice: information sensitivity of graph coloring, A note on unique games, Coloration de graphes : fondements et applications, Column subset selection problem is UG-hard, A query efficient non-adaptive long code test with perfect completeness, The longest common subsequence problem for arc-annotated sequences, Approximation algorithms for Hamming clustering problems, Strong Inapproximability of the Shortest Reset Word, Reducing Testing Affine Spaces to Testing Linearity of Functions, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Max-3-Lin over non-abelian groups with universal factor graphs, On the approximability of robust spanning tree problems, Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete, Asymptotics of the chromatic number for quasi-line graphs, Optimizing concurrency under Scheduling by Edge Reversal, Pseudorandom sets in Grassmann graph have near-perfect expansion, Why Greed Works for Shortest Common Superstring Problem, Approximation and Hardness Results for the Max k-Uncut Problem, Max-Cut via Kuramoto-Type Oscillators, Mathematics of computation through the lens of linear equations and lattices, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, Unnamed Item, Local correction of juntas, Solving the weighted MAX-SAT problem using the dynamic convexized method, On the hardness of efficiently approximating maximal non-\(L\) submatrices., Introduction to Testing Graph Properties, Randomly colouring graphs (a combinatorial view), A survey on the structure of approximation classes, Distributed Graph Algorithms and their Complexity: An Introduction, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Inapproximability and approximability of minimal tree routing and coloring, Partition into cliques for cubic graphs: Planar case, complexity and approximation, An ant-based algorithm for coloring graphs, Revisiting alphabet reduction in Dinur’s PCP., Improved approximation algorithms for projection games, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, The 0-1 inverse maximum stable set problem, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Approximating maximum satisfiable subsystems of linear equations of bounded width, The approximability of non-Boolean satisfiability problems and restricted integer programming, Designing small keyboards is hard, Limitation on the Rate of Families of Locally Testable Codes, Testing Juntas: A Brief Survey, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Invariance in Property Testing, Query-Efficient Dictatorship Testing with Perfect Completeness, Linear-consistency testing., New tools and connections for exponential-time approximation, The complexity of Boolean constraint satisfaction local search problems, Inapproximability and approximability of maximal tree routing and coloring, Approximating the minimum clique cover and other hard problems in subtree filament graphs, Extracting all the randomness and reducing the error in Trevisan's extractors, Maximum cut-clique problem: ILS heuristics and a data analysis application, Unnamed Item, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Proximity Oblivious Testing and the Role of Invariances, Proximity Oblivious Testing and the Role of Invariances, On the advantage over a random assignment, Algorithmic and hardness results for the colorful components problems, Three-Player Entangled XOR Games are NP-Hard to Approximate, On the span in channel assignment problems: Bounds, computing and counting, Satisfying Degree-d Equations over GF[2 n], Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Short Locally Testable Codes and Proofs, Bravely, Moderately: A Common Theme in Four Recent Works, On the Complexity of Computational Problems Regarding Distributions, Introduction to Testing Graph Properties, Imperfect gaps in Gap-ETH and PCPs, Zero knowledge and the chromatic number, Graphs and Algorithms in Communication Networks on Seven League Boots, Why greed works for shortest common superstring problem, On Khot’s unique games conjecture, A Characterization of Graphs with Fractional Total Chromatic Number Equal to, Priority algorithms for graph optimization problems, Interactive and probabilistic proof-checking, On the hardness of approximating max-satisfy, Clique is hard to approximate within \(n^{1-\epsilon}\), On Dinur’s proof of the PCP theorem, On weighted vs unweighted versions of combinatorial optimization problems, An Improved Dictatorship Test with Perfect Completeness
