All reports by Author David García Soriano:

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR10-048
| 24th March 2010
__

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet#### Monotonicity Testing and Shortest-Path Routing on the Cube

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>