Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions

Abstract

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in Rn { 1, 1}.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2011
Accession Number
ADA579443

Entities

People

  • Ilias Diakonikolas
  • Rocco A. Servedio
  • Ryan P. O'Donnell
  • Yi Wu

Organizations

  • Columbia University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Agreements
  • Algorithms
  • Artificial Intelligence
  • Coefficients
  • Computer Programming
  • Computer Science
  • Copyrights
  • Data Sets
  • Gaussian Distributions
  • Notation
  • Polynomials
  • Probability
  • Probability Distributions
  • Random Variables
  • Theorems
  • Theoretical Computer Science

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Nuclear and Radiation Engineering.