Sketching algorithms
Monday,
December 10, 2018
11:40 AM - 12:40 PM
Department of Computer Science, 500 W. 120th St., New York, New York 10027
Room/Area: 451
Room/Area: 451
A "sketch" is a data structure supporting some pre-specified set of queries and updates to a database while consuming space substantially (often exponentially) less than the information theoretic minimum required to store everything seen. Thus sketching can be seen as some form of functional compression. The advantages of sketching include reduced memory consumption, faster algorithms, and reduced bandwidth requirements in distributed computing environments.
Sketching has been a core technique in several domains, including processing massive data streams with low memory footprint, 'compressed sensing' for lossy compression of signals with few linear measurements, and dimensionality reduction or 'random projection' methods for speedups in large-scale linear algebra algorithms, and high-dimensional computational geometry.
This talk will provide a glimpse into some recent progress on core problems in the theory of sketching algorithms.
Sketching has been a core technique in several domains, including processing massive data streams with low memory footprint, 'compressed sensing' for lossy compression of signals with few linear measurements, and dimensionality reduction or 'random projection' methods for speedups in large-scale linear algebra algorithms, and high-dimensional computational geometry.
This talk will provide a glimpse into some recent progress on core problems in the theory of sketching algorithms.
Jelani Nelson is Associate Professor of Computer Science and John L. Loeb Associate Professor of Engineering and Applied Sciences at Harvard. His main research interest is in algorithm design and analysis, with focus on streaming algorithms, dimensionality reduction, compressed sensing, and randomized linear algebra algorithms. He completed his Ph.D. in computer science at MIT in 2011, receiving the George M. Sprowls Award for best computer science doctoral dissertations at MIT. He is the recipient of an NSF CAREER Award, ONR Young Investigator Award, Sloan Fellowship, and Presidential Early Career Award for Scientists and Engineers (PECASE).
LOCATION:
← BACK TO EVENTS
- Morningside
- Lecture
- Computer Science
- Alumni
- Faculty
- Family-friendly
- Graduate Students
- Prospective Students
- Postdocs
- Staff
- Public
- Students
- Trainees
Date Navigation Widget
Getting to Columbia
Other Calendars
- Alumni Events
- Barnard College
- Columbia Business School
- Columbia College
- Committee on Global Thought
- Heyman Center
- Jewish Theological Seminary
- Miller Theatre
- School of Engineering & Applied Science
- School of Social Work
- Teachers College
Guests With Disabilities
- Columbia University makes every effort to accommodate individuals with disabilities. Please notify us if you need any assistance by contacting the event’s point person. Alternatively, the Office of Disability Services can be reached at 212.854.2388 and [email protected]. Thank you.