Aquí hay una respuesta que quizás sea demasiado larga …
Estoy seguro de que difiere de persona a persona, pero mi experiencia fue la siguiente. En primer lugar, entré en el primer año de MIT sin saber mucho sobre informática, y también sin saber qué era una prueba matemática. Sabía algo de C / C ++ de enseñarme a mí mismo en mi último año de escuela secundaria, y algo de HTML de enseñarme a mí mismo en 8º grado, pero eso fue todo. Tampoco tenía idea de qué era la investigación.
Mi primera exposición a las pruebas fue en el año de primer año, tomando la pista teórica para el cálculo de una sola variable / multivariable y las ecuaciones diferenciales (18.014, 18.024 y 18.034 – ver Jelani Nelson – CLASES). Mi primera exposición a los algoritmos fue en mi segundo curso de algoritmos de Spring (6.046). Me gustó la clase, pero en ese momento era solo una clase de muchas y no pensé mucho más en los algoritmos durante al menos otro año. Mi siguiente curso de informática teórica fue un curso de criptografía para graduados (6.875) en mi primavera de secundaria, que realmente disfruté. En ese momento, pensé que quería hacer criptografía.
- Cómo estudiar para exámenes competitivos.
- ¿Deberíamos alojarnos en un albergue o una universidad cuando estudiamos en el BIPC?
- ¿Cómo puedo estudiar más de 14 horas al día? ¿Alguna motivación o concentración hacks?
- ¿Dónde puedo encontrar información sobre los estudios que buscan curas utilizando alucinógenos?
- Cómo estudiar con la máxima concentración.
Al mismo tiempo, me inscribí en una cuenta de TopCoder cerca del final del tercer año (en mayo). También me inscribí en una cuenta en la pasarela de capacitación de USACO y en los sitios web de otros jueces en línea. Un par de amigos míos en el MIT, a saber, Hubert Hwang (TopCoder: antimateria) y David Pritchard (TopCoder: daveagp), estaban realmente en TopCoder en ese momento y me metí en eso debido a su influencia. Es bastante fácil para mí volverse adicto a los juegos de computadora / video, y vi los problemas de resolución en estos sitios web como un juego. Verano de 2004 Probablemente pasé más de 8 horas al día resolviendo ejercicios algorítmicos en varios sitios web. Yo diría que esta fase de mi vida fue bastante fundamental. Después de aproximadamente 2 años en TopCoder, el pensamiento algorítmico se convirtió en una segunda naturaleza.
También realicé algunos cursos de posgrado en algoritmos en mi último año: Algoritmos avanzados (6.854), Algoritmos aleatorios (6.856) y Estructuras de datos avanzadas (6.897 en ese momento, ahora 6.851). Todos tenían proyectos finales, pero estaba bastante ocupado tomando 6 clases por semestre, así que no tuve mucho tiempo para lanzar ningún esfuerzo serio de investigación. Afortunadamente, Erik Demaine, como parte de 6.897, tuvo algunas “sesiones abiertas de resolución de problemas” a las que asistí. Estos fueron bastante divertidos, y como parte de uno, un equipo de 7 de nosotros resolvimos un problema de estructura de datos sobre los cortes dinámicos de sándwich de jamón que publicamos ese verano en CCCG. No fue un problema importante, pero creo que uno de los objetivos de estas sesiones era presentar a los jóvenes a la investigación en informática teórica. Funcionó en mí; Creo que fue un buen refuerzo de confianza, y simplemente una buena manera de mojarme los pies. (También fue mi primer artículo en colaboración con Daniel Kane, con el que terminé trabajando más tarde en varios proyectos durante la escuela de posgrado).
En mi último año de otoño, también solicité admisión en dos (dos) escuelas de posgrado (diciendo que quería hacer criptografía). Tenía un promedio de calificaciones (GPA) de 5.0 en ese momento, pero no tenía experiencia en investigación de teoría, y fui rechazado de ambos. (Tampoco puedo recordar el motivo por el que hice la solicitud, teniendo en cuenta que en ese momento no entendía realmente lo que era un doctorado …). Después del último año hice un Master de un año supervisado por Bradley Kuszmaul y Charles Leiserson, centrado en la memoria externa y en la memoria caché de las estructuras de datos ajenas. Como solo tomaba dos clases por semestre, tenía mucho más tiempo para concentrarme en la investigación. En algún momento, Bradley y yo creamos un compromiso de actualización / consulta para el antecesor de la memoria externa, pero luego Jeremy Fineman señaló que se había realizado en un SODA varios años antes. Sin embargo, trabajamos en otras cosas, lo que llevó a un documento de SPAA un año más tarde en dos soluciones que no tenían en cuenta la memoria caché y que tenían como objetivo obtener un rendimiento de actualización mucho mejor sin dejar de tener buenas consultas. Mi principal contribución fue en la desarticulación de la “matriz de búsqueda anticipada de memoria caché” (COLA) en ese trabajo. Entonces, creo que para este punto, tuve la capacidad de hacer un trabajo de teoría.
Sin embargo, realmente no encontré mi área actual (transmisión / esbozo / reducción de dimensionalidad / etc.) Hasta mi segundo año de doctorado. En mi primer año traté de hacer algunas cosas más que no me gustaba el caché, pero realmente no llegué a ningún lado. En mi segundo año, en otoño, tomé un curso de Piotr Indyk sobre transmisión y bocetos. Hice un proyecto final con Krzysztof Onak y Nick Harvey sobre estimación de entropía en flujos de datos. Tuvimos un progreso no trivial al final del curso, y seguimos trabajando intensamente en la primavera. Conseguimos obtener un algoritmo bastante bueno para la fecha límite de FOCS, por lo que lo enviamos y lo aceptamos. Ese fue mi primer artículo en el área que se convirtió en el foco de mi tesis.
