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.)