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 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.

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

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.

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)).

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.

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 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 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.

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 ) .

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 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.

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

The function \(f : \mathbb{F}_2^n \to \mathbb{F}_2\) is k-linear if it returns the sum (over \(\mathbb{F}_2\)) of exactly k coordinates of its input. We introduce strong lower bounds on the query complexity for testing whether a function is k-linear. We show that for any \(k \le \frac n2\), at least k − o(k) queries are required to test k-linearity, and we show that when \(k \approx \frac n2\), this lower bound is nearly tight since \(\frac43 k + o(k)\) queries are sufficient to test k-linearity. We also show that non-adaptive testers require 2k − O(1) queries to test k-linearity.

We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph.

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 a new bound on the average sensitivity of polynomial threshold functions. In particular we show that a polynomial threshold function of degree $d$ in at most $n$ variables has average sensitivity at most $\sqrt{n}(\log(n))^{O(d\log(d))}2^{O(d^2\log(d)}$. For fixed $d$ the exponent in terms of $n$ in this bound is known to be optimal. This bound makes significant progress towards the Gotsman-Linial Conjecture which would put the correct bound at $\Theta(d\sqrt{n})$.

We develop and analyze a new family of pseudorandom generators for polynomial threshold functions with respect to the Gaussian distribution. In particular, for any fixed degree we develop a generator whose seed length is subpolynomial in the error parameter, epsilon. We get particularly nice results for degree 1 and degree 2 threshold functions, in which cases our seed length is O(log(n) + log^{3/2}(1/epsilon)) and exp(O~(log^{2/3}(1/epsilon))), respectively.

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson-Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 e] ≤ δ, with seed-length r = O(log d + log(1/δ) ċ log (log(1/δ/e)). In particular, for δ = 1/ poly(d) and fixed e > 0, we obtain seed-length O((log d)(log log d)). Previous constructions required Ω(log2 d) random bits to obtain polynomially small error. We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/δ)/e2) on the embedding dimension. Previously, Jayram and Woodruff [10] used communication complexity techniques to show a similar bound.

We discuss a psuedorandom generator to $\epsilon$-fool degree-d polynomial threshold functions with respect to the Gaussian distribution with seed length $2^O_c(d)\log(n) \epsilon^{-4-c}$. Our analysis involves several new ideas including what we term the "noisy derivative" of a function and a stronger version of standard anticoncentration results.

We show that any $O_d(\epsilon^{-4d 7^d})$-independent family of Gaussians $\epsilon$-fools any degree-$d$ polynomial threshold function.

Given a Young diagram $\lambda$ and the set $H^{\lambda}$ of partitions of $\{1,2,\dots$, $|\lambda|\}$ of shape $\lambda$, we analyze a particular ${\cal S}_{|\lambda|}$-module homomorphism ${\Bbb Q}H^{\lambda}\to{\Bbb Q}H^{\lambda'}$ to show that ${\Bbb Q}H^{\lambda}$ is a submodule of ${\Bbb Q}H^{\lambda'}$ whenever $\lambda$ is a hook $(n,1,1,\dots,1)$ with $m$ rows, $n\geq m$, or any diagram with two rows.

For a partition Λ of n, let H ( Λ ) denote its hook product. If l is prime and a ⩾ 0 an integer, then define p l ( a ; n ) = | { Λ : | Λ | = n , a = ord l ( H ( Λ ) ) } | . These numbers are simply related to the McKay numbers in the representation theory of the symmetric group. Using a generating function of Nakamura and the “circle method,” we determine asymptotic properties of p l ( a ; n ) and ∑ a ( − 1 ) a p l ( a ; n ) , resolving questions of Ono. In particular we show that for fixed l and n, p l ( a ; n ) roughly fits a given distribution that is dependent on l, is centered near n − c 1 n log n and has width c 2 n . We also give an asymptotic formula for ∑ a ( − 1 ) a p l ( a ; n ) that is valid whenever n is not, for any k, within a multiplicative factor of c log l of l k . This formula is of the form ± c ( n ) / n exp ( κ ( n ) n ) where c and κ are specific functions of n and the sign is determined by n.