## Abstract

In a maximum-r-constraint satisfaction problem with variables {x_{1},x_{2},...,x_{n}}, we are given Boolean functions f_{1},f_{2},...,f_{m} each involving r of the n variables and are to find the maximum number of these functions that can be made true by a truth assignment to the variables. We show that for r fixed, there is an integer q ∈ O(log(1/ε)/ε^{4}) such that if we choose q variables (uniformly) at random, the answer to the sub-problem induced on the chosen variables is, with high probability, within an additive error of εq^{r} of q^{r}/n^{r} times the answer to the original n-variable problem. The previous best result for the case of r = 2 (which includes many graph problems) was that there is an algorithm which given the induced sub-problem on q = O(1/ε^{5}) variables, can find an approximation to the answer to the whole problem within additive error εn^{2}. For r ≥ 3, the conference version of this paper (in: Proceedings of the 34th ACM STOC, ACM, New York, 2002, pp. 232-239) and independently Andersson and Engebretsen give the first results with sample complexity q dependent only polynomially upon 1/ε. Their algorithm has a sample complexity q of O(1/ε^{7}). They (as also the earlier papers) however do not directly prove any relation between the answer to the sub-problem and the whole problem as we do here. Our method also differs from other results in that it is linear algebraic, rather than combinatorial in nature.

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

Pages (from-to) | 212-243 |

Number of pages | 32 |

Journal | Journal of Computer and System Sciences |

Volume | 67 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2003 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics