Search

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two $k$-subsets; when viewed as linear queries, comparison queries are $2k$-sparse and have only $\{-1,0,1\}$ coefficients. We give similar constructions for sorting sumsets $A+B$ and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms. Our constructions are based on the notion of "inference dimension", recently introduced by the authors in the context of active classification with comparison queries. This can be viewed as another contribution to the fruitful link between machine learning and discrete geometry, which goes back to the discovery of the VC dimension., 18 paged, 1 figure

We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and parameters $0< \epsilon, \delta

We examine a new variant of the classic prisoners and light switches puzzle: A warden leads his $n$ prisoners in and out of $r$ rooms, one at a time, in some order, with each prisoner eventually visiting every room an arbitrarily large number of times. The rooms are indistinguishable, except that each one has $s$ light switches; the prisoners win their freedom if at some point a prisoner can correctly declare that each prisoner has been in every room at least once. What is the minimum number of switches per room, $s$, such that the prisoners can manage this? We show that if the prisoners do not know the switches' starting configuration, then they have no chance of escape—but if the prisoners do know the starting configuration, then the minimum sufficient $s$ is surprisingly small. The analysis gives rise to a number of puzzling open questions, as well.

Let $V$ be any vector space of multivariate degree-$d$ homogeneous polynomials with co-dimension at most $k$, and $S$ be the set of points where all polynomials in $V$ {\em nearly} vanish. We establish a qualitatively optimal upper bound on the size of $\epsilon$-covers for $S$, in the $\ell_2$-norm. Roughly speaking, we show that there exists an $\epsilon$-cover for $S$ of cardinality $M = (k/\epsilon)^{O_d(k^{1/d})}$. Our result is constructive yielding an algorithm to compute such an $\epsilon$-cover that runs in time $\mathrm{poly}(M)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models with hidden variables. These include density and parameter estimation for $k$-mixtures of spherical Gaussians (with known common covariance), PAC learning one-hidden-layer ReLU networks with $k$ hidden units (under the Gaussian distribution), density and parameter estimation for $k$-mixtures of linear regressions (with Gaussian covariates), and parameter estimation for $k$-mixtures of hyperplanes. Our algorithms run in time {\em quasi-polynomial} in the parameter $k$. Previous algorithms for these problems had running times exponential in $k^{\Omega(1)}$. At a high-level our algorithms for all these learning problems work as follows: By computing the low-degree moments of the hidden parameters, we are able to find a vector space of polynomials that nearly vanish on the unknown parameters. Our structural result allows us to compute a quasi-polynomial sized cover for the set of hidden parameters, which we exploit in our learning algorithms., Comment: Full version of FOCS'20 paper

We construct sets A and B in a vector space over $$\mathbb{F}$$ with the property that A is “statistically” almost closed under addition by B in the sense that a + b almost always lies in A when a ∈ A and b ∈ B, but which is extremely far from being “combinatorially” almost closed under addition by B: if A′⊂ A, B′⊂ B and A′ + B′ is comparable in size to A′, then |B′| ⪅ |B|1/2.

We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in logspace that have been considered in the literature, including halfspaces (over general domains), modular tests and combinatorial shapes. For all these classes, our generator is the first that achieves near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize RL - a central question in complexity theory. Our construction combines ideas from a large body of prior work, ranging from a classical construction of [NN93] to the recent gradually increasing independence paradigm of [KMN11, CRSW13, GMRTV12], while also introducing some novel analytic machinery which might find other applications.

Given a finite set $X\subset \mathbb{R}^{d}$ and a binary linear classifier $c:\mathbb{R}^{d}\rightarrow\{0,1\}$ , how many queries of the form $c(x)$ are required to learn the label of every point in $X$ ? Known as point location, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth $\tilde{O}(d\log(\vert X\vert))$ , improving on the previous best of $\tilde{O}(\overline{d}^{2}\log(\vert X\vert))$ from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, building on the work of Carlen, Lieb, and Loss (J. Geometric Analysis 2004), as well as Dvir, Saraf, and Wigderson (STOC 2014), we prove a novel characterization of Barthe's Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that $X$ may be transformed into approximate isotropic position if and only if there exists no $k$ -dimensional subspace with more than a $k/d$ -fraction of $X$ , and provide a similar characterization for exact isotropic position. The below is an extended abstract. The full work can be found at https://arxiv.org/abs/2004.11380

