Abstract
How big is a pointer? The question seems to have a trivial answer: there are at least $\log n$ bits in a pointer to a memory of size $n$. In this talk, I’ll show that this is not always true. There are many situations where pointers can be compressed. After exploring the theory of compressed pointers, I’ll show that they can have consequences in the design of hardware and operating systems.
Biography
Martin Farach-Colton is the Leonard J. Shustek Professor of Computer Science and Chair of the Department of Computer Science and Engineering at NYU, 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 Fellow of the AAAS, ACM, IEEE, and SIAM, and a Fellow of the Argentine National Academy of Sciences.