IC Colloquium - Something for almost nothing: Advances in sub-linear time algorithms
Event details
| Date | 04.11.2013 |
| Hour | 16:15 › 17:30 |
| Speaker | Ronitt Rubenfeld - MIT and Tel Aviv University |
| Location | |
| Category | Conferences - Seminars |
Abstract:
Linear-time algorithms have long been considered the gold standard of computational efficiency. Indeed, it is hard to imagine doing better than that, since for a nontrivial problem, any algorithm must consider all of the input in order to make a decision. However, as extremely large data sets are pervasive, it is natural to wonder what one can do in {\em sub-linear} time. Over the past two decades, several surprising advances have been made on designing such algorithms. We will give a non-exhaustive survey of this emerging area, highlighting recent progress and directions for further research.
Bio:
Ronitt Rubinfeld received her Bachelor's degree at the University of Michigan and PhD at the University of California, Berkeley. She held postdoctoral positions at DIMACS and the Hebrew University at Jerusalem. After several years as a faculty member at Cornell University and a senior research scientist at NEC Research Institute, she is currently on the faculties of MIT and Tel Aviv University. She has been a recipient of the ONR Young Investigator award, NSF Career Award, Sloan Fellowship, Cornell Association for Computer Science Undergraduates Faculty of the Year award and a Cornell College of Engineering Teaching award. She was an invited speaker at the International Congress of Mathematicians in 2006. Her research focuses on sub-linear time algorithms for big datasets.
Linear-time algorithms have long been considered the gold standard of computational efficiency. Indeed, it is hard to imagine doing better than that, since for a nontrivial problem, any algorithm must consider all of the input in order to make a decision. However, as extremely large data sets are pervasive, it is natural to wonder what one can do in {\em sub-linear} time. Over the past two decades, several surprising advances have been made on designing such algorithms. We will give a non-exhaustive survey of this emerging area, highlighting recent progress and directions for further research.
Bio:
Ronitt Rubinfeld received her Bachelor's degree at the University of Michigan and PhD at the University of California, Berkeley. She held postdoctoral positions at DIMACS and the Hebrew University at Jerusalem. After several years as a faculty member at Cornell University and a senior research scientist at NEC Research Institute, she is currently on the faculties of MIT and Tel Aviv University. She has been a recipient of the ONR Young Investigator award, NSF Career Award, Sloan Fellowship, Cornell Association for Computer Science Undergraduates Faculty of the Year award and a Cornell College of Engineering Teaching award. She was an invited speaker at the International Congress of Mathematicians in 2006. Her research focuses on sub-linear time algorithms for big datasets.
Links
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Aleksander Madry