All reports by Author Ilias Diakonikolas:

__
TR18-189
| 8th November 2018
__

Ilias Diakonikolas, Daniel Kane#### Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

__
TR17-133
| 7th September 2017
__

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price#### Sample-Optimal Identity Testing with High Probability

__
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-178
| 11th November 2016
__

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price#### Collision-based Testers are Optimal for Uniformity and Closeness

Comments: 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

__
TR16-074
| 9th May 2016
__

Ilias Diakonikolas, Daniel Kane#### A New Approach for Testing Properties of Discrete Distributions

__
TR13-172
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

__
TR13-171
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

__
TR12-181
| 20th December 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### The Inverse Shapley Value Problem

__
TR12-152
| 7th November 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Inverse Problems in Approximate Uniform Generation

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
TR09-117
| 18th November 2009
__

Ilias Diakonikolas, Daniel Kane, Jelani Nelson#### Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

Ilias Diakonikolas, Daniel Kane

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ 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 ...
more >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>

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, Themis Gouleakis, John Peebles, Eric Price

We study the fundamental problems of (i) uniformity testing of a discrete distribution,

and (ii) closeness testing between two discrete distributions with bounded $\ell_2$-norm.

These problems have been extensively studied in distribution testing

and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}.

In this work, we show ... 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 >>>

Ilias Diakonikolas, Daniel Kane

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 in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').

In this work, we give a ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates

\[

\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]

\]

to within an additive $\pm \eps$ in ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[

\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]

to within an additive $\pm \eps$. For any constant ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>