CS Events

Computer Science Department Colloquium

How big is a pointer?


Download as iCal file

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

Link for the recording of the event:


Password: wU3?Qi&0