Algorithms and Theoretical Computer Science

The theories of computer science are what make computers possible. Algorithms include computational calculation and automated reasoning, while theoretical computer science deals with the mathematical aspects of computing. These theories help engineers build on our current knowledge of computers in order to invent breakthroughs, paving the way to better and newer solutions.

Faculty: 

Boris  Aronov
Lisa   Hellerstein
John   Iacono


Sample research projects:

John Iacono is the co-author of "Cache-Oblivious Persistence." Partial persistence is a general transformation that takes a data structure and allows queries to be executed on any past state of the structure. The cache-oblivious model is the leading model of a modern multi-level memory hierarchy. This paper presents the first general transformation for making cache-oblivious model data structures partially persistent.

Read the paper here (pdf)

 

Boris Aronov co-wrote a paper titled "Improved Bounds for the Union of Locally Fat Objects in the Plane." In this paper, they obtain sharper upper bounds on the complexity of the union of n locally γ-fat objects of constant complexity in the plane, and of n γ-fat triangles in the plane.

Read the paper here (pdf)