Arie Matsliah, Ph.D. Thesis Seminar
Wednesday, 25.6.2008, 16:00
With the recent advances in technology, we are faced with the need to process increasingly larger amounts of data
Originally, a problem was considered computable if there was an algorithm that could decide it in finite time given any
input instance. Later came the notion of polynomial time computation, and then the possibility of making computations
faster through use of parallel machines. However, the algorithms involved still face the obvious obstacle of reading the
entire input prior to its assessment.
There are practical situations in which the input is so large that even taking a linear time in its size to provide an
answer is too much. In other situations the input is not easily accessible, or does not have an explicit representation,
and an "oracle" procedure that computes its values in specific locations is provided instead.
The main line of our research revolves around designing and analyzing algorithms that make a decision concerning the
input after reading only a small portion of it. In particular, the questions addressed in this work are related to
combinatorial property testing, sub-linear time algorithms, and probabilistically checkable proofs of proximity (PCPPs).