All reports by Author Alistair Stewart:

__
TR17-132
| 7th September 2017
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Sharp Bounds for Generalized Uniformity Testing

__
TR17-075
| 29th April 2017
__

Clement Canonne, Ilias Diakonikolas, Alistair Stewart#### Fourier-Based Testing for Families of Distributions

Revisions: 1

__
TR16-177
| 11th November 2016
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Revisions: 1

__
TR13-069
| 1st May 2013
__

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis#### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ ... more >>>

Clement Canonne, Ilias Diakonikolas, Alistair Stewart

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

The following two decision problems capture the complexity of

comparing integers or rationals that are succinctly represented in

product-of-exponentials notation, or equivalently, via arithmetic

circuits using only multiplication and division gates, and integer

inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>