The Taub Faculty of Computer Science Events and Talks

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).