CS Events

Computer Science Department Colloquium

Gaps in My Research

 

Download as iCal file

Monday, April 10, 2023, 10:30am - 11:30am
 

Speaker: Michael A. Bender

Bio

Bender is Professor and David R. Smith Leading Scholar in Computer Science at Stony Brook University. He was Founder and Chief Scientist at Tokutek, Inc, an enterprise database company, which was acquired byPerconain 2014.  Bender's research interests span the areas of data structures and algorithms, I/O-efficient computing, scheduling, and parallel computing.  He has coauthored over 180 articles on these and other topics.  He has won several awards, including an R&D 100 Award, a Test-of-Time Award, a Distinguished Paper Award, two Best Paper Awards, and five awards for graduate and undergraduate teaching.


 

Bender received his B.A. in Applied Mathematics from Harvard University in 1992 and obtained a D.E.A. in Computer Science from the EcoleNormaleSuperieure de Lyon, France in 1993. He completed a Ph.D. on Scheduling Algorithms from Harvard University in 1998. He has held Visiting Scientist positions at both MIT and King's College London. He is a Fellow of the European Association for Theoretical Computer Science (EATCS). 

Location : Core 301

: 

Event Type: Computer Science Department Colloquium

Abstract: In my first computer science course, we learned that insertion sort runs in $O(n^2)$ time---each insertion into the array takes time $O(n)$ and there are $n$ insertions. I distinctly remember asking, "why not do what librarians do? Why not leave gaps in the array in anticipation of future insertions?" Some years later, I would find the answer to this question---adding gaps to insertion sort improves its running time to $O(n \log n)$. This technique of strategically leaving gaps in arrays to support future insertions is surprisingly powerful. I'll explain how leaving gaps leads to a general approach for designing platform-independent data structures. I'll also present two recent theoretical breakthroughs: how we (1) solved a 40-year-old problem on how efficiently one can maintain a dynamic set of sorted items in an array, and (2) overturned 60-year-old conventional wisdom on the performance of linear-probing hash tables. Throughout the talk, I'll emphasize the surprising bi-directional bridge between algorithms and real-world systems building.

: 

Contact  Jie Gao

Zoom
https://rutgers.zoom.us/j/95777675829?pwd=NzlDYnIyRGlRMlZLU0ZUS3QvNVpwUT09