## Abstract

Assuming that NP ⊈ ∩_{ε > 0} BPTIME(2 ^{nε}), we show that graph min-bisection, dense fc-subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values.

Original language | English (US) |
---|---|

Pages (from-to) | 1025-1071 |

Number of pages | 47 |

Journal | SIAM Journal on Computing |

Volume | 36 |

Issue number | 4 |

DOIs | |

State | Published - 2006 |

## Keywords

- Approximation algorithms
- Hardness of approximation
- Probabilistically checkable proofs (PCPs)

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics