Miklos Ajtai

Research Staff Member
IBM Almaden Research Center
CS Principles and Methodologies Department

Address:
Miklos Ajtai
IBM Almaden Research Center
Department K53
650 Harry Road
San Jose, CA 95120.
ph. +1 (408) 927-1852
fax +1 (408) 927-3030
email: ...@almaden.ibm.com where you have to replace ... with my last name

Research Interest.

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.