Source author record

Vladimir Nikishkin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Information Theory math.IT math.ST Statistics Theory Computational Complexity Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

7topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions

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 ε$ with probability at least $2/3$ . We show that for any $k \ge 2, ε>0$ , the {\em optimal} sample complexity of the $\mathcal{A}_k$ -closeness testing problem is $Θ(\max\{ k^{4/5}/ε^{6/5}, k^{1/2}/ε^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.

preprint2014arXiv

Testing Identity of Structured Distributions

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

preprint2012arXiv

Amortized communication complexity of an equality predicate

We study the communication complexity of a direct sum of independent copies of the equality predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); computational complexity of the proposed protocol is polynomial in size of inputs. Our protocol improves the result achieved in 1995(Feder, Kushilevitz, Naor, Nisan). Our construction is based on two techniques: Nisan's pseudorandom generator (1992) and Smith's string synchronization algorithm (2007).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.