Ron Fagin, IBM Fellow!
On April 10, 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. More, and and interview with Ron, here.
Overview
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.
Projects
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?
Research Staff
- 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.
- 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.
- Jan Vondrak: Approximation algorithms, stochastic optimization, discrete probability.
- David Woodruff: Algorithms, complexity theory, cryptography.
Postdoctoral Fellows
- Yi Wu: Learning theory, complexity theory
- Moritz Hardt: Sensitive data analysis, algorithms, complexity and learning theory
What's all this about P not equaling NP?
Recently 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.)
Recent Awards: External to IBM
Awards to People
- 2012 IEEE W. Wallace McDowell Award: Ronald Fagin won "for fundamental and lasting contributions to the theory of databases"
- 2011 IEEE Technical Achievement Award: Ronald Fagin won "for pioneering contributions to the theory of rank and score aggregation"
- 2010 AAAS Fellow Election: Phokion Kolaitis was elected an AAAS Fellow
- 2009 Informs Fellow Election: Nimrod Megiddo was elected an INFORMS Fellow
- 2008 ACM Fellow Election: Ken Clarkson was elected an ACM Fellow
- 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
- The 2004 SIGMOD Edgar F. Codd Innovations Award was awarded to Ronald Fagin
- The 2003 Knuth Prize was awarded to Miklós Ajtai
- 2001: Ronald Fagin was named Docteur Honoris Causa of the University of Paris
Awards for Papers
- 2011 ACM PODS Alberto O. Mendelzon Test-of-Time Award, Ronald Fagin with Amnon Lotem and Moni Naor
- Best Paper Award, 26th IEEE Conference on Computational Complexity (CCC 2011), Ryan Williams
- Best Paper Award, 29th Annual ACM Symposium on Principles of Database Systems (PODS 2010), David Woodruff with Daniel Kane and Jelani Nelson
- Best Paper Award, 13th International Conference on Database Theory (ICDT, 2010), Ronald Fagin with Marcelo Arenas and Alan Nash
- Best Paper Award, 12th International Conference on Database Theory (ICDT, 2009), Phokion Kolaitis with Foto Afrati
- An inaugural 2008 ACM PODS Alberto O. Mendelzon Test-of-Time-Award, Phokion Kolaitis
- Best Paper Award, Fall IEEE Vehicular Technology Conference (VTC 2007), Ken Clarkson with John Hobby
- 2005 SIAM Outstanding Paper Prize, Robert Krauthgamer with Uriel Feige (Weizmann Institute of Science; Microsoft Research)
- Best Paper Award, 2001 ACM Symposium on Principles of Database Systems (PODS 2001), Ronald Fagin with Amnon Lotem and Moni Naor
Recent Awards: Internal to IBM
Awards to People
- 2010 IBM Corporate Award: Ronald Fagin won an IBM Corporate Award for advances in database theory
- 2009 IBM Academy of Technology: Miklos Ajtai was named a member of the IBM Academy of Technology
- 2009 Master Inventor: Nimrod Megiddo was honored as an IBM Master Inventor
- 2007 IBM Academy of Technology: Ronald Fagin was named a member of the IBM Academy of Technology
Awards for Papers
- 2010 Pat Goldberg Memorial Best Paper Award was awarded to Jelani Nelson (MIT), Daniel Kane (MIT), and David P. Woodruff
- 2008 Pat Goldberg Memorial Best Paper Award was awarded to Jacob Abernathy (UC Berkeley), Elad Hazan and Alexander Rakhlin (UC Berkeley) (Announced August 2009)
- 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 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)
Awards for Accomplishments, Innovations, or Patents
- 2008 IBM Outstanding Technical Achievement Award and 2006 IBM Outstanding Innovation Award: Ronald Fagin and Phokion Kolaitis, with Lucian Popa, for schema mappings research
- 2007 IBM Supplemental Patent Issue Award: Ronald Fagin and Nimrod Megiddo, with Moni. Naor, Dalit Naor, and Jeffrey Lotspiech, for key IBM patents on encryption keys
- 2005 IBM Research Division Accomplishment: Nimrod Megiddo, with Bruce Cassidy, Benny Gill, and Dharmendra Modha, for research on adaptive replacement caches
- 2005 IBM Research Division Accomplishment: Ronald Fagin and Phokion Kolaitis, with Lucian Popa, for research on foundations of schema mappings. Was upgraded in 2007 (along with practice of schema mappings by Howard Ho, Laura Haas, and Mauricio. Hernandez) to an Outstanding IBM Research Division Accomplishment.
- 2004 IBM Research Division Accomplishment and IBM Outstanding Innovation Award: Miklos Ajtai, for lower bounds for branching programs
- 2004 IBM Outstanding Technical Achievement Award: Nimrod Megiddo, with Dharmendra Modha, for research on adaptive replacement cache algorithms
- 2003 IBM supplemental Patent Issue Award: Miklos Ajtai, Ronald Fagin, and Larry Stockmeyer, with Randal Burns, Darrell Long, David Pease, Bernie Lopez, Robert Morris, and Norm Pass, for key IBM patents on differential backup
- 2003 IBM Research Division Accomplishment: David Gibson, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, and Andrew Tomkins, for research on using the link structure of the web
- 2002 IBM Outstanding Innovation Award: Miklos Ajtai, Ronald Fagin and Larry Stockmeyer, with Randal Burns, for differential backup for Tivoli Storage Manager
- 2001 IBM Research Division Accomplishment and IBM Outstanding Innovation Award: Ronald Fagin, for research on aggregation algorithms for middleware
Summer interns
- 2011: Yi Li, Ian Post, Eric Price, Mary Wootters
- 2010: Arnab Bhattacharyya, Shayan Oveis Gharan, Greg Valiant, Dang-Trinh Huynh-Ngoc
- 2009: Ilias Diakonikolas, Jelani Nelson
- 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, Amit Sahai
Recent short-term visitors
- Alina Ene (May - June 2011)
- Balder ten Cate (Jul - Aug 2010)
- Nati Srebro (Aug 2 - Aug 6 2010)
- Guy Kindler (Aug 10 - Aug 21, 2009)
- Suresh Venkatasubramanian (Jul 27 - Aug 8, 2009)
- Robi Krauthgamer (Jul 13 - Jul 24, 2009)
- Aravind Srinivasan (Jun 24 - Jun 26,2009)
- 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)
Recent longer-term visitors and postdoctoral fellows
- Benny Kimelfeld (2008-2010) [postdoctoral fellow]
- C. Seshadhri (2008-2010) [postdoctoral fellow]
- Mihai Pătraşcu (2008-2009) [IBM Raviv Memorial Fellow]
- 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)
IBM Research CS Algorithms & Theory
