Miklos Ajtai  Miklos Ajtai photo       

contact information

Research Staff Member
IBM Almaden Research Center
San Jose, CA 95120
  +1dash408dash927dash1852

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.