Research

Keywords

Computational complexity, linear time theory, computational models (RAM and cellular automaton), logic and finite model theory, descriptive complexity, complexity of logical theories and logical queries, complexity of enumeration problems.

Description

My main topic is the study of linear time complexity and, more generally, of the complexity classes defined "up to a constant factor" in the RAM model. This study is closely related to logical definability in finite structures (finite model theory). More precisely, I work or have worked on the following subjects:

  1. Time complexity of problems in the RAM model
  2. Time complexity classes defined "up to a constant factor" and computational robustness of these classes
  3. Linear time complexity classes in their nondeterministic and deterministic versions; characterization of these classes in logic (finite model theory)
  4. Complexity of logical problems
  5. Time complexity lower bounds of "natural" (combinatorial) problems
  6. Two extensions of linear time complexity
    1. to enumeration problems
    2. to linear time of deterministic and nondeterministic cellular automata

Publications (references and abstracts)