scientific article; zbMATH DE number 1256635

Publication date: 28 May 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

error-correcting codes complexity hierarchies hardness of approximations

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Annealed replication: A new heuristic for the maximum clique problem ⋮ A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems ⋮ The hardness of approximation: Gap location ⋮ A short note on the approximability of the maximum leaves spanning tree problem ⋮ Probabilistic proof systems — A survey ⋮ On the power of multi-prover interactive protocols ⋮ Theorems for a price: Tomorrow's semi-rigorous mathematical culture ⋮ The death of proof? Semi-rigorous mathematics? You've got to be kidding! ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Recent results in hardness of approximation ⋮ Some recent strong inapproximability results ⋮ A note on unique games ⋮ A note on PCP vs. MIP ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ The complexity of approximating a nonlinear program ⋮ ZK-PCPs from leakage-resilient secret sharing ⋮ MNP: A class of NP optimization problems ⋮ Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function ⋮ Ramsey theory and integrality gap for the independent set problem ⋮ Checking properties of polynomials ⋮ Approximating the independence number via the \(\vartheta\)-function ⋮ Simulating BPP using a general weak random source ⋮ Succinct classical verification of quantum computation ⋮ Improved non-approximability results for vertex cover with density constraints ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ The approximation of maximum subgraph problems ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ A branch and cut solver for the maximum stable set problem ⋮ Probabilistic verification of proofs in calculuses ⋮ Approximate solution of NP optimization problems ⋮ On approximating the longest path in a graph ⋮ MNP: A class of NP optimization problems ⋮ Statistical analysis of financial networks ⋮ A well-characterized approximation problem ⋮ The ideal membership problem and polynomial identity testing ⋮ Pseudo-Boolean optimization ⋮ Clique-detection models in computational biochemistry and genomics ⋮ Mining market data: a network approach ⋮ On maximum planar induced subgraphs ⋮ Approximate evaluations of characteristic polynomials of Boolean functions ⋮ Hardness and methods to solve CLIQUE ⋮ Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits ⋮ Boosting verifiable computation on encrypted data ⋮ Unnamed Item ⋮ Bounding queries in the analytic polynomial-time hierarchy ⋮ Integer programming as a framework for optimization and approximability ⋮ Zero knowledge and the chromatic number ⋮ Some APX-completeness results for cubic graphs ⋮ Derandomized graph products ⋮ Extracting randomness: A survey and new constructions ⋮ The inapproximability of non-NP-hard optimization problems. ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Bounded queries, approximations, and the Boolean hierarchy