Miklos Ajtai  Miklos Ajtai photo       

contact information

Research Staff Member
IBM Almaden Research Center
San Jose, CA 95120



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.