Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR10-048 | 24th March 2010
David García Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Monotonicity Testing and Shortest-Path Routing on the Cube

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

TR09-060 | 4th June 2009
Harry Buhrman, David García Soriano, Arie Matsliah

Learning parities in the mistake-bound model.

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

ISSN 1433-8092 | Imprint