Title: Intractability Results for Problems in Computational Learning and Approximation
| Time: | Tuesday, June 16, 3:00pm |
| Location: | Klaus Conference Room 2100 |
| Advisor: | Dr. Subash Knot, College of Computing |
| Committee: | Dr. Santosh Vempala, College of Computing |
| Dr. Robin Thomas, School of Mathematics | |
| Dr. Prasad Tetali, School of Mathematics | |
| Dr. Eric Vigoda, College of Computing | |
| Reader: | Dr. Santosh Vempala, College of Computing |
Abstract:
In this thesis we prove intractability results for some well studied problems in computational learning and combinatorial optimization.
Minimizing and Learning DNF Expressions: We study the problem of finding the minimum size DNF formula for a boolean function f on the d-dimensional boolean hypercube {0,1}^d given its truth table. We show that unless NP is contained in quasipolynomial time, there is no polynomial time algorithm that approximates this problem to within factor d^{1-eps} where eps> 0 is an arbitrarily small constant. Our result essentially matches the known O(d) approximation for the problem.
We also study the learnability of small size DNF formulas. We show that assuming NP is not equal to RP, for arbitrarily small constant eps> 0 and any fixed positive integer t, a two term DNF cannot be PAC-learnt in polynomial time by a t term DNF to within 1/2 + eps accuracy. Under the same complexity assumption, we show that for arbitrarily small constants mu, eps> 0 and any fixed positive integer t, an AND function (i.e. a single term DNF) cannot be PAC-learnt in polynomial time under adversarial mu-noise (also known as agnostic learning) by a t-CNF to within 1/2 + eps accuracy. Our results improve upon the previously known hardness for these problems by Alekhnovich etal., Feldman and Feldman etal.
Learning Intersection of Two Halfspaces: We show that unless NP = RP, it is hard to PAC-learn intersection of two halfspaces in R^n using a hypothesis which is a function of up to l linear threshold functions for any integer l to within accuracy of 1/2 + eps for any constant eps> 0. Specifically, we show that for every integer l and an arbitrarily small constant eps> 0, unless NP = RP, no polynomial time algorithm can distinguish whether there is an intersection of two halfspaces that correctly classifies a given set of labeled points in R^n, or whether any function of l linear threshold functions can correctly classify at most 1/2 + eps fraction of the points. Our result is optimal up to an arbitrarily small constant eps> 0, and improves upon the previous NP-hardness for this problem by Alekhnovich etal.
Reconstructing Multivariate Polynomials over F[2]: We study the polynomial reconstruction problem for low-degree multivariate polynomials over F[2]. In this problem, we are given a set of points x_i in F[2]^n and target values zeta_i in F[2] for each of these points, with the strong promise promise that there is a linear polynomial over F[2] that agrees with at least 1 - eps fraction of the point-value pairs. Our goal is to find a degree d polynomial that has good agreement with the set of point-value pairs. We show that it is NP-hard to find a polynomial that agrees with more than 1 - 2^{-d} + delta fraction of the pairs for any constants eps, delta>0 and positive integer d. This extends the previously known hardness of approximation (or even NP-completeness) for the case when d = 1, which follows from a celebrated result of Hastad. In the setting of Computational Learning, our result shows the hardness of agnostic learning of parities, where the learner is allowed a low-degree polynomial over F[2] as a hypothesis.
SDP Integrality Gaps with Local ell_1-Embeddability: We construct integrality gap instances for SDP relaxation of the Maximum Cut and the Sparsest Cut problems. If the triangle inequality constraints are added to the SDP, then the SDP vectors naturally define an n-point negative type metric where n is the number of vertices in the problem instance. Our gap-instances satisfy a stronger constraint that every sub-metric on t = O((log log log n)^{1/6}) points is isometrically embeddable into ell_1. The local ell_1-embeddability constraints are implied when the basic SDP relaxation is augmented with t rounds of the Sherali-Adams LP-relaxation.
For the Maximum Cut problem, we obtain an optimal gap of alpha_{GW}^{-1} - eps, where alpha_{GW} is the Goemans-Williamson constant and eps> 0 is an arbitrarily small constant. For the Sparsest Cut problem, we obtain a gap of Omega((log log log n)^{1/13}). The latter result can be rephrased as a construction of an n-point negative type metric such that every t-point sub-metric is isometrically ell_1-embeddable, but embedding the whole metric into ell_1 incurs distortion Omega((log log log n)^{1/13}).
Integrality Gap for Uniform Sparsest Cut: Arora, Rao and Vazirani showed that the standard semi-definite programming relaxation of the Uniform Sparsest Cut problem with the triangle inequality constraints has an integrality gap of O(sqrt{log n}). They conjectured that the gap is bounded from above by a constant. In this study, we disprove this conjecture (referred to as the ARV-Conjecture) by constructing an Omega(log log n) integrality gap instance. Khot and Vishnoi had earlier disproved the non-uniform version of the ARV-Conjecture.
<
Full-Text Page >