# Miklos Ajtai

## contact information

Research Staff Member

IBM Almaden Research Center

San Jose, CA 95120

+14089271852

IBM Almaden Research Center

San Jose, CA 95120

+14089271852

## links

## profile

My main field of interest is complexity theory and its connections with combinatorics, logic, and other branches of mathematics. I am particularly interested in the theory of lower bounds in various settings e.g. constant depth circuits, branching programs, propositional proof systems. I am also working on problems in the theory of lattices and its application to cryptography. This interest also has its origin in complexity theory: namely the connection between worst-case and average-case complexity and the NP-completeness of lattice problems. Other areas: expander graph constructions, sorting, deterministic simulation of probabilistic algorithms, file differencing algorithms, finite model theory.