Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Property Testing and Combinatorial Approximation
event speaker icon
Arie Matsliah (Ph.D. Thesis Seminar)
event date icon
Wednesday, 25.06.2008, 16:00
event location icon
Taub 601
event speaker icon
Advisor: Assoc. Prof. E. Fischer
With the recent advances in technology, we are faced with the need to process increasingly larger amounts of data increasingly faster. 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).