## 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:

- Time complexity of problems in the RAM model
- Time complexity classes defined "up to a constant factor" and computational robustness of these classes
- Linear time complexity classes in their nondeterministic and deterministic versions; characterization of these classes in logic (finite model theory)
- Complexity of logical problems

- Time complexity lower bounds of "natural" (combinatorial) problems
- Two extensions of linear time complexity