Back to search

Georgia Institute of Technology

Intractability results for problems in computational learning and approximation

Abstract

dc:description.abstract

In this thesis we prove intractability results for well studied problems in computational learning and approximation. Let ε , mu > 0 be arbitrarily small constants and t be an arbitrary constant positive integer. We show an almost optimal hardness factor of d[superscript{1-ε}] for computing an equivalent DNF expression with minimum terms for a boolean function on d variables, given its truth table. In the study of weak learnability, we prove an optimal 1/2 + ε inapproximability for the accuracy of learning an intersection of two halfspaces with an intersection of t halfspaces. Further, we study the learnability of small DNF formulas, and prove optimal 1/2 + ε inapproximability for the accuracy of learning (i) a two term DNF by a t term DNF, and (ii) an AND under adversarial mu-noise by a t-CNF. In addition, we show a 1 - 2[superscript{-d}] + ε inapproximability for accurately learning parities (over GF(2)), under adversarial mu-noise, by degree d polynomials, where d is a constant positive integer. We also provide negative answers to the possibility of stronger semi-definite programming (SDP) relaxations yielding much better approximations for graph partitioning problems such as Maximum Cut and Sparsest Cut by constructing integrality gap examples for them. For Maximum Cut and Sparsest Cut we construct examples -- with gaps alpha[superscript{-1}] - ε (alpha is the Goemans-Williamson constant) and Omega((logloglog n)[superscript{1/13}]) respectively -- for the standard SDP relaxations augmented with O((logloglog n)[superscript{1/6}]) rounds of Sherali-Adams constraints. The construction for Sparsest Cut also implies that an n-point negative type metric may incur a distortion of Omega((logloglog n)[superscript{1/ 13}]) to embed into ell_1 even if the induced submetric on every subset of O((logloglog n)[superscript{1/6}]) points is isometric to ell_1. We also construct an integrality gap of Omega(loglog n) for the SDP relaxation for Uniform Sparsest Cut problem augmented with triangle inequalities, disproving a well known conjecture of Arora, Rao and Vazirani.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Saket, Rishi
Advisor dc:contributor.advisor
  • Khot, Subhash
Committee members dc:contributor.committeemember
  • Tetali, Prasad
  • Thomas, Robin
  • Vempala, Santosh
  • Vigoda, Eric

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/29681

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Saket, Rishi. Intractability results for problems in computational learning and approximation. Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29681