Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR11-041 | 24th March 2011
Dana Ron, Gilad Tsur

Testing Computability by Width-Two OBDDs

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 >>>

ISSN 1433-8092 | Imprint