David Ron Karger (nacido el 1 de mayo de 1967) es un científico informático estadounidense que es profesor y miembro del Laboratorio de Ciencias de la Computación e Inteligencia Artificial ( CSAIL ) en el Instituto Tecnológico de Massachusetts .
Karger recibió una licenciatura en Artes de la Universidad de Harvard y un doctorado en informática de la Universidad de Stanford . [3]
El trabajo de Karger en algoritmos se ha centrado en aplicaciones de aleatorización a problemas de optimización y ha llevado a un progreso significativo en varios problemas centrales. Es responsable del algoritmo de Karger , un método de Monte Carlo para calcular el corte mínimo de un grafo conectado. [4] Karger desarrolló el algoritmo de árbol de expansión mínimo más rápido hasta la fecha, con Philip Klein y Robert Tarjan . Encontraron un algoritmo aleatorizado en el tiempo lineal basado en una combinación del algoritmo de Borůvka y el algoritmo de eliminación inversa. [5] Con Ion Stoica , Robert Morris , Frans Kaashoek y Hari Balakrishnan , también desarrolló Chord , uno de los cuatro protocolos originales de tabla hash distribuida . [6]
Karger ha llevado a cabo investigaciones en el área de recuperación de información y gestión de información personal . Este trabajo se ha centrado en nuevas interfaces y algoritmos para ayudar a las personas a filtrar de forma eficaz grandes cantidades de información. Mientras estuvo en Xerox PARC , trabajó en el sistema Scatter/Gather, que agrupaba jerárquicamente una colección de documentos y permitía al usuario reunir grupos en diferentes niveles y volver a dispersarlos. [7] Más recientemente [ ¿cuándo? ] ha estado investigando sistemas de recuperación que se personalizan para adaptarse mejor a las necesidades y comportamientos de sus usuarios individuales, liderando el proyecto Haystack . David Karger también forma parte de Confer: una herramienta para asistentes a conferencias utilizada en muchas conferencias de investigación.
La disertación de Karger recibió el premio de disertación doctoral ACM de 1994 [8] y el Premio Tucker de la Sociedad de Programación Matemática de 1997. [9] También recibió el Premio de Iniciativa en Investigación de la Academia Nacional de Ciencias de 2004. [10]
Karger está casado con Allegra Goodman , una escritora estadounidense. La pareja vive en Cambridge, Massachusetts y tiene cuatro hijos, tres varones y una niña. [11]