Boosting and Hard-Core Sets

This paper connects two fundamental ideas from theoretical computer science hard-core set construction, a type of hardness amplification from computational complexity, and boosting, a technique from computational learning theory. Using this connection we give fruitful applications of complexity-theoretic techniques to learning theory and vice versa. We show that the hard-core set construction of R. Impagliazzo (1995), which establishes the existence of distributions under which boolean functions are highly inapproximable, may be viewed as a boosting algorithm. Using alternate boosting methods we give an improved bound for hard-core set construction which matches known lower bounds from boosting and thus is optimal within this class of techniques. We then show how to apply techniques from R. Impagliazzo to give a new version of Jackson's celebrated Harmonic Sieve algorithm for learning DNF formulae under the uniform distribution using membership queries. Our new version has a significant asymptotic improvement in running time. Critical to our arguments is a careful analysis of the distributions which are employed in both boosting and hard-core set constructions.

Authors

• Adam R. Klivans
• Rocco A. Servedio

Keywords

• Boosting
• Read only memory
• Circuits
• Boolean functions
• Computer science
• Mathematics
• Application software
• Marine vehicles
• Uniform Distribution
• Running Time
• Fundamental Idea
• Computational Theory
• Boolean Function
• Theoretical Computer Science
• Learning Models
• Learning Algorithms
• Size Parameters
• Original Algorithm
• Strong Learning
• Weak Learners
• Final Hypothesis
• Input Fractions
• Concept Of Class
• Learning Cost
• Polynomial Number
• Complexity Hypothesis