Foundational Issues in Computer Science

点击翻译按钮获取中文摘要

This project investigates three distinct areas. (1) Average case complexity. The major goal is to enable one to prove the average case hardness of real-life decision and search problems. The research involves reexaming the basic definition of average-case reduction and average-case polynomial-time. (2) Finite model theory. The most challenging question is whether there exists a logic that captures the notion of polynomial-time on arbitrary (not necessarily ordered) structures. The PI has conjecture a few year ago that the answer is negative. The thrust of the research is the question what parts of polynomial time can be captured by logics. Another direction is extension of the methods of finite model theory to the study of finite structures with weights in infinite domains. (3) Abstract state machines. Abstract state machines is a new model of computation which has been successfully used to specify and verify real-life algorithms. Here this model is applied to complexity theory and finite model theory.