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: 

ITR: Collaborative Research: Natural Language in the Development of High-Confidence Software

Abstract:


Inadequate communication of domain knowledge in natural language (such as English textual descriptions) is a major source of requirements defects in high-confidence software. Such defects can threaten lives, property, and the dependability of critical infrastructures. This research develops innovative, multi-disciplinary techniques designed expressly to identify and cope with the properties of natural language that lead to these problems. It analyses the domain-knowledge communication problem from the perspective  Read more about ITR: Collaborative Research: Natural Language in the Development of High-Confidence Software

Category: 

Pages