CS Events Monthly View
Computer Science Department Colloquium
How big is a pointer?
Monday, September 13, 2021, 11:00am
Speaker: Dr. Martin Farach-Colton
Martin Farach-Colton is a professor of computer science at Rutgers University, where he works on pure and applied algorithms in I/O-efficient storage systems, streaming algorithms and string matching. He was Founder and CTO at Tokutek, Inc, an enterprise database company, which was acquired by Percona in 2015. He has been a Member of Technical Staff at Bell Labs (1997-98) and was an early employee of Google, Inc. (2000-2002). Farach-Colton received his M.D. from Johns Hopkins and his Ph.D. from the University of Maryland. Farach-Colton is a Sloan and SIAM Fellow.
Location : Via Zoom
Event Type: Computer Science Department Colloquium
Abstract: There is an obvious lower bound of Omega(log n) bits needed to encode a pointer to a memory of size n. But is this really the smallest a pointer can be? We show that in many cases, pointers can be much smaller, which has implications to both the theory of succinct data structures and to virtual memory systems.
Rutgers University School of Arts and Sciences
Contact Host: Dr. Matthew Stone