The Unique Games Conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work, we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem, known as L p Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points X = {α 1 , … , α m } ⊆ R n and a parameter k (possibly depending on n ). The goal is to find a subspace H of R n of dimension k that minimizes the ℓ p norm of the Euclidean distances to the points in X . For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p = ∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p ∈ (2, ∞), and for k = n − 1, it is NP-hard to approximate this problem to within a factor of γ p − ϵ for constant ϵ > 0, where γ p is the p th norm of a standard Gaussian random variable. This matches the γ p approximation algorithm obtained by Deshpande, Tulsiani, and Vishnoi who also showed the same hardness result under the UGC. The second problem we study is the related L p Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor, and Schechtman. Here, the input is a multilinear quadratic form ∑ n i , j = 1 a ij x i x j and the goal is to maximize the quadratic form over the ℓ p unit ball, namely, all x with ∑ n i = 1 | x i | p ⩽ 1. The problem is polynomial time solvable for p = 2. We show that for any constant p ∈ (2, ∞), it is NP-hard to approximate the quadratic form to within a factor of γ 2 p − ϵ for any ϵ > 0. The same hardness factor was shown under the UGC by Kindler et al. We also obtain a γ 2 p -approximation algorithm for the problem using the convex relaxation of the problem defined by Kindler et al. A γ 2 p approximation algorithm has also been independently obtained by Naor and Schechtman. These are the first approximation thresholds, proven under P ≠ NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves do not explicitly involve the Gaussian distribution.

Given a matrix A with n rows, a number k < n, and 0 < delta < 1, A is (k,delta)-RIP (Restricted Isometry Property) if, for any vector x in R^n, with at most k non-zero co-ordinates, (1-delta)|x|^2 <= |Ax|^2 <= (1+delta)|Ax|^2. In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large k and a small delta;. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. Specifically, we prove that for any arbitrarily large constant C>0 and any arbitrarily small constant 0<delta<1, there exists some k such that given a matrix M, it is SSE-Hard to distinguish the following two cases: i) (Highly RIP) M is (k,delta)-RIP; ii) (Far away from RIP) M is not (k/C,1-delta)-RIP. Most of the previous results on the topic of hardness of RIP certification only hold for certification when delta=o(1). In practice, it is of interest to understand the complexity of certifying a matrix with delta being close to sqrt(2) - 1, as it suffices for many real applications to have matrices with delta=sqrt(2)-1. Our hardness result holds for any constant delta. Specifically, our result proves that even if delta is indeed very small, i.e. the matrix is in fact strongly RIP, certifying that the matrix exhibits weak RIP itself is SSE-Hard. In order to prove the hardness result, we prove a variant of the Cheeger's Inequality for sparse vectors.

We introduce a novel privacy framework that we call Membership Privacy. The framework includes positive membership privacy, which prevents the adversary from significantly increasing its ability to conclude that an entity is in the input dataset, and negative membership privacy, which prevents leaking of non-membership. These notions are parameterized by a family of distributions that captures the adversary's prior knowledge. The power and flexibility of the proposed framework lies in the ability to choose different distribution families to instantiate membership privacy. Many privacy notions in the literature are equivalent to membership privacy with interesting distribution families, including differential privacy, differential identifiability, and differential privacy under sampling. Casting these notions into the framework leads to deeper understanding of the strengthes and weaknesses of these notions, as well as their relationships to each other. The framework also provides a principled approach to developing new privacy notions under which better utility can be achieved than what is possible under differential privacy.

We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovász relaxation. The Local Distribution LP is generally stronger than the Lovász relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovász relaxation gives a (2 − 2/k)-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2 − 2/k − ∊)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2 − 2/k − ∊)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem, known as the Lp Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points S = {a1, …, am} ⊆ ℝn and a parameter k (possibly depending on n). The goal is to find a subspace H of ℝn of dimension k that minimizes the ℓp norm of the Euclidean distances to the points in S. For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p = ∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p (2 < p < ∞), and for k = n − 1, it is NP-hard to approximate this problem to within a factor of γp − ∊ for constant ∊ > 0, where γp is the pth norm of a standard Gaussian random variable. This matches the γp approximation algorithm obtained by Deshpande, Tulsiani and Vishnoi [9] who also showed the same hardness result under the Unique Games Conjecture. The second problem we study is the related Lp Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman [24]. Here, the input is a multilinear quadratic form σni,j=1 aijxixj and the goal is to maximize the quadratic form over the ℓp unit ball, namely all x with σni=1 |xi|p = 1. The problem is polynomial time solvable for p = 2. We show that for any constant p (2 < p < ∞), it is NP-hard to approximate the quadratic form to within a factor of γ2p − ∊ for any ∊ > 0. The same hardness factor was shown under the UGC in [24]. We also obtain a γ2p-approximation algorithm for the problem using the convex relaxation of the problem defined by [24]. A γ2p approximation algorithm has also been independently obtained by Naor and Schechtman [27]. These are the first approximation thresholds, proven under P ≠ NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves have no mention of Gaussians.

Consider the problem of pricing n items under an unlimited supply with m buyers.Each buyer is interested in a bundle of at most k of the items.These buyers are single minded, which means each of them has a budget and they will either buy all the items if the total price is within their budget or they will buy none of the items.The goal is to price each item with profit margin p1, p2, ..., pn so as to maximize the overall profit.When k = 2, such a problem is called the graph-vertex-pricing problem.Another special case of the problem is the highway-pricing problem when the items (toll-booths) are arranged linearly on a line and each buyer (as a driver) is interested in paying for a path that consists of consecutive items.The goal again is to price the items (tolls) so as to maximize the total profits.There is an O(k)-approximation algorithm by [BB06] when the price on each item must be above its margin cost; i.e., pi > 0 for every i ∈ [n].As for the highway problem, a PTAS is shown in [GR11].We investigate the above problem when the seller is allowed to price some of the items below their margin cost.It is shown in [BB06, BBCH07] that by pricing some of the items below cost, the maximum profit can increase by a factor of Ω(log n).These items sold at low prices to stimulate other profitable sales are called "loss leaders".Given the possibility of making more profit, understanding the approximability of pricing loss leaders for graph-vertex-pricing, highway-pricing as well as the general item pricing problem are formulated as open problems in [BB06,BBCH07].In this paper, we obtain strong hardness of approximation result for the problem of pricing loss leaders.First we show that it is NP-hard to get better than O(log log log n)approximation when k ≥ 3.This improves a previous super-constant hardness result assuming the Unique Games Conjecture [Wu11].In addition, we show a super-constant Unique-Games hardness for the highway-pricing problem as well as the graph-vertex-pricing problem.

In 1997, Hastad showed NP-hardness of (1 - ε, 1/q + δ)-approximating Max-3Lin(Zq); however it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 - ε, δ)- approximating Max-3Lin(Z). In 2004, Khot-Kindler-Mossel-O'Donnell showed UG-hardness of (1 - ε, δ) approximating Max-2Lin(Zq) for q = q(ε, δ) a sufficiently large constant; however achieving the same hardness for Max-2Lin(Z) was given as an open problem in Raghavendra's 2009 thesis. In this work we show that fairly simple modifications to the proofs of the Max-3Lin(Zq) and Max-2Lin(Zq) results yield optimal hardness results over Z. In fact, we show a kind of "bicriteria" hardness: even when there is a (1 - ε) good solution over Z, it is hard for an algorithm to find a 5-good solution over Z, M, or Zmfor any m ≥ q(ε, δ) of the algorithm's choosing.

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 fnding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in ℝn × {– 1, 1}. We prove that for any constants d ≥ 1, ∊ > 0, Assuming the Unique Games Conjecture, no polynomial-time algorithm can fnd a degree-d PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {–1, 1}, even if there exists a degree-d PTF that is consistent with a 1 − ∊ fraction of the examples. It is NP-hard to fnd a degree-2 PTF that is consistent with a (1/2 + ∊) fraction of a given set of labeled examples in ℝn × {– 1, 1}, even if there exists a half-space (degree-1 PTF) that is consistent with a 1 − ∊ fraction of the examples. These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-d PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e. degree-1 PTFs) under arbitrary distributions.

... under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0. Our first main result shows that a recent pseudorandom generator construction of Meka and Zuckerman [MZ09], when suitably modified, can fool arbitrary functions of d halfspaces under product distributions where each coordinate has bounded fourth moment. To ǫ-fool any size-s, depth-d decision tree of halfspaces, our pseudorandom generator uses seed length O((dlog(ds/ǫ)+logn)·log(ds/ǫ)). For monotone functions of d halfspaces, the seed length can be improved to O((dlog(d/ǫ)+logn)·log(d/ǫ)). We get better bounds for larger ǫ; for example, to1/polylog(n)-foolallmonotonefunctionsof(logn)/loglognhalfspaces,ourgeneratorrequires a seed of length just O(logn). Our second main result generalizes the work of Diakonikolas et al. [DGJ + 09] to show that bounded independence suffices to fool functions of halfspaces under product distributions. Assuming each coordinatesatisfiesacertainstrongermoment condition, we showthat anyfunction computable by a size-s, depth-d decision tree of halfspaces is ǫ-fooled by Õ(d4 s 2 /ǫ 2)-wise independence. Our technical contributions include: a new multidimensional version of the classical Berry-Esseen theorem; a derandomization thereof; a generalization of Servedio [Ser07]’s regularity lemma for halfspaceswhichworksunderanyproduct distribution with bounded fourth moments; an extension of this regularity lemma to functions of many halfspaces; and, new analysis of the sandwiching polynomials technique of Bazzi [Baz09] for arbitrary product distributions.

We prove the following strong hardness result for learning: Given a distribution on labeled examples from the hypercube such that there exists a monomial (or conjunction) consistent with (1-¿)-fraction of the examples, it is NP-hard to find a halfspace that is correct on ( 1/2 + ¿)-fraction of the examples, for arbitrary constant ¿ > 0. In learning theory terms, weak agnostic learning of monomials by halfspaces is NP-hard. This hardness result bridges between and subsumes two previous results which showed similar hardness results for the proper learning of monomials and halfspaces. As immediate corollaries of our result, we give the first optimal hardness results for weak agnostic learning of decision lists and majorities. Our techniques are quite different from previous hardness proofs for learning. We use an invariance principle and sparse approximation of halfspaces from recent work on fooling halfspaces to give a new natural list decoding of a halfspace in the context of dictatorship tests/label cover reductions. In addition, unlike previous invariance principle based proofs which are only known to give Unique Games hardness, we give a reduction from a smooth version of Label Cover that is known to be NP-hard.

In the conclusion of his monumental paper on optimal inapproximability results, Håstad [13] suggested that Fourier analysis of Dictator (Long Code) Tests may not be universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of satisfiable 3-bit constraint satisfaction problems. In particular, he asked if the “Not Two” (NTW) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. Around the same time, Zwick [30] showed that all satisfiable 3-CSPs are 5/8-approximable and conjectured that the 5/8 is optimal. In this work we show that Fourier analysis techniques can produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness lower bound of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [30]. Our work precisely determines the 3-query “Dictatorship Testing gap”. Although this represents progress on Zwick's conjecture, current PCP “outer verifier” technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.

In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ naPCP1,s[O(log n),3]? In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-CSPs") is NP-hard. The previous best upper bound and lower bound for s are 20/27+µ by Khot and Saket [KS06], and 5/8 (assuming NP subseteq BPP) by Zwick [Zwi98]. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP naPCP1,5/8+ µ[O(log n),3] for any constant µ > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 ≤ c ≤ 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [1/2,1] -> [1/2,1] by GapSDP(c) = inf{s : (c, s) is an SDP gap}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] by determining the entire SDP gap curve; we show GapSDP(c) = S(c) for a certain explicit (but complicated to state) function S. In particular, our lower bound GapSDP(c) - S(c) is proved via a polynomial-time - RPR2' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR2 confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR2 algorithm can be guaranteed to find cuts of value larger than S(c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S(c) SDP gap, our RPR2 algorithm actually finds the optimal cut.) - Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P ≠ NP and the Unique Games Conjecture.

This paper presents a strategy for efficiently selecting informative data from large corpora of transcribed speech. We propose to choose data uniformly according to the distribution of some target speech unit (phoneme, word, character, etc). In our experiment, in contrast to the common belief that "there is no data like more data", we found it possible to select a highly informative subset of data that produces recognition performance comparable to a system that makes use of a much larger amount of data. At the same time, our selection process is efficient and fast.