Computer Science

The IBM Computer Science Principles and Methodologies Group (aka the Theory Group) 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.

We have ongoing projects 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?

• Recent activity reports

External Awards
• 2008 ACM Fellow Election: Ken Clarkson was elected an ACM Fellow
• An inaugural 2008 ACM PODS Alberto O. Mendelzon Test-of-Time-Award, awarded to Phokion Kolaitis
• 2007: Phokion Kolaitis was elected a Foreign Member of the Finnish Academy of Science and Letters
• 2006 AAAS Fellow Election: Ronald Fagin was elected an AAAS Fellow
• 2005 ACM Fellow Election: Phokion Kolaitis was elected an ACM Fellow
• 2005 SIAM Outstanding Paper Prize was awarded to Robert Krauthgamer and Uriel Feige (Weizmann Institute of Science; Microsoft Research)
• The 2004 SIGMOD Edgar F. Codd Innovations Award was awarded to Ronald Fagin
• The 2003 Knuth Prize was awarded to Miklós Ajtai


IBM Research Awards
• 2005 Pat Goldberg Memorial Best Paper Award was awarded to Volker Markl, Peter Haas, Nimrod Megiddo, Marcel Kutsch (IBM Germany), T.M. Tran (IBM SVL), and Utkarsh Srivastava (former summer intern, Stanford) (Announced July 2006)
• 2004 Pat Goldberg Memorial Best Paper Award was awarded to Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, Wang-Chiew Tan (UC Santa Cruz) (Announced August 2005)
• 2003 Pat Goldberg Memorial Best Paper Award was awarded to Nimrod Megiddo and Dharmendra Modha (Announced August 2004)
• 2002 IBM Research CS/EE/Math Best Paper Award was awarded to Miklós Ajtai (Announced August 2003)
• 2001 IBM Research CS/EE/Math Best Paper Awards were awarded to Ronald Fagin, Ravi Kumar, and D. Sivakumar (Announced August 2002)

• Miklós Ajtai: Complexity theory, cryptography, lattice-based algorithms.
• Ken Clarkson: Computational geometry, design and analysis of algorithms, optimization.
• Ronald Fagin: Logic, complexity theory, database principles, reasoning about knowledge, information retrieval.
• Vitaly Feldman: Learning theory, computational models of the brain, complexity theory.
• Elad Hazan: Online learning, optimization, computational finance, game theory.
• T. S. Jayram: Complexity theory, algorithms for massive data sets.
• Phokion Kolaitis: Logic in computer science, computational complexity, database theory
  
• Nimrod Megiddo: Optimization, machine learning.
• David Woodruff: Algorithms, complexity theory, cryptography.

• Benny Kimelfeld: Database theory, XML, query optimization, enumeration algorithms and complexity, probabilistic databases, incomplete information, ranking techniques, information retrieval.
• Mihai Pătraşcu (IBM Raviv Memorial Fellow): Algorithms, data structures
• C. Seshadhri: Sublinear algorithms and property testing, approximation algorithms, computational geometry, machine learning

• 2009: Jelani Nelson, Ilias Diakonikolas
• 2008: Shipra Agrawal, Steve Hanneke, Swastik Kopparty, Homin Lee, Jelani Nelson, Prasad Raghavendra
• 2007: Alexandr Andoni, Seshadhri Comandur, Mihai Pătraşcu
• 2006: Alexandr Andoni, Nilesh Dalvi, Ben Rossman, Atri Rudra
• 2005: Kamalika Chaudhuri, Parikshit Gopalan, Satyen Kale, Elitza Maneva, Ciamac Moallemi
• 2004: Marcelo Arenas, Shuchi Chawla, Iordanis Kerenidis, James Lee, Eugene Nudelman
• 2003: Iordanis Kerenidis, David Liben-Nowell, Erik Vee, An Zhu
• 2002: Gagan Aggarwal, Aaron Archer, Mayur Datar, Subhash Khot, Matthias Ruhl
• 2001: Aaron Archer, Ziv Bar-Yossef, April Rasala, Tim Roughgarden, Matthias Ruhl, An Zhu
• 2000: Andris Ambainis, Ziv Bar-Yossef, Venkatesan Guruswami, Liadan O'Callaghan, Adam Kalai, Byunggyoo Kim, John Langford
• 1999: Moses Charikar, Venkatesan Guruswami, and Amit Sahai

• Bruno Marnette (Apr 7-May 7, 2008)
  
• Lisa Fleischer (Aug 27-31, 2007)
  
• Amit Chakrabarti (Jun 1-29, 2007)
  
• Marcelo Arenas (Jun 4-8, 2007)
  
• Tim Roughgarden (Sep 5-6 and Sep 12-22, 2006)
  
• Amit Chakrabarti (Aug 14-25, 2006)
  
• Matt Valeriote (June 5-10, 2006)
  
• Mihai Patrascu (Apr 26-May 1, 2006)
  
• Daniela Pucci de Farias (Jan 31-Feb 3, 2006)
  
• Jeremy Schwartz (Jan 31-Feb 3, 2006)
  
• Manoj Prabhakaran (Dec 19-Dec 21, 2005)
  
• Yuval Rabani (Oct 10-Oct 21, 2005)
  
• Daniela Pucci de Farias (Aug 1-Aug 5, 2005)
  
• Eli Ben-Sasson (Apr 18-May 5, 2005)
  
• Yuval Rabani (Feb 8-Feb 23, 2005)
  
• Albert Atserias (Jan 31-Feb 11, 2005)
  
• Daniela Pucci de Farias (Jan 18-Jan 24, 2005)
  
• Ravi Sundaram (Nov 8-Nov 15, 2004)
  
• Seffi Naor (Aug 30-Sep 10, 2004)
  
• Amit Chakrabarti (Aug 9-Aug 20, 2004)
  
• Leonard Schulman (Aug 9-Aug 12, 2004)
• Daniela Pucci de Farias (Aug 2-Aug 9, 2004)
  
• Moshe Y. Vardi (Jul 26-Jul 30, 2004)
• Yuval Rabani (Jun 28-Jul 16, 2004)
  

• Balder ten Cate (Jan - Aug, 2008)
  
• Elitza Maneva (2006-2008) [postdoctoral fellow]
  
• Aranyak Mehta (2005-2007) [postdoctoral fellow]
  
• Erik Vee (2004-2006) [postdoctoral fellow]
  
• Matthias Ruhl (2003-2004) [Joseph Raviv postdoctoral fellow]
  
• Daniela Pucci de Farias (2002-2003)