Contact Info
Office
Crerar 247

Research

Focus Areas: Theory, Computational Logic, Type Theory, Complexity Theory, Randomness

My interest in the computational properties of random and generic sets goes back to my thesis, written under the supervision of Carl Jockusch in Mathematics at the University of Illinois. Unlike most people working in computational complexity theory, my understanding of randomness is based on measure theory and definability rather than compressibility.

Another long-term research interest is the Berman-Hartmanis Isomorphism Conjecture, which holds that all NP-complete sets are isomorphic under polynomial-time computable and invertable 1-1 reductions. Just for the record, I believe that the conjecture is false.

I’m currently coming up to speed on type theory, approaching it as a mash-up of formal logic and functional programming.

Research

Theory

The mathematical foundations of computation, including algorithm design, complexity and logic

Labs & Groups

Theoretical Computer Science Group

The Theory group plays a fundamental role in connecting CS with physics, statistics, and other mathematical sciences.

Programming Languages Group

Interested in all aspects of programming language design and implementation, ranging from theoretical foundations to practical applications.

News & Events

No Name

Ravi Chugh Promoted to Associate Professor at UChicago Computer Science

Jan 06, 2021
No Name

Cosmos Boekell Comes Full Circle to Lead CS Instructional Laboratory (CSIL)

Oct 23, 2019
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube