Research and Grants

PYI: The Internal Quantitative Structure of Complexity Classes

Abstract:


New extensions of Lebesgue measure theory are used to investigate the internal, quantitative structure of complexity classes. The relationships among intrinsically pseudorandom objects, pseudorandom number generators, probabilistic and interactive complexity classes, and completeness phenomena are studied. Another focus is the measure structure of exponential time complexity classes.


 

Read more about PYI: The Internal Quantitative Structure of Complexity Classes

Category: 

CPS:Synergy: Safety-Aware Cyber-Molecular Systems

Future cyber-molecular systems such as biosensors and drug therapeutics must operate safely in a dynamic physical environment.   A newly funded project by computer science faculty Robyn Lutz, Jack Lutz, and Jim Lathrop, and GDCB faculty Eric Henderson, will help design cyber-molecular systems that are reliably safe for use.  

Read more about CPS:Synergy: Safety-Aware Cyber-Molecular Systems

Category: 

AF:Small:Collaborative Research:Studies in nonuniformity, completeness, and reachability

Abstract:


Computational complexity theory classifies computational problems into various complexity classes based on the amount of resources needed to solve them. This classification is done by measuring various resources such as time, space, nonuniformity, nondeterminism, and randomness. A better understanding of the relationships among these various resources shed light on the computational difficulty of the problems that are encountered in practice. Read more about AF:Small:Collaborative Research:Studies in nonuniformity, completeness, and reachability

Category: 

Pages