PaperMetrixEvidence-aware discovery
EN
Interface language English EN العربية AR Türkçe TR
Create account
Researcher profile

Ilias Diakonikolas

7 papers in the PaperMetrix corpus

Publications

Papers by this author

  1. Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

    2015

    We give a general unified method that can be used for L1closeness testing of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testing …

  2. Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

    2015 · arXiv (Cornell University)

    We give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order $n$ is the discrete probability distribution of the sum of $n$ mutually independent Bernoulli random variables. Given $\widetilde{O}(1/ε^2)$ …

  3. Testing Conditional Independence of Discrete Distributions

    2017 · arXiv (Cornell University)

    We study the problem of testing \emph{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 …

  4. Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms

    2018 · arXiv (Cornell University)

    We study the problem of robustly learning multi-dimensional histograms. A $d$-dimensional function $h: D \rightarrow \mathbb{R}$ is called a $k$-histogram if there exists a partition of the domain $D \subseteq \mathbb{R}^d$ into $k$ axis-aligned rectangles …

  5. Testing Conditional Independence of Discrete Distributions

    2018

    We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X,Y,Z) on domain [ℓ1] × [ℓ2] × [n], we want to distinguish, with probability at least …

  6. Hardness of Learning Halfspaces with Massart Noise.

    2020 · arXiv (Cornell University)

    We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. Specifically, given labeled examples $(x, y)$ from a distribution $D$ on $\mathbb{R}^{n} \times \{ \pm 1\}$ such that the marginal …

  7. Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise

    2024 · arXiv (Cornell University)

    We study the problem of learning a single neuron with respect to the $L_2^2$-loss in the presence of adversarial distribution shifts, where the labels can be arbitrary, and the goal is to find a ``best-fit'' …