Algorithms and Theory     


Algorithms and Theory - overview

Our dual objective is to pursue basic research on a broad range of theoretical topics and to impact real-world issues by applying our expertise to solving problems for IBM and its clients.

We do basic research in a number of areas of theoretical computer science, including approximation algorithms, combinatorics, complexity theory, computational geometry, distributed systems, learning theory, online algorithms, cryptography and quantum computing.

IBM researchers have access to an extensive array of challenging problems that motivate innovative solutions and, at the same time, constantly push the theoretical state-of-the-art with the development of new algorithms and new optimization techniques. We provide innovative, custom solutions to business and industrial problems that are at the boundaries of what can be solved today.


Almaden Research Center

Research Staff

  • Amir Abboud: Complexity theory, hardness in P, fine-grained complexity
  • Miklos Ajtai (emeritus): Complexity theory, cryptography, lattice-based algorithms.
  • Clément Canonne (Goldstine Postdoctoral Fellow): Property testing with a focus on distribution testing, learning theory, online and approximation algorithms, stochastic processes.
  • Ken Clarkson: Matrix computations, computational geometry, algorithms, optimization.
  • Ronald Fagin (IBM Fellow): Logic, complexity theory, database principles, reasoning about knowledge, information retrieval.
  • Phokion Kolaitis: Logic in computer science, computational complexity, database theory.
  • Nimrod Megiddo: Optimization, machine learning.

Watson Research Center

Research Staff

  • Srinivasan Arunachalam: Quantum and classical aspects of algorithms, learning theory, complexity theory, analysis of Boolean functions.
  • Charanjit Jutla: Cryptography, complexity theory, coding theory, mathematical logic.
  • Krzysztof Onak: Sublinear-time algorithms, property testing, streaming, algorithms for massive data sets.
  • Kanthi Sarpatwar: Algorithmic design and analysis, mathematical programming, privacy preserving machine learning.

IBM Research – India

Research Staff

See also

Cryptography, Quantum Computing