All reports by Author Gilad Tsur:

__
TR11-078
| 9th May 2011
__

Dana Ron, Gilad Tsur#### On Approximating the Number of Relevant Variables in a Function

__
TR11-041
| 24th March 2011
__

Dana Ron, Gilad Tsur#### Testing Computability by Width-Two OBDDs

Dana Ron, Gilad Tsur

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

Dana Ron, Gilad Tsur

Property testing is concerned with deciding whether an object

(e.g. a graph or a function) has a certain property or is ``far''

(for a prespecified distance measure) from every object with

that property. In this work we consider the property of being

computable by a read-once ...
more >>>