## Abstract

Let X ⊆ R ^{n} and let C be a class of functions mapping ℝ ^{n} → {-1,1}. The famous VC-Theorem states that a random subset S of X of size O(d/ε ^{2} log d/ε, where d is the VC-Dimension of C, is (with constant probability) an ε-approximation for C with respect to the uniform distribution on X. In this work, we revisit the problem of constructing S explicitly. We show that for any X ⊆ ℝ ^{n} and any Boolean function class C that is uniformly approximated by degree k polynomials, an ε-approximation S can be be constructed deterministically in time poly(n ^{k},1/ε,|X|) provided that ε = Ω(W·√log|X|/|X|) where W is the weight of the approximating polynomial. Previous work due to Chazelle and Matousek suffers an d ^{O(d)} factor in the running time and results in superpolynomial-time algorithms, even in the case where k = O(1). We also give the first hardness result for this problem and show that the existence of a poly(n ^{k},|X|,1/ε)-time algorithm for deterministically constructing ε-approximations for circuits of size n ^{k} for every k would imply that P∈=∈BPP. This indicates that in order to construct explicit ε-approximations for a function class , we should not focus solely on 's VC-dimension. Our techniques use deterministic algorithms for discrepancy minimization to construct hard functions for Boolean function classes over arbitrary domains (in contrast to the usual results in pseudorandomness where the target distribution is uniform over the hypercube).

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

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings |

Pages | 495-504 |

Number of pages | 10 |

DOIs | |

State | Published - Aug 28 2012 |

Event | 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 - Cambridge, MA, United States Duration: Aug 15 2012 → Aug 17 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7408 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012 |
---|---|

Country/Territory | United States |

City | Cambridge, MA |

Period | 8/15/12 → 8/17/12 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)