קולוקוויום: Colloquium: On Imperfect but Very Fast Algorithms by Dana Ron

Electrical Engineering Colloquium 

Speaker: Prof. Dana Ron

Title: On Imperfect but Very Fast Algorithms

Abstract 

Algorithms are usually considered efficient if they run in time that is polynomial in their input size. Assuming the algorithm reads its entire input, the best we can hope for is linear time. But what if the input is huge and we can’t afford even reading it entirely? Here is where sublinear-time algorithms come into play. Such algorithms do not read the entire input, but rather query/sample it. We allow them to give approximate answers, and fail with small probability. What we gain is efficiency.
 
In this talk, I will try to give a taste of sublinear algorithms.

Light refreshments will be served before the lecture

This colloquium is not counted toward seminar credit.

ההרצאה לא מזכה בקרדיט שמיעת סמינרים.