Title: Testing assignments for satisfying a read-once formula
Speaker: Eldar Fischer, Israel Institute of Technology (Technion)
Date: Wednesday, October 17, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Property Testing deals with the following question: Distinguish using as few queries to the input as possible, ideally with a number of queries independent of the input size, between inputs that satisfy a given property and inputs that are far from any possible input satisfying the property. In the massively parametrized model, a fixed part of the input is given to the algorithm in advance, on which the algorithm has to be exact. That is, any alternative input differing on the part given in advance is not considered to be close to the original input.
In this talk we consider properties defined by read-once Boolean formulas, where the formula is given in advance. Such formulas are representable as trees with their nodes labeled by the corresponding gates. The part of the input that is not given in advance (and must be queried from) is the assignment to the formula's variables, i.e. the values at its leaves.
For all properties given by And/Or gates, and in fact all properties where the gates are of bounded arity, we give a test whose number of queries does not depend on the input size at all. In essence this means that untestability cannot be "broken down" to small gates. On the other hand, for non-Boolean alphabets there is in fact a simple gate with two inputs that can be used for formulas that are not testable with a constant number of queries.
We also discuss some related questions, such as instances where we can estimate the actual distance of the input from satisfying the formula, and a test for And/Or formulas whose number of queries is only quasi-polynomial in the approximation parameter.
This is joint work with Yonatan Goldhirsh and Oded Lachish.