Sourav Chakraborty (Chennai, India):
 Testing st-connectivity in the orientation model
<br><br>
Abstract: "Property testing" asks the query-complexity of
distinguishing, with high probability, the cases when a string has
a property and when it is $\epsilon$-far in relative Hamming
distance from all strings having the property.  Graph properties
have been studied primarily in the dense model where the a graph on
v vertices is represented by a string of length v(v-1)/2.
Properties of sparse graphs cannot be studied in this model.
<br><br>

Halevy, Lachish, Newman, and Tsur (2007) introduced a model called
the "orientation model" to study properties of oriented graphs
regardless of their density.  In this model, an undirected graph is
explicitly given; the hidden information accessible through an
oracle is an orientation of this graph.
<br><br>

A major question which was left open in the paper by Halevy at al.
is whether the property of $st$-connectivity can be tested in this
model with a constant number of queries.  We answer this question
in the affirmative: We show that $st$-connectivity in the orientation
model can be tested using $O(2^{2^{2^{1/\epsilon}}})$ queries.
<br><br>

This is accomplished by a reduction of testing $st$-connectivity
to the problem of testing bounded-width branching programs, solved
by Ilan Newman.  The reduction combines combinatorial arguments
with a new concentration lemma for sequences of integers.
<br><br>

This is joint work with Eldar Fischer, Oded Lachish, Arie Matsliah
and Ilan Newman.