Principles and Methodologies - overview

The Principles and Methodologies Group (A.K.A. the Theory Group) at IBM Research - Almaden explores foundational issues that confront the computing industry today. Because theory cuts across every aspect of computer science, we tend to interact with a large number of other research teams.

Our research includes ongoing work in the following areas:

  • Algorithms: How can we get computers to solve problems efficiently?
  • Complexity: What computational resources (time, storage, etc) do problems inherently require?
  • Database Principles: What models and algorithms are useful in helping computers store and retrieve information efficiently?


What's all this about P not equaling NP?

Not long ago there was considerable interest in a proposed proof that P is not equal to NP. In response to that interest, some members of the theory group gave a talk to describe, for a general scientific audience, some aspects of this work and the community's analysis of it.

(The video starts a little bit into the talk; the speakers are Ken Clarkson, Ron Fagin, and Ryan Williams, in that order; the "D." referred to is Vinay Deolalikar, the author of the proposed proof.)

Video of the talk (including all but the first few slides)

The slides



Ron Fagin, IBM Fellow!

On April 10, 2012, theory group member Ron Fagin was named an IBM Fellow. This is IBM's highest technical distinction; there have been only 238 IBM Fellows since the program began in 1963. See here for more, and an interview with Ron.

Tribute to John Backus

A tribute to John Backus, one of the first members of our Theory Group, written by Alex Aiken