The Computer Science Colloquium
Thursday, April 3, 2014 4:15-5:30pm, room 9204
(Stony Brook University)
" Incrementalization: From Clarity to Efficiency "
Two major concerns of study rest at the center of computer science: what to compute, and how to compute efficiently. Problem solving involves going from clear specifications for the "what" to efficient implementations for the "how". This is challenging because, usually, clear specifications correspond to straightforward implementations, not at all efficient, while efficient implementations are difficult to understand, not at all clear.
This work gives an overview of a systematic method for transforming clear specifications into efficient implementations via incrementalization. The method has three steps: (1) iterate---determine a minimum increment to be taken repeatedly, (2) incrementalize---maintain appropriate values incrementally over the repeated steps, and (3) implement---design data structures for the values maintained. We illustrate the method through examples, taken from problems in hardware design and image processing expressed using loops and arrays, in query processing and access control expressed using set expressions, in sequence processing and math puzzles expressed using recursive functions, in program analysis and trust management expressed using logic rules, and in building software components expressed using objects. Finally we discuss our ongoing projects, including optimization of distributed algorithms expressed using logic quantifications.
The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.