Publications 
Eldar Fischer, Yonatan Goldhirsh and Oded Lachish
Partial Tests, Universal Tests and Decomposability
5th Innovations in Theoretical Computer Science (ITCS), 2014.
Subsumes ECCC TR13082 and arXiv:1306.1360 [cs.CC]
[Abstract]
[PDF:soon!]
For a property $P$ and a subproperty $P'$, we say that $P$ is \emph{$P'$partially testable with $q$ queries} if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$far from $P$, using $q$ queries. Some natural properties 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, sometimes even a number independent of the input size.
For properties over ${0,1}$, the notion of being thus partitionable ties in closely with MerlinArthur proofs of Proximity (MAPs) as defined independently in \cite{MAP}; a partition into $r$ partiallytestable properties is the same as a MerlinArthur system where the proof consists of the identity of one of the $r$ partiallytestable properties, giving a $2$way translation to an $O(\log r)$ size proof.
Our main result is that for some low complexity properties a partition as above cannot exist, and moreover that for each of our properties there does not exist even a single subproperty featuring both a large size and a queryefficient partial test, in particular improving the lower bound set in \cite{MAP}. For this we use neither the traditional Yaotype arguments nor the more recent communication complexity method, but open up a new approach for proving lower bounds.
First, we use entropy analysis, which allows us to apply our arguments directly to $2$sided tests, thus avoiding the cost of the conversion in \cite{MAP} from $2$sided to $1$sided tests. Broadly speaking we use ``distinguishing instances'' of a supposed test to show that a uniformly random choice of a member of the subproperty has ``low entropy areas'', ultimately leading to it having a low total entropy and hence having a small base set.
Additionally, to have our arguments apply to adaptive tests, we use a mechanism of ``rearranging'' the input bits (through a decision tree that adaptively reads the entire input) to expose the low entropy that would otherwise not be apparent.
Apart from the main result, we also explore the possibility of a connection in the other direction, namely whether the existence of a good partition (or MAP) can lead to a relatively queryefficient standard property test. We provide some preliminary results concerning this question, including a simple lower bound on the possible tradeoff, and some positive tradeoff result for the very restricted framework of $1$sided proximity oblivious tests.
The positive tradeoff result is through the construction of a ``universal tester'' that works the same for all properties admitting a restricted test. Our tester is very related to the notion of samplebased testing (for a nonconstant number of queries) as defined by Goldreich and Ron. In particular it partially addresses some of the questions raised by Goldreich and Ron.
Yonatan Goldhirsh and Michael Viderman
Testing Membership in Counter Automaton Languages
17th. International Workshop on Randomization and Computation (RANDOM), 2013.
[Abstract]
[PDF:Soon!]
Alon et al. (SICOMP 2001) showed that all regular languages are testable with a constant number of queries. On the other hand, they also showed that some context free languages require $\Omega(\sqrt{n})$ queries to test. Following this, Alon et al. suggested the problem of classifying the context free languages that are testable with a constant number of queries.
We make progress towards the solution of this problem. Our main result is that languages accepted by \emph{weak counter automata} are testable with a constant number of queries. A counter automaton is a pushdown automaton with a single stack symbol, effectively a nonnegative counter that the automaton may compare to zero. It is \emph{weak} if the set of possible transitions with a zero counter is a subset of the possible transitions with a positive counter. Note that this restriction is essential, since Lachish et. al. (CC 2008) proved that there exist counter automaton languages requiring $\Omega(\polylog n)$ queries to test.
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh and Arie Matsliah
On the Power of Conditional Samples in Distribution Testing
4th Innovations in Theoretical Computer Science (ITCS), 2013.
[Abstract]
[arXiv]
[ECCC]
In this paper we define and examine the power of the {\em conditionalsampling} oracle in the context of distributionproperty testing. The conditionalsampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, conditioned on $S$ (and independently of all prior samples). The conditionalsampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals $[n]$.
We show that with the conditionalsampling oracle, testing uniformity, testing identity to a known distribution, and testing any labelinvariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the samplecomplexity remains nearmaximal even with conditional sampling.
Eldar Fischer, Yonatan Goldhirsh and Oded Lachish
Testing Formula Satisfaction
13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2012.
[Abstract]
[arXiv]
We study the query complexity of testing for properties defined by read once formulae, as instances of massively parametrized properties, and prove several testability and nontestability results. First we prove the testability of any property accepted by a Boolean readonce formula involving any bounded arity gates with a number of queries exponential in $\epsilon$ and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an estimation algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulae only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $\epsilon$. On the other hand we show that such testability results do not hold in general for formulae over nonBoolean alphabets; specifically we construct a property defined by a readonce arity 2 (nonBoolean) formula over alphabets of size 4, such that any 1/4test for it requires a number of queries depending on the formula size.
