This project concentrates on three areas: (1) Average-case complexity: Tuning up the average-case reduction theory, finding more average-case complete problems, and proving average-case hardness of real- life problems; (2) Finite model theory: Investigating whether semantical properties (such as monotonicity) have any syntactic characterizations on finite structures, determining whether parts of polynomial time properties can be captured by polynomial-time-bounded logics, and studying finite structures with weights in infinite structures (such as arithmetic); (3) Evolving algebras: Examining a new computation model (evolving algebras) in order to use these algebras to specify and verify real-life algorithms.
