Thursday, June 3, 2021 – 10:00am to 11:00am
Virtual Presentation – ET Remote Access – Zoom
DI WANG, Ph.D. Student https://www.cs.cmu.edu/~diw3/
Type-Guided Worst-Case Input Generation
An important characteristic of a computer program is its resource requirements, that is, the amount of resource such as time, memory, power, etc. that the program needs to execute. Analyzing the worst-case resource usage of a program has many applications, such as finding performance bottlenecks. Besides an analysis of the worst-case behavior, it is often desirable to obtain specific inputs such that executing the analyzed program on these inputs exhibits the worst-case performance.
In this talk, I present a provably sound technique for type-guided worst-case input generation for functional programs. The technique builds on automatic amortized resource analysis, a type-based technique for deriving symbolic bounds on the resource usage of functions. Experiments demonstrate that the technique works effectively and can derive worst-case inputs with hundreds of integers for sorting algorithms, operations on search trees, and insertions into hash tables.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
Zoom Participation. See announcement.