El premio Machtey se otorga en el Simposio anual de IEEE sobre fundamentos de la informática (FOCS) al autor (es) de los mejores trabajos de los estudiantes. Un artículo califica como artículo de estudiante si todos los autores son estudiantes de tiempo completo en la fecha de envío. La decisión de adjudicación la toma el Comité de Programa.
El premio lleva el nombre de Michael Machtey, quien fue investigador en la comunidad teórica de ciencias de la computación en la década de 1970. [1] La contraparte de este premio en el Simposio ACM sobre Teoría de la Computación (STOC) es el Premio Danny Lewin al Mejor Trabajo Estudiantil . [2]
Destinatarios anteriores
Los beneficiarios anteriores del premio Machtey se enumeran a continuación. [ cita requerida ]
Año | Destinatario (Universidad) | Papel |
---|---|---|
2020 | Rahul Ilango ( MIT ) | "La fórmula de profundidad constante y las versiones de función parcial de MCSP son difíciles" |
2019 | Jason Li ( CMU ) | "K-cut mínimo más rápido de un gráfico simple" |
Josh Alman ( MIT ) Lijie Chen ( MIT ) | "Construcción eficiente de matrices rígidas utilizando un NP Oracle" | |
2018 | Shuichi Hirahara ( Universidad de Tokio ) | "Reducciones del peor caso al promedio que no son de caja negra dentro de NP" |
Urmila Mahadev ( UC Berkeley ) | "Verificación clásica de la computación cuántica" | |
2017 | Rasmus Kyng ( Yale ) Peng Zhang ( Georgia Tech ) | "Resultados de dureza para sistemas lineales estructurados" [3] |
2016 | Michael B. Cohen ( MIT ) | "Gráficos de Ramanujan en tiempo polinomial" [4] |
Aviad Rubinstein (Berkeley) | "Resolver la complejidad de calcular los equilibrios de Nash aproximados de dos jugadores" [5] | |
2015 | Mika Göös ( Universidad de Toronto ) | "Límites inferiores para la camarilla frente al conjunto independiente" |
Aaron Sidford ( MIT ) Yin Tat Lee ( MIT ) Sam Chiu-wai Wong ( Universidad de California, Berkeley ) | "Un método de plano de corte más rápido y sus implicaciones para la optimización combinatoria y convexa" | |
2014 | Aaron Sidford (MIT) Yin Tat Lee (MIT) | "Métodos de búsqueda de rutas para la programación lineal: resolución de programas lineales en iteraciones Õ (√rank) y algoritmos más rápidos para un flujo máximo" |
2013 | Jonah Sherman ( Universidad de California, Berkeley ) | "Caudales casi máximos en un tiempo casi lineal" [6] |
2012 | Nir Bitansky ( Universidad de Tel Aviv ), Omer Paneth ( Universidad de Boston ) | "De la imposibilidad de la ofuscación a una nueva técnica de simulación sin caja negra" |
2011 | Kasper Green Larsen ( Aarhus ) | "Búsqueda de rango en el modelo de grupo y discrepancia combinatoria" |
Timon Hertli ( ETH Zúrich ) | "3-SAT más rápido y sencillo: límites de SAT únicos para retención de PPSZ en general" | |
2010 | Aaron Potechin ( MIT ) | "Límites en redes de conmutación monótona para conectividad dirigida" |
2009 | Alexander Sherstov ( UT Austin ) | "La intersección de dos medios espacios tiene un grado de umbral alto" |
Jonah Sherman ( Universidad de California, Berkeley ) | "Rompiendo la barrera del flujo de productos múltiples para sqrt (log (n)) - Aproximaciones al corte más disperso" | |
2008 | Mihai Pătraşcu ( MIT ) | "Succínter" |
2007 | Por Austrin ( KTH ) | "Hacia una gran inaproximación para cualquier 2-CSP" |
2006 | Nicholas JA Harvey (MIT) | "Estructuras y algoritmos algebraicos para problemas de emparejamiento y matriz" |
2005 | Mark Braverman ( Toronto ) | "Sobre la complejidad de las funciones reales" |
Tim Abbott (MIT), Daniel Kane (MIT), | "Sobre la complejidad de los juegos de dos jugadores en los que se gana y se pierde" | |
2004 | Lap Chi Lau (Toronto) | "Un teorema aproximado de corte de min-Steiner-empaquetamiento de árboles de Max-Steiner" |
Marcin Mucha ( Varsovia ), Piotr Sankowski (Varsovia) | "Emparejamientos máximos a través de la eliminación gaussiana" | |
2003 | Subhash Khot ( Princeton ) | "Dureza de aproximar el problema del vector más corto en normas de alta Lp" |
2002 | Boaz Barak ( Weizmann ) | "Lanzamiento de monedas de ronda constante con un hombre en el medio o realización del modelo de cadena aleatoria compartida" |
Harald Räcke ( Paderborn ) | "Minimizar la congestión en las redes generales" | |
2001 | Boaz Barak (Weizmann) | "Cómo superar la barrera de la simulación de caja negra" |
Vladlen Koltun ( Tel Aviv ) | "Límites superiores casi ajustados para descomposiciones verticales en cuatro dimensiones" | |
2000 | Piotr Indyk ( Stanford ) | "Distribuciones estables, generadores pseudoaleatorios, incrustaciones y cálculo del flujo de datos" |
1999 | Markus Bläser ( Bonn ) | "Un límite inferior de 5/2 n 2 para el rango de multiplicación de matrices n × n sobre campos arbitrarios" |
Eric Vigoda ( Berkeley ) | "Límites mejorados para el muestreo de colorantes" | |
1998 | Kamal Jain ( Tecnología de Georgia ) | "Algoritmo de aproximación del factor 2 para el problema de red de Steiner generalizado" |
Daniele Micciancio (MIT) | "El problema del vector más corto es NP-difícil de aproximar dentro de alguna constante" | |
1997 | Santosh Vempala ( CMU ) | "Un algoritmo basado en muestreo aleatorio para aprender la intersección de medios espacios" |
1996 | Jon Kleinberg (MIT) | "Flujo no divisible de fuente única" |
1995 | Andras Benczur (MIT) | "Una representación de recortes dentro de 6/5 veces la conectividad perimetral con aplicaciones" |
Satyanarayana V. Lokam ( Chicago ) | "Métodos espectrales para la rigidez de la matriz con aplicaciones para compensaciones de tamaño-profundidad y complejidad de la comunicación" | |
1994 | Rakesh K. Sinha, TS Jayram ( Washington ) | "Programas de ramificación eficientes y ajenos a las funciones de umbral" |
Jeffrey C. Jackson ( CMU ) | "Un algoritmo de consulta de membresía eficiente para aprender DNF con respecto a la distribución uniforme" | |
1993 | Pascal Koiran | "Una versión débil del modelo de Blum, Shub & Smale" |
1992 | Bernd Gärtner ( FU Berlín ) | "Un algoritmo subexponencial para problemas de optimización abstracta" |
1991 | Anna Gal (Chicago) | "Límites inferiores para la complejidad de circuitos booleanos confiables con puertas ruidosas" |
Jaikumar Radhakrishnan ( Rutgers ) | "Mejores límites para fórmulas de umbral" | |
1990 | David Zuckerman (Berkeley) | "Fuentes aleatorias débiles generales" |
1989 | Bonnie Berger (MIT) John Rompel (MIT) | "Simulación de la independencia (log c n ) en NC" |
1988 | Shmuel Safra (Weizmann) | "Sobre la complejidad de los omega-autómatas" |
1987 | John Canny (MIT) | "Un nuevo método algebraico para la planificación del movimiento del robot y la geometría real" |
Abhiram G. Ranade ( Yale ) | "Cómo emular la memoria compartida (versión preliminar)" | |
1986 | Prabhakar Raghavan (Berkeley) | "Construcción probabilística de algoritmos deterministas: aproximación de programas de empaquetamiento de enteros" |
1985 | Ravi B. Boppana (MIT) | "Amplificación de fórmulas booleanas probabilísticas" |
1984 | Joel Friedman (Harvard) | "Construcción de fórmulas monótonas de tamaño O ( n log n ) para el k -ésimo polinomio simétrico elemental de n variables booleanas" |
1983 | Harry Mairson (Stanford) | "La complejidad del programa de buscar una tabla" |
mil novecientos ochenta y dos | Carl Sturtivant ( Universidad de Minnesota ) | "Simetrías generalizadas de polinomios en complejidad algebraica" |
1981 | F. Thomson Leighton (MIT) | "Nuevas técnicas de límite inferior para VLSI" |
Ver también
- Lista de premios de informática
- Premio Kleene
Referencias
- ^ Lista de publicaciones de Michael Machtey en DBLP
- ^ ACM SIGACT. "Danny Lewin Best Student Paper Award" Archivado el 20 de junio de 2008 en Wayback Machine.
- ^ "Premios al mejor artículo de FOCS 2017" (PDF) .
- ^ "Premios FOCS 2016 al Mejor Trabajo" (PDF) .
- ^ "Premios FOCS 2016 al Mejor Trabajo" (PDF) .
- ^ "FOCS 2013 Best Paper Awards" . Archivado desde el original el 13 de diciembre de 2013 . Consultado el 6 de diciembre de 2013 .