Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs are used in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fit to match the data; typically, we seek a set of parameters that maximize the likelihood of the data. The algorithms used for this task either optimize over a limited family of DPPs, or else use local improvement heuristics that do not provide theoretical guarantees of optimality. It is natural to ask if there exist efficient algorithms for finding a maximum likelihood DPP model for a given data set. In seminal work on DPPs in Machine Learning, Kulesza conjectured in his PhD Thesis (2012) that the problem is NP-complete. In this work we prove Kulesza’s conjecture: we prove moreover, that even computing a $1-\frac{1}{\mathrm{poly} \log N}$-approximation to the maximum log-likelihood of a DPP on a set of $N$ items is NP-complete. At the same time, we also obtain the first polynomial-time algorithm obtaining a nontrivial worst-case approximation to the optimal likelihood: we present a polynomial-time $1/\log m$-approximation algorithm (for data sets of size $m$), which moreover obtains a $1-\frac{1}{\log N}$-approximation if all $N$ elements appear in a $O(1/N)$-fraction of the subsets. In terms of techniques, the hardness result reduces to solving a gap instance of a “vector coloring" problem on a hypergraph obtained from an adaptation of the constructions of Bogdanov, Obata and Trevisan (FOCS 2002), using the strong expanders of Alon and Capalbo (FOCS 2007).

We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT, 1988) as a variant of PAC learning, in which the algorithm has access to noisy examples and uncorrupted labels, and the goal is to recover an accurate hypothesis. Sloan (COLT, 1988) and Goldman and Sloan (Algorithmica, 1995) discovered information-theoretic limits to learning in this model, which have impeded further progress. In this article we extend the model to that of list learning, drawing inspiration from the list-decoding model in coding theory, and its recent variant studied in the context of learning. On the positive side, we show that sparse conjunctions can be efficiently list learned under some assumptions on the underlying ground-truth distribution. On the negative side, our results show that even in the list-learning model, efficient learning of parities and majorities is not possible regardless of the representation used.

Map search is a major vertical in all popular search engines. It also plays an important role in personal assistants on mobile, home or desktop devices. A significant fraction of map search traffic is comprised of “address queries” - queries where either the entire query or some terms in it refer to an address or part of an address (road segment, intersection etc.). Here we demonstrate that correctly understanding and tagging address queries are critical for map search engines to fulfill them. We describe several recurrent sequence architectures for tagging such queries. We compare their performance on two subcategories of address queries - single entity (aka single point) addresses and multi entity (aka multi point) addresses, and finish by providing guidance on the best practices when dealing with each of these subcategories.

AC^0 o MOD_2 circuits are AC^0 circuits augmented with a layer of parity gates just above the input layer. We study AC^0 o MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC^0 o MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an ~Omega(n^2) lower bound for the special case of depth-4 AC^0 o MOD_2. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions’ values at 0, given that their first d moments match.

A function f : Fn/2 → {0,1} is triangle-free if there are no x1, x2, x3 ∈ Fn/2 satisfying x1 + x2 + x3 --0 and f(x1) -- f(x2) -- f(x3) -- 1. In testing triangle freeness, the goal is to distinguish with high probability triangle-free functions from those which are ε-far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on ε (GAFA, 2005), however the best known upper bound is a tower type function of 1/ε. The best known lower bound on the query complexity of the canonical tester is 1/ε13.239 (Fu and Kleinberg, RANDOM, 2014).

We study Boolean functions with sparse Fourier spectrum or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x ⊕ y) - a fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix Mffor such functions is exactly the Fourier sparsity of f. Let d = deg2(f) be the F2-degree of f and DCC(f · ⊕) stand for the deterministic communication complexity for f(x ⊕ y). We show that 1) DCC(f · ⊕) = O(2d2/2logd-2 ∥f̂∥1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2) DCC(f · ⊕) = O(d∥f̂∥1) = O(√(rank(Mf))). This improves the (trivial) linear bound by nearly a quadratic factor. We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that the communication cost of our protocol is at most logO(1)rank(Mf). The above bounds are obtained from different analysis for the number of parity queries required to reduce f's F2-degree. Our bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity. Along the way we also prove several structural results about Boolean functions with small Fourier sparsity ∥f̂∥0or spectral norm ∥f̂∥1, which could be of independent interest. For functions f with constant F2-degree, we show that: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with ±-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; and 3) f depends only on polylog∥f̂∥1linear functions of input variables. For functions f with small spectral norm, we show that: 1) there is an affine subspace of co dimension ∥f̂∥1on which f(x) is a constant, and 2) there is a parity decision ∥f̂∥1log∥f̂∥0for computing f.

Recently Rubinfeld et al. (ICS 2011, pp. 223–238) proposed a new model of sublinear algorithms called local computation algorithms. In this model, a computation problem F may have more than one legal solution and each of them consists of many bits. The local computation algorithm for F should answer in an online fashion, for any index i, the ith bit of some legal solution of F. Further, all the answers given by the algorithm should be consistent with at least one solution of F. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.

Let be three Boolean functions. We say a triple (x, y, x + y) is a triangle in the function-triple (f1, f2, f3) if f1(x) = f2(y) = f3(x + y) = 1. (f1, f2, f3) is said to be triangle-free if there is no triangle in the triple. The distance between a function-triple and triangle-freeness is the minimum fraction of function values one needs to modify in order to make the function-triple triangle-free. A canonical tester for triangle-freeness repeatedly picks x and y uniformly and independently at random and checks if f1(x) = f2(y) = f3(x + y) = 1. Based on an algebraic regularity lemma, Green showed that the number of queries for the canonical testing algorithm is upper-bounded by a tower of 2's whose height is polynomial in 1/ε. A trivial query complexity lower bound of Ω(1/ε) is straightforward to show. In this paper, we give the first non-trivial query complexity lower bound for testing triangle-freeness in Boolean functions. We show that, for every small enough e there exists an integer n0(ε) such that for all n ≥ n0 there exists a function-triple depending on all the n variables which is ε-far from being triangle-free and requires queries for the canonical tester. For the single function case that f1 = f2 = f3, we obtain a weaker lower bound of . We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square-root of the query complexity of the corresponding canonical tester. Consequently, this yields and query complexity lower bounds for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers.

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549–595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $\textsc{rej}(\epsilon)$ were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781–1795]. They used Fourier analysis to show that $\textsc{rej}(\epsilon)\geq\epsilon$ for every $0\leq\epsilon\leq1/2$. They also conjectured that this bound might not be tight for $\epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $\textsc{rej}(\epsilon)\geq\epsilon$ by an additive constant that depends only on $\epsilon$: $\textsc{rej}(\epsilon)\geq\epsilon+\min\{1376\epsilon^{3}(1-2\epsilon)^{12},\frac{1}{4}\epsilon(1-2\epsilon)^{4}\}$, for every $0\leq\epsilon\leq1/2$. Our analysis is based on a relationship between $\textsc{rej}(\epsilon)$ and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test due to Green for {}``triangle freeness'': A function $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies this property if $f(x),f(y),f(x+y)$ do not all equal $1$, for any pair $x,y\in\mathbb{F}_{2}^{n}$. Here we extend this test to a more systematic study of testing for linear-invariant non-linear properties. We consider properties that are described by a single forbidden pattern (and its linear transformations), i.e., a property is given by $k$ points $v_{1},\ldots,v_{k}\in\mathbb{F}_{2}^{k}$ and $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies the property that if for all linear maps $L:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{n}$ it is the case that $f(L(v_{1})),\ldots,f(L(v_{k}))$ do not all equal $1$. We show that this property is testable if the underlying matroid specified by $v_{1},\ldots,v_{k}$ is a graphic matroid. This extends Green's result to an infinite class of new properties. Our techniques extend those of Green and in particular we establish a link between the notion of {}``1-complexity linear systems'' of Green and Tao, and graphic matroids, to derive the results.

In this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.