Title: Distributed Monotonicity Reconstruction

Speaker: Mike Saks, Rutgers 
 
Suppose $P$ is a property of functions defined on some domain
$D$.  Given an arbitrary function $f$ defined on $D$
we want to find a function $g$ satisfying
$P$ that is close to $f$ (in Hamming
distance). The algorithm has access to  
a single short random string (of size polylogarithmic in $|D|$)
and when presented with an element $x$ of the domain, 
should make a small (polylogarithic in  $|D|$) number of
probes to the function $f$, and should then output $g(x)$.
Such an algorithm is called a "distributed reconstruction algorithm"
for the property $P$.

This framework can be viewed as a generalization
of self-correction of programs and local decoding of codes.
In that setting the property
being reconstructed is membership in a good code, and functions
having the property are "far" from each other, so that
a correctible
function $f$ (one that is close to having the property) has a unique
correction.  In our setting,
we consider more general properties, where the input function $f$
may be close to many possible functions with the property.
This introduces the problem of ensuring that the local corrections to
$f$ are {\em consistent}, that is, combine to give
a function having property $P$.

We show how to obtain such a reconstruction algorithm in the case that
the function is a multidimensional array and the property
to be reconstructed is monotonicity: being sorted along
every line of the array.

This is joint work with Seshadhri Comandur.