Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Complexity Zoology is both a survey of the relationships between complexity classes and the software designed to assist the survey. It is inspired by the Complexity Zoo, an online wiki describing complexity classes and their properties. Given an initial data set consisting of a list of complexity classes, inclusions, and oracle separations, the Complexity Zoology expert system deduces further relations using transitivity. The system can also identify unanswered questions that are extremal in a precise sense, thereby identifying interesting open problems.

Complexity Zoology's data set has largely been informed by the expertise of Scott Aaronson, who created the Complexity Zoo wiki, and Lance Fortnow. Greg Kuperberg wrote the original version of Complexity Zoology and provided additional contributions to the data set.

This is a cross-listing of the CS department colloquium. See math department e-mail for the Zoom URL.