Source author record

Yonatan Goldhirsh

Yonatan Goldhirsh appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.PR math.ST Statistics Theory

Catalog footprint

What is connected

3works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2014arXiv

On the Power of Conditional Samples in Distribution Testing

In this paper we define and examine the power of the {\em conditional-sampling} oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $μ$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $μ$, conditioned on $S$ (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals $[n]$. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample-complexity remains near-maximal even with conditional sampling.

preprint2014arXiv

Testing Formula Satisfaction

We study the query complexity of testing for properties defined by read once formulas, as instances of {\em massively parametrized properties}, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates, with a number of queries exponential in $ε$, doubly exponential in the arity, and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an {\em estimation} algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulas only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $ε$. On the other hand, we show that such testability results do not hold in general for formulas over non-Boolean alphabets; specifically we construct a property defined by a read-once arity $2$ (non-Boolean) formula over an alphabet of size $4$, such that any $1/4$-test for it requires a number of queries depending on the formula size. We also present such a formula over an alphabet of size $5$ that additionally satisfies a strong monotonicity condition.

preprint2013arXiv

Some properties are not even partially testable

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $ε$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, but can be partitioned into a small number of subsets for which they are partially testable with very few queries. We prove the existence of a property $P$ such that the only subsets $P'$ for which $P$ is $P'$-partially testable are very small. To prove this we introduce new techniques for proving property testing lower bounds. In addition to obtaining some broad-brush criteria for non-testability, this implies a lower bound on the possibility of PCPPs with a sublinear proof. This also implies lower bounds on MAPs, a notion newly defined by Gur and Rothblum. The new techniques rely on analyzing a proposed partial tester. We show that the queries performed by a tester must, with high probability, query indexes where a uniformly random member of the sub-property has low entropy. We then show how one can aggregate the "entropy loss" to deduce that a random choice in the sub-property must have low entropy, and therefore the sub-property must be small. We develop two techniques for aggregating the entropy loss. A simpler technique that applies to non-adaptive testers is based on partitioning the input bits into high query probability parts and parts where there is an entropy loss when conditioned on the high probability parts. Against adaptive testers we develop a technique based on constructing a decision tree. The root-to-leaf paths in this tree rearrange the input into parts where each exhibits entropy loss when conditioned on the path prefix. This decision tree is constructed by combining carefully selected decision trees from those used by the adaptive testing algorithm.