The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in l2-norm, then f is close to g in l1-distance. Notably, our bound relating the two distances is independent of the dimension. That is, we show that Boolean degree-d PTFs are robustly identifiable from their degree-d Chow parameters. No non-trivial bound was previously known for d >1. Our robust identifiability result gives the following algorithmic applications: First, we show that Boolean degree-d PTFs can be efficiently approximately reconstructed from approximations to their degree-d Chow parameters. This immediately implies that degree-d PTFs are efficiently learnable in the uniform distribution d-RFA model. As a byproduct of our approach, we also obtain the first low integer-weight approximations of degree-d PTFs, for d>1. As our second application, our robust identifiability result gives the first efficient algorithm, with dimension-independent error guarantees, for malicious learning of Boolean degree-d PTFs under the uniform distribution. The proof of our robust identifiability result involves several new technical ingredients, including the following structural result for degree-d multivariate polynomials with very poor anti-concentration: If p is a degree-d polynomial where p(x) is very close to 0 on a large number of points in { ± 1 }n, then there exists a degree-d hypersurface that exactly passes though almost all of these points. We leverage this structural result to show that if the degree-d Chow distance between f and g is small, then we can find many degree-d polynomials that vanish on their disagreement region, and in particular enough that forces the l1-distance between f and g to also be small. To implement this proof strategy, we require additional technical ideas. In particular, in the d=2 case we show that for any large vector space of degree-2 polynomials with a large number of common zeroes, there exists a linear function that vanishes on almost all of these zeroes. The degree-d degree generalization of this statement is significantly more complex, and can be viewed as an effective version of Hilbert’s Basis Theorem for our setting.

Consider any Boolean function $$F(X_1,\ldots ,X_N)$$F(X1,ź,XN) that has more than $$2^{-N^{\delta }}\cdot 2^N$$2-Nź·2N satisfying assignments for some $$\delta $$ź, $$0 0$$d>0. Then how many variables do we need to fix in order to satisfy F? We show that one can always find some "short" partial assignment on which F evaluates to 1 by fixing at most $$\alpha N$$źN variables for some constant $$\alpha

Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al. [Maximally recoverable codes for grid-like topologies, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 2092-2108] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it. Consider a labeling of the edges of the complete bipartite graph Kn, n, with labels coming from Fd2 that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in n × n grid topologies. Prior to the current work, it was known that d is between (log n)2 and n log n. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group.

A natural number is a binary k’ th power if its binary representation consists of k consecutive identical blocks. We prove, using tools from combinatorics, linear algebra, and number theory, an analogue of Waring’s theorem for sums of binary k’th powers. More precisely, we show that for each integer k> 2, there exists an effectively computable natural number n such that every sufficiently large multiple of Ek:=gcd(2k - 1,k) is the sum of at most n binary k’th powers. (The hypothesis of being a multiple of Ek cannot be omitted, since we show that the gcd of the binary k’th powers is Ek.) Furthermore, we show that n = 2O(k3). Analogous results hold for arbitrary integer bases b>2.

We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X, Y, Z) on domain $[\ell_{1}]\times[\ell_{2}]\times[n]$ , we want to distinguish, with probability at least 2/3, between the case that $X$ and $Y$ are conditionally independent given $Z$ from the case that (X,\ Y,\ Z) is ɛ-far, in l 1 -distance, from every distribution that has this property. Conditional independence is a concept of central importance in probability and statistics with a range of applications in various scientific domains. As such, the statistical task of testing conditional independence has been extensively studied in various forms within the statistics and econometrics communities for nearly a century. Perhaps surprisingly, this problem has not been previously considered in the framework of distribution property testing and in particular no tester with sublinear sample complexity is known, even for the important special case that the domains of X and Y are binary. The main algorithmic result of this work is the first conditional independence tester with sublinear sample complexity for discrete distributions over $[\ell_{1}]\times[ell_{2}]\times[n]$ . To complement our upper bounds, we prove information-theoretic lower bounds establishing that the sample complexity of our algorithm is optimal, up to constant factors, for a number of settings. Specifically, for the prototypical setting when l 1 ,l 2 =O(1), we show that the sample complexity of testing conditional independence (upper bound and matching lower bound) is \begin{equation*} \Theta(\max(n^{1/2}/\varepsilon^{2},\min(n^{7/8}/varepsilon,n^{6/7}/\varepsilon^{8/7}))) \end{equation*} To obtain our tester, we employ a variety of tools, including (1) a suitable weighted adaptation of the flattening technique [DK16], and (2) the design and analysis of an optimal (unbiased) estimator for the following statistical problem of independent interest: Given a degree -d polynomial Q:Rn→R and sample access to a distribution $p$ over [n], estimate Q(p_{1}, …, p_{n}) up to small additive error. Obtaining tight variance analyses for specific estimators of this form has been a major technical hurdle in distribution testing (see, e.g., [CDVV14]). As an important contribution of this work, we develop a general theory providing tight variance bounds for all such estimators. Our lower bounds, established using the mutual information method, rely on novel constructions of hard instances that may be useful in other settings.

We present an algebraic method to study four-dimensional toric varieties by lifting matrix equations from the special linear group ${\rm SL}_2({\mathbb Z})$ to its preimage in the universal cover of ${\rm SL}_2({\mathbb R})$. With this method we recover the classification of two-dimensional toric fans, and obtain a description of their semitoric analogue. As an application to symplectic geometry of Hamiltonian systems, we give a concise proof of the connectivity of the moduli space of toric integrable systems in dimension four, recovering a known result, and extend it to the case of semitoric integrable systems with a fixed number of focus-focus points and which are in the same twisting index class. In particular, we show that any semitoric system with precisely one focus-focus singular point can be continuously deformed into a system in the same isomorphism class as the Jaynes-Cummings model from optics.

Canonical Projective Embeddings of the Deligne-Lusztig Curves Associated to 2 A 2 , 2 B 2 and 2 G 2 Daniel M. Kane May 15, 2015 Abstract The Deligne-Lusztig varieties associated to the Coxeter classes of the algebraic groups 2 A 2 , 2 B 2 and 2 G 2 are affine algebraic curves. We produce explicit projective models of the closures of these curves. Furthermore for d the Coxeter number of these groups, we find polynomials for each of these models that cut out the F q -points, the F q d -points and the F q d+1 - points, and demonstrate a relation satisfied by these polynomials. Introduction There are four kinds of finite groups of Lie type of rank 1. The associated Deligne-Lusztig varieties for the Coxeter classes of these groups all give affine algebraic curves. The completions of these curves have several applications in- cluding the representation theory of the associated group ([1, 5]), coding theory ([4]) and the construction of potentially interesting covers of P 1 ([3]). In this paper, we consider these curves associated to the groups G = 2 A 2 , 2 B 2 and 2 G 2 . The remaining curve is associated to G = A 1 and is P 1 , but we do not cover this case as it is easy and doesn’t follow many of the patterns found in the analysis of the other three cases. For each of these curves, we explicitly construct an embedding C ,→ P(W ) where W is a representation of G of dimension 3,5, or 14 respectively, and provide an explicit system of equations cutting out C. The curve associated to 2 A 2 is the Fermat curve. The curve associated to B 2 is also well-known though not immediately isomorphic to our embedding. Embeddings of the curve associated to 2 G 2 were not known until recently. In [6], they constructed an explicit curve with the correct genus, symmetry group and number of points. Later, in [2], Eid and Duursma use this description to independently arrive at the embedding we produce in this paper. ∗ University of California, San Diego, Department of Mathematics / Department of Computer Science and Engineering, 9500 Gilman Drive #0404, La Jolla, CA 92093 dakane@ucsd.edu

© 2015 American Mathematical Society. We prove the existence of designs of small size in a number of contexts. In particular our techniques can be applied to prove the existence of n-designs on Sd of size O d (nd logd−1(n)).

We consider the problem of robust polynomial regression, where one receives samples $(x_i, y_i)$ that are usually within $\sigma$ of a polynomial $y = p(x)$, but have a $\rho$ chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate $p$ only when $\rho < \frac{1}{\log d}$. We give an algorithm that works for the entire feasible range of $\rho < 1/2$, while simultaneously improving other parameters of the problem. We complement our algorithm, which gives a factor 2 approximation, with impossibility results that show, for example, that a $1.09$ approximation is impossible even with infinitely many samples., Comment: 19 Pages. To appear in FOCS 2017

A polynomial threshold function (PTF) of degree d is a boolean function of the form f=sgn(p), where p is a degree-d polynomial, and sgn is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is not close to a constant function, where a boolean function g is called δ-close to constant if, for some ve{1,-1}, we have g(x)=v for all but at most δ fraction of inputs. We show for every PTF f of degree d≥ 1, and parameters 0r≤ 1/16, that Pr∾ Rr [fρ is not δ-close to constant] ≤ √ #183;(logr-1· logδ-1)O(d2), where ρ ∾ Rr is a random restriction leaving each variable, independently, free with probability r, and otherwise assigning it 1 or -1 uniformly at random. In fact, we show a more general result for random block restrictions: given an arbitrary partitioning of input variables into m blocks, a random block restriction picks a uniformly random block lE [m] and assigns 1 or -1, uniformly at random, to all variable outside the chosen block l. We prove the Block Restriction Lemma saying that a PTF f of degree d becomes δ-close to constant when hit with a random block restriction, except with probability at most m-1/2 #183; (logm#183; logδ-1)O(d2). As an application of our Restriction Lemma, we prove lower bounds against constant-depth circuits with PTF gates of any degree 1≤ d≪ √logn/loglogn, generalizing the recent bounds against constant-depth circuits with linear threshold gates (LTF gates) proved by Kane and Williams (STOC, 2016) and Chen, Santhanam, and Srinivasan (CCC, 2016). In particular, we show that there is an n-variate boolean function Fn E P such that every depth-2 circuit with PTF gates of degree d≥ 1 that computes Fn must have at least (n3/2+1/d)#183; (logn)-O(d2) wires. For constant depths greater than 2, we also show average-case lower bounds for such circuits with super-linear number of wires. These are the first super-linear bounds on the number of wires for circuits with PTF gates. We also give short proofs of the optimal-exponent average sensitivity bound for degree-d PTFs due to Kane (Computational Complexity, 2014), and the Littlewood-Offord type anticoncentration bound for degree-d multilinear polynomials due to Meka, Nguyen, and Vu (Theory of Computing, 2016). Finally, we give derandomized versions of our Block Restriction Lemma and Littlewood-Offord type anticoncentration bounds, using a pseudorandom generator for PTFs due to Meka and Zuckerman (SICOMP, 2013).

Let $X$ be a finite collection of sets (or "clusters"). We consider the problem of counting the number of ways a cluster $A \in X$ can be partitioned into two disjoint clusters $A_1, A_2 \in X$, thus $A = A_1 \uplus A_2$ is the disjoint union of $A_1$ and $A_2$; this problem arises in the run time analysis of the ASTRAL algorithm in phylogenetic reconstruction. We obtain the bound$$ | \{ (A_1,A_2,A) \in X \times X \times X: A = A_1 \uplus A_2 \} | \leq |X|^{3/p} $$where $|X|$ denotes the cardinality of $X$, and $p := \log_3 \frac{27}{4} = 1.73814\dots$, so that $\frac{3}{p} = 1.72598\dots$. Furthermore, the exponent $p$ cannot be replaced by any larger quantity. This improves upon the trivial bound of $|X|^2$. The argument relies on establishing a one-dimensional convolution inequality that can be established by elementary calculus combined with some numerical verification.In a similar vein, we show that for any subset $A$ of a discrete cube $\{0,1\}^n$, the additive energy of $A$ (the number of quadruples $(a_1,a_2,a_3,a_4)$ in $A^4$ with $a_1+a_2=a_3+a_4$) is at most $|A|^{\log_2 6}$, and that this exponent is best possible.

We prove a structural result for degree-$d$ polynomials. In particular, we show that any degree-$d$ polynomial, $p$ can be approximated by another polynomial, $p_{0}$, which can be decomposed as some function of polynomials $q_{1},\ldots,q_{m}$ with $q_{i}$ normalized and $m=O_{d}(1)$, so that if $X$ is a Gaussian random variable, the probability distribution on $(q_{1}(X),\ldots,q_{m}(X))$ does not have too much mass in any small box. ¶ Using this result, we prove improved versions of a number of results about polynomial threshold functions, including producing better pseudorandom generators, obtaining a better invariance principle, and proving improved bounds on noise sensitivity.

We prove new bounds on the average sensitivity of polynomial threshold functions. In particular, we show that for f, a degree-d polynomial threshold function in n variables that $$\mathbb{AS}(f) \leq \sqrt{n}(\log(n))^{O(d log(d))}2^{O(d^2 log(d))}.$$ AS ( f ) ≤ n ( log ( n ) ) O ( d l o g ( d ) ) 2 O ( d 2 l o g ( d ) ) . This bound amounts to a significant improvement over previous bounds, and in particular, for fixed d gives the same asymptotic exponent of n as the one predicted by the Gotsman---Linial Conjecture.

Swinnerton-Dyer considered the proportion of twists of an elliptic curve with full [math] -torsion that have [math] -Selmer group of a particular dimension. Swinnerton-Dyer obtained asymptotic results on the number of such twists using an unusual notion of asymptotic density. We build on this work to obtain similar results on the density of twists with particular rank of [math] -Selmer group using the natural notion of density.

We study the problem of list-decodable (robust) Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. In the former problem, we are given a set T of points in n with the promise that an α-fraction of points in T, where 0G, and no assumptions are made about the remaining points. The goal is to output a small list of candidate vectors with the guarantee that at least one of the candidates is close to the mean of G. In the latter problem, we are given samples from a k-mixture of spherical Gaussians on n and the goal is to estimate the unknown model parameters up to small accuracy. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. Specifically, our main contributions are as follows: List-Decodable Mean Estimation. Fix any d ∈ + and 0Od ((nd/α)) and runtime Od ((n/α)d) that outputs a list of O(1/α) many candidate vectors such that with high probability one of the candidates is within l2-distance Od(α−1/(2d)) from the mean of G. The only previous algorithm for this problem achieved error O(α−1/2) under second moment conditions. For d = O(1/), where >0 is a constant, our algorithm runs in polynomial time and achieves error O(α). For d = Θ(log(1/α)), our algorithm runs in time (n/α)O(log(1/α)) and achieves error O(log3/2(1/α)), almost matching the information-theoretically optimal bound of Θ(log1/2(1/α)) that we establish. We also give a Statistical Query (SQ) lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. Learning Mixtures of Spherical Gaussians. We give a learning algorithm for mixtures of spherical Gaussians, with unknown spherical covariances, that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform k-mixture of identity covariance Gaussians we obtain the following: For any >0, if the pairwise separation between the means is at least Ω(k+√log(1/δ)), our algorithm learns the unknown parameters within accuracy δ with sample complexity and running time (n, 1/δ, (k/)1/). Moreover, our algorithm is robust to a small dimension-independent fraction of corrupted data. The previously best known polynomial time algorithm required separation at least k1/4 (k/δ). Finally, our algorithm works under separation of O(log3/2(k)+√log(1/δ)) with sample complexity and running time (n, 1/δ, klogk). This bound is close to the information-theoretically minimum separation of Ω(√logk). Our main technical contribution is a new technique, using degree-d multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.

We present a family a monotone functions fd :f0; 1g n !f0; 1g so that fd can be computed as a depth-d decision tree and so that fd disagrees with any k-junta on a constant fraction of inputs for any k = exp(o( p d)). This gives a negative answer to a problem

We study problems in distribution property testing: Given sample access to one or more unknown discrete distributions, we want to determine whether they have some global property or are epsilon-far from having the property inL1 distance (equivalently, total variation distance, or “statistical distance”). In this work, we give a novel general approach for distribution testing. We describe two techniques: our first technique gives sample–optimal testers, while our second technique gives matching sample lower bounds. As a consequence, we resolve the sample complexity of a wide variety of testing problems. Our upper bounds are obtained via a modular reduction based approach. Our approach yields optimal testers for numerous problems by using a standard L2-identity tester asa black-box. Using this recipe, we obtain simple estimators for a wide range of problems, encompassing many problems previously studied in the TCS literature, namely: (1) identity testing to a fixed distribution, (2) closeness testing between two unknown distributions (with equal/unequal sample sizes),(3) independence testing (in any number of dimensions), (4) closeness testing for collections of distributions, and (5) testing histograms. For all of these problems, our testers are sampleoptimal, up to constant factors. With the exception of (1),ours are the first sample-optimal testers for the corresponding problems. Moreover, our estimators are significantly simpler to state and analyze compared to previous results.As an important application of our reduction-based technique, we obtain the first adaptive algorithm for testing equivalence between two unknown distributions. The sample complexity of our algorithm depends on the structure of the unknown distributions – as opposed to merely their domain size– and is significantly better compared to the worst-case optimal L1-tester in many natural instances. Moreover, our technique naturally generalizes to other metrics beyond the L1-distance. As an illustration of its flexibility, we use it to obtain the first near-optimal equivalence tester under the Hellinger distance.Our lower bounds are obtained via a direct information theoretic approach: Given a candidate hard instance, our proof proceeds by bounding the mutual information between appropriate random variables. While this is a classical method in information theory, prior to our work, it had not been used in this context. Previous lower bounds relied either on the birthday paradox, or on moment-matching and were thus restricted to symmetric properties. Our lower bound approach does not suffer from any such restrictions and gives tight sample lower bounds for the aforementioned problems.

We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the problems of (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown Gaussian distribution. For each of these problems, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the computational complexity of {\em any} Statistical Query algorithm for the problem. Our SQ lower bound for Problem (1) is qualitatively matched by known learning algorithms for GMMs. Our lower bound for Problem (2) implies that the accuracy of the robust learning algorithm in~\cite{DiakonikolasKKLMS16} is essentially best possible among all polynomial-time SQ algorithms. Our SQ lower bounds are attained via a unified moment-matching technique that is useful in other contexts and may be of broader interest. Our technique yields nearly-tight lower bounds for a number of related unsupervised estimation problems. Specifically, for the problems of (3) robust covariance estimation in spectral norm, and (4) robust sparse mean estimation, we establish a quadratic {\em statistical--computational tradeoff} for SQ algorithms, matching known upper bounds. Finally, our technique can be used to obtain tight sample complexity lower bounds for high-dimensional {\em testing} problems. Specifically, for the classical problem of robustly {\em testing} an unknown mean (known covariance) Gaussian, our technique implies an information-theoretic sample lower bound that scales {\em linearly} in the dimension. Our sample lower bound matches the sample complexity of the corresponding robust {\em learning} problem and separates the sample complexity of robust testing from standard (non-robust) testing., Changes from v1: Revised presentation. Added more applications of the technique (SQ lower bounds for robust sparse mean estimation and robust covariance estimation in spectral norm). Sharpened testing lower bound to linear in the dimension (compared to nearly-linear in first version)

A symplectic semitoric manifold is a symplectic $4$-manifold endowed with a Hamiltonian $(S^1 \times \mathbb{R})$-action satisfying certain conditions. The goal of this paper is to construct a new symplectic invariant of symplectic semitoric manifolds, the helix, and give applications. The helix is a symplectic analogue of the fan of a nonsingular complete toric variety in algebraic geometry, that takes into account the effects of the monodromy near focus-focus singularities. We give two applications of the helix: first, we use it to give a classification of the minimal models of symplectic semitoric manifolds, where "minimal" is in the sense of not admitting any blowdowns. The second application is an extension to the compact case of a well known result of V\~{u} Ngoc about the constraints posed on a symplectic semitoric manifold by the existence of focus-focus singularities. The helix permits to translate a symplectic geometric problem into an algebraic problem, and the paper describes a method to solve this type of algebraic problem., Comment: 40 pages, 7 figures. Presentation improved, typos corrected

We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval $[0, T]$ and the frequencies can be "off-grid". Previous methods for this problem required the gap between frequencies to be above 1/T, the threshold required to robustly identify individual frequencies. We show the frequency gap is not necessary to estimate the signal as a whole: for arbitrary $k$-Fourier-sparse signals under $\ell_2$ bounded noise, we show how to estimate the signal with a constant factor growth of the noise and sample complexity polynomial in $k$ and logarithmic in the bandwidth and signal-to-noise ratio. As a special case, we get an algorithm to interpolate degree $d$ polynomials from noisy measurements, using $O(d)$ samples and increasing the noise by a constant factor in $\ell_2$., FOCS 2016

We prove asymptotically optimal bounds on the Gaussian noise sensitivity of degree-d polynomial threshold functions. These bounds translate into optimal bounds on the Gaussian surface area of such functions, and therefore imply new bounds on the running time of agnostic learning algorithms.

We define a class of discrete abelian group extensions of rank-one transformations and establish necessary and sufficient conditions for these extensions to be power weakly mixing. We show that all members of this class are multiply recurrent. We then study conditions sufficient for showing that cartesian products of transformations are conservative for a class of invertible infinite measure-preserving transformations and provide examples of these transformations., 20 pages

We design efficient data structures for dynamically maintaining a ham-sandwich cut of two point sets in the plane subject to insertions and deletions of points in either set. A ham-sandwich cut is a line that simultaneously bisects the cardinality of both point sets. For general point sets, our first data structure supports each operation in O(n^1^/^3^+^@e) amortized time and O(n^4^/^3^+^@e) space. Our second data structure performs faster when each point set decomposes into a small number k of subsets in convex position: it supports insertions and deletions in O(logn) time and ham-sandwich queries in O(klog^4n) time. In addition, if each point set has convex peeling depth k, then we can maintain the decomposition automatically using O(klogn) time per insertion and deletion. Alternatively, we can view each convex point set as a convex polygon, and we show how to find a ham-sandwich cut that bisects the total areas or total perimeters of these polygons in O(klog^4n) time plus the O((kb)polylog(kb)) time required to approximate the root of a polynomial of degree O(k) up to b bits of precision. We also show how to maintain a partition of the plane by two lines into four regions each containing a quarter of the total point count, area, or perimeter in polylogarithmic time.

When studying the least common multiple of some finite sequences of integers, the first author introduced the interesting arithmetic functions g k g_k ( k ∈ N ) (k \in \mathbb {N}) , defined by g k ( n ) := n ( n + 1 ) … ( n + k ) lcm ⁡ ( n , n + 1 , … , n + k ) g_k(n) := \frac {n (n + 1) \dots (n + k)} {\operatorname {lcm}(n, n+1, \dots , n + k)} ( ∀ n ∈ N ∖ { 0 } ) (\forall n \in \mathbb {N} \setminus \{0\}) . He proved that for each k ∈ N k \in \mathbb {N} , g k g_k is periodic and k ! k! is a period of g k g_k . He raised the open problem of determining the smallest positive period P k P_k of g k g_k . Very recently, S. Hong and Y. Yang improved the period k ! k! of g k g_k to lcm ⁡ ( 1 , 2 , … , k ) \operatorname {lcm}(1 , 2, \dots , k) . In addition, they conjectured that P k P_k is always a multiple of the positive integer lcm ⁡ ( 1 , 2 , … , k , k + 1 ) k + 1 \frac {\operatorname {lcm}(1 , 2 , \dots , k , k + 1)}{k + 1} . An immediate consequence of this conjecture is that if ( k + 1 ) (k + 1) is prime, then the exact period of g k g_k is precisely equal to lcm ⁡ ( 1 , 2 , … , k ) \operatorname {lcm}(1 , 2 , \dots , k) . In this paper, we first prove the conjecture of S. Hong and Y. Yang and then we give the exact value of P k P_k ( k ∈ N ) (k \in \mathbb {N}) . We deduce, as a corollary, that P k P_k is equal to the part of lcm ⁡ ( 1 , 2 , … , k ) \operatorname {lcm}(1 , 2 , \dots , k) not divisible by some prime.

For sums-of-squares formulas of the form ( x 1 2 + ⋯ + x r 2 ) ( y 1 2 + ⋯ + y s 2 ) = z 1 2 + ⋯ + z t 2 where the z i are bilinear functions of the x i and y i . Let L ( r , s ) denote the smallest possible value of t allowing such a formula to hold. We have two well-known lower bounds on the size of L ( r , s ) . One was obtained independently by Hopf and Stiefel, and another by Atiyah. These bounds are given by requiring certain binomial coefficients be divisible by certain powers of 2. Although the behavior of the Hopf–Stiefel bound is fairly well understood, the Atiyah bound is not. In this paper we provide an efficient algorithm for computing the Atiyah bound and some results on which of the lower bounds is larger.

An $(n, k)$-Poisson Multinomial Distribution (PMD) is a random variable of the form $X = \sum_{i=1}^n X_i$, where the $X_i$'s are independent random vectors supported on the set of standard basis vectors in $\mathbb{R}^k.$ In this paper, we obtain a refined structural understanding of PMDs by analyzing their Fourier transform. As our core structural result, we prove that the Fourier transform of PMDs is {\em approximately sparse}, i.e., roughly speaking, its $L_1$-norm is small outside a small set. By building on this result, we obtain the following applications: {\bf Learning Theory.} We design the first computationally efficient learning algorithm for PMDs with respect to the total variation distance. Our algorithm learns an arbitrary $(n, k)$-PMD within variation distance $\epsilon$ using a near-optimal sample size of $\widetilde{O}_k(1/\epsilon^2),$ and runs in time $\widetilde{O}_k(1/\epsilon^2) \cdot \log n.$ Previously, no algorithm with a $\mathrm{poly}(1/\epsilon)$ runtime was known, even for $k=3.$ {\bf Game Theory.} We give the first efficient polynomial-time approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with $n$ players and $k$ strategies, our algorithm computes a well-supported $\epsilon$-Nash equilibrium in time $n^{O(k^3)} \cdot (k/\epsilon)^{O(k^3\log(k/\epsilon)/\log\log(k/\epsilon))^{k-1}}.$ The best previous algorithm for this problem had running time $n^{(f(k)/\epsilon)^k},$ where $f(k) = \Omega(k^{k^2})$, for any $k>2.$ {\bf Statistics.} We prove a multivariate central limit theorem (CLT) that relates an arbitrary PMD to a discretized multivariate Gaussian with the same mean and covariance, in total variation distance. Our new CLT strengthens the CLT of Valiant and Valiant by completely removing the dependence on $n$ in the error bound., Comment: 68 pages, full version of STOC 2016 paper

This paper aims to move research in the bounded retrieval model BRM from theory to practice by considering symmetric rather than public-key encryption, giving efficient schemes, and providing security analyses with sharp, concrete bounds. The threat addressed is malware that aims to exfiltrate a user's key. Our schemes aim to thwart this by using an enormously long key, yet paying for this almost exclusively in storage cost, not speed. Our main result is a general-purpose lemma, the subkey prediction lemma, that gives a very good bound on an adversary's ability to guess a modest length subkey of a big-key, the subkey consisting of the bits of the big-key found at random, specified locations, after the adversary has exfiltrated partial information about the big-key e.g., half as many bits as the big-key is long. We then use this to design a new kind of key encapsulation mechanism, and, finally, a symmetric encryption scheme. Both are in the random-oracle model. We also give a less efficient standard-model scheme that is based on universal computational extractors UCE. Finally, we define and achieve hedged BRM symmetric encryption, which provides authenticity in the absence of leakage.

We construct a class of transformations similar to the Pascal transformation, except for the use of spacers, and show that these transformations are weakly mixing.

Let B ∈ Z [ x ] be a polynomial with b = B ( 0 ) . Let S be a complete residue class modulo b containing 0. We attempt to classify the polynomials B and residue classes S so that for every polynomial P ∈ Z [ x ] there exists a polynomial Q with coefficients in S such that P ≡ Q ( mod B ) .

Many teachers allow students to drop the lowest score from a sequence of quizzes, tests, or homework assignments. When the number of grades is large, some teachers will even allow students to drop several of their lowest scores. A computer gradebook program would need to implement an algorithm to provide this feature (see one of many examples of computer gradebook software, for example, [4]). A natural criterion to decide which grades to drop would be to drop the set of grades that maximizes the student's final grade. In some circumstances, it can be non-trivial to determine the best grades to drop. Using natural brute force methods, the time needed to find this optimal set of grades to drop can grow exponentially as the number of grades involved grows making these methods impractical even on fast computers. We discuss some unexpected behavior exhibited by this problem and provide a simple and very efficient algorithm for finding the best set of grades to drop.

Let Sa,b = {an+b:n ≥ 0 } where n is an integer. Let Pa,b(n) denote the number of partitions of n into elements of Sa,b. In particular, we have the generating function, $$ \sum_{n=0}^{\infty} P_{a,b}(n)q^{n}=\prod_{n=0}^{\infty} \frac{1}{(1-q^{an+b})}. $$ We obtain asymptotic results for Pa,b(n) when gcd(a,b) = 1. Our methods depend on the combinatorial properties of generating functions, asymptotic approximations such as Stirling's formula, and an in depth analysis of the number of lattice points inside certain simplicies.

Andrews and Lewis have conjectured that the sign of the number of partitions of n n with crank congruent to 0 mod 3, minus the number of partitions of n n with crank congruent to 1 mod 3, is determined by the congruence class of n n mod 3 apart from a finite number of specific exceptions. We prove this by using the “circle method" to approximate the value of this difference to great enough accuracy to determine its sign for all sufficiently large n n .

We give a general unified method that can be used for $L_1$ {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing the equivalence of two unknown (potentially arbitrary) univariate distributions under the $\mathcal{A}_k$-distance metric: Given sample access to distributions with density functions $p, q: I \to \mathbb{R}$, we want to distinguish between the cases that $p=q$ and $\|p-q\|_{\mathcal{A}_k} \ge \epsilon$ with probability at least $2/3$. We show that for any $k \ge 2, \epsilon>0$, the {\em optimal} sample complexity of the $\mathcal{A}_k$-closeness testing problem is $\Theta(\max\{ k^{4/5}/\epsilon^{6/5}, k^{1/2}/\epsilon^2 \})$. This is the first $o(k)$ sample algorithm for this problem, and yields new, simple $L_1$ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions., Comment: 27 pages, to appear in FOCS'15

We study the question of identity testing for structured distributions. More precisely, given samples from a {\em structured} distribution $q$ over $[n]$ and an explicit distribution $p$ over $[n]$, we wish to distinguish whether $q=p$ versus $q$ is at least $\epsilon$-far from $p$, in $L_1$ distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including $t$-flat distributions, $t$-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof., Comment: 21 pages, to appear in SODA'15

We determine for what proportion of integers h one now knows that there are infinitely many prime pairs p, p + h as a consequence of the Zhang–Maynard–Tao theorem. We consider the natural generalization of this to k-tuples of integers, and we determine the limit of what can be deduced assuming only the Zhang–Maynard–Tao theorem.

© 2015 Elsevier Inc. All rights reserved. We prove the conjectured limiting normality for the number of crossings of a uniformly chosen set partition of [n] = {1,2,⋯,n}. The arguments use a novel stochastic representation and are also used to prove central limit theorems for the dimension index and the number of levels.

We prove new bounds on the average sensitivity of the indicator function of an intersection of k halfspaces. In particular, we prove the optimal bound of O n log ( k ) . This generalizes a result of Nazarov, who proved the analogous result in the Gaussian case, and improves upon a result of Harsha, Klivans and Meka. Furthermore, our result has implications for the runtime required to learn intersections of halfspaces. Primary; 52C45

We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form ψ(P(x)), where P:{1,-1}n -> R is a low-degree polynomial and ψ:R -> R is a function with small Lipschitz constant. PRGs for smooth functions of low-degree polynomials have received a lot of attention recently and play an important role in constructing PRGs for the natural class of polynomial threshold functions [12,13,24,16,15]. In spite of the recent progress, no nontrivial PRGs were known for fooling Lipschitz functions of degree O(log n) polynomials even for constant error rate. In this work, we give the first such generator obtaining a seed-length of (log n)~O(l2/e2) for fooling degree l polynomials with error e. Previous generators had an exponential dependence on the degree l. We use our PRG to get better integrality gap instances for sparsest cut, a fundamental problem in graph theory with many applications in graph optimization. We give an instance of uniform sparsest cut for which a powerful semi-definite relaxation (SDP) first introduced by Goemans and Linial and studied in the seminal work of Arora, Rao and Vazirani [3] has an integrality gap of exp(Ω((log log n)1/2)). Understanding the performance of the Goemans-Linial SDP for uniform sparsest cut is an important open problem in approximation algorithms and metric embeddings. Our work gives a near-exponential improvement over previous lower bounds which achieved a gap of Ω(log log n) [11,21]. Our gap instance builds on the recent short code gadgets of Barak et al. [5].

In studying the enumerative theory of super characters of the group of upper triangular matrices over a finite field, we found that the moments (mean, variance, and higher moments) of novel statistics on set partitions of [n]={1,2,⋯,n} have simple closed expressions as linear combinations of shifted bell numbers. It is shown here that families of other statistics have similar moments. The coefficients in the linear combinations are polynomials in n. This allows exact enumeration of the moments for small n to determine exact formulae for all n.

Using maximal isotropic submodules in a quadratic module over Z[subscript p], we prove the existence of a natural discrete probability distribution on the set of isomorphism classes of short exact sequences of cofinite type Z[superscript p]-modules, and then conjecture that as E varies over elliptic curves over a fixed global field k, the distribution of 0→E(k)⊗Q[subscript p]/Z[subscript p]→Sel[subscript p∞]E→Ш[p[superscript ∞]]→0 is that one. We show that this single conjecture would explain many of the known theorems and conjectures on ranks, Selmer groups, and Shafarevich–Tate groups of elliptic curves. We also prove the existence of a discrete probability distribution on the set of isomorphism classes of finite abelian pp-groups equipped with a nondegenerate alternating pairing, defined in terms of the cokernel of a random alternating matrix over ZpZp, and we prove that the two probability distributions are compatible with each other and with Delaunay’s predicted distribution for ШШ. Finally, we prove new theorems on the fppf cohomology of elliptic curves in order to give further evidence for our conjecture., John Simon Guggenheim Memorial Foundation, National Science Foundation (U.S.) (Grants DMS-0841321 and DMS-1069236)

We give two different and simple constructions for dimensionality reduction in $\ell_2$ via linear mappings that are sparse: only an $O(\varepsilon)$-fraction of entries in each column of our embedding matrices are non-zero to achieve distortion $1+\varepsilon$ with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas (JCSS 2003) and Dasgupta, Kumar, and Sarl\'{o}s (STOC 2010). Such distributions can be used to speed up applications where $\ell_2$ dimensionality reduction is used., Comment: v6: journal version, minor changes, added Remark 23; v5: modified abstract, fixed typos, added open problem section; v4: simplified section 4 by giving 1 analysis that covers both constructions; v3: proof of Theorem 25 in v2 was written incorrectly, now fixed; v2: Added another construction achieving same upper bound, and added proof of near-tight lower bound for DKS scheme