David Ron Karger (nacido el 1 de mayo de 1967) es un científico informático estadounidense, profesor y miembro del Laboratorio de Ciencias de la Computación e Inteligencia Artificial ( CSAIL ) del Instituto Tecnológico de Massachusetts .
Karger obtuvo 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 avances significativos en varios problemas centrales. Es responsable del algoritmo de Karger , un método de Monte Carlo para calcular el corte mínimo de un gráfico conexo. [4] Karger desarrolló el algoritmo de árbol de expansión mínima más rápido hasta la fecha, con Philip Klein y Robert Tarjan . Encontraron un algoritmo aleatorio en 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 realizado 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 examinar eficazmente grandes masas 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 redispersarlos. [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 los asistentes a conferencias utilizada en muchos congresos de investigación.
La disertación de Karger recibió el premio de tesis doctoral ACM de 1994 [8] y el premio Tucker de 1997 de la Sociedad de Programación Matemática . [9] También recibió el Premio 2004 a la Iniciativa en Investigación de la Academia Nacional de Ciencias . [10]
Karger está casado con Allegra Goodman , una escritora estadounidense. La pareja vive en Cambridge, Massachusetts y tiene cuatro hijos, tres niños y una niña. [11]