Cache-Adaptive Analysis
Computer Science Department
Stony Brook University
COM2 Level 1
SR@LT19 COM2, Level 1
Abstract:
A process's share of memory changes dynamically as other processes start, stop, or change their own demands for memory. Designing and analyzing algorithms that can respond to these changes can be challenging.
In this talk, we will explain how cache-oblivious algorithms can help in the design of such "cache-adaptive" algorithms. We will also present analytical techniques that make performance analysis of cache adaptive algorithms almost as easy as analysis of algorithms in the standard Disk-Access-Machine (DAM) model.
Biodata:
Rob Johnson is an Assistant Professor at Stony Brook University and conducts research on Security, Big Data Algorithms, and Cryptography. He is director of the Security, Privacy, And Theory (SPLAT) lab at Stony Brook, the Cryptography Lab at the New York Center for Excellence in Wireless and Information Technology (CEWIT), and the Smart Grid Cyber-Security Testing Lab of the New York Advanced Energy Research and Technology Center (AERTC).
He does theoretical work with an impact on the real world. He developed BetrFS, a file system that uses recent advances in data structures to improve performance on some operations by over an order of magnitude. He invented the Quotient filter, a high-performance alternative to the Bloom filter for Big Data applications. He founded cache-adaptive analysis, a theoretical framework for designing and analyzing algorithms that dynamically share memory with other processes. He broke the High-bandwidth Digital Content Protection (HDCP) crypto-system used in almost all DVD players and TVs. He co-authored CQual, a static analysis tool that has found dozens of bugs in the Linux kernel. Since then, it has been used to audit the entire Debian Linux distribution for format-string bugs.
He completed his Ph.D. at UC Berkeley in 2006.