
PreviousNext
We study the testing problem, that is, the problem of determining (maybe
probabilistically) if a function to which we have oracle access
satisfies a given property.
We propose a framework in which to formulate and carry out the analyzes
of several known tests. This framework establishes a connection between
more >>>
We consider the computational complexity of some problems
dealing with matrix rank. Let E,S be subsets of a
commutative ring R. Let x_1, x_2, ..., x_t be variables.
Given a matrix M = M(x_1, x_2, ..., x_t) with entries
chosen from E union {x_1, x_2, ..., ...
more >>>
We consider the well known problem of determining the k'th
vertex reached by chasing pointers in a directed graph of
out-degree 1. The famous "pointer doubling" technique
provides an O(log k) parallel time algorithm on a
Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>
PreviousNext