matemático americano
Michael Ezra Saks es un matemático estadounidense. Actualmente es el director del Departamento de Matemáticas de la Universidad de Rutgers (2017–) y desde 2006 hasta 2010 fue director del Programa de Posgrado en Matemáticas de la Universidad de Rutgers . Saks recibió su doctorado. del Instituto de Tecnología de Massachusetts en 1980 después de completar su disertación titulada Propiedades de dualidad de sistemas de conjuntos finitos [1] bajo la dirección de su asesor Daniel J. Kleitman .
Puede encontrar una lista de sus publicaciones y colaboraciones en DBLP . [2]
En 2016 se convirtió en miembro de la Association for Computing Machinery . [3] [4]
Investigación
La investigación de Saks en teoría de la complejidad computacional , combinatoria y teoría de grafos ha contribuido al estudio de los límites inferiores en la teoría del orden , la computación aleatoria y el equilibrio espacio-temporal .
En 1984, Saks y Jeff Kahn demostraron que existe un límite inferior teórico de la información estricto para clasificar información parcialmente ordenada hasta una constante multiplicativa. [5]
En [1] se demostró el primer límite inferior superlineal para el problema de la transmisión ruidosa. En un modelo de transmisión ruidoso, a los procesadores se les asigna un bit de entrada local . Cada procesador puede realizar una transmisión ruidosa a todos los demás procesadores donde los bits recibidos pueden invertirse de forma independiente con una probabilidad fija. El problema es que el procesador determine alguna función . Saks y col. demostró que un protocolo existente de Gallager era de hecho óptimo mediante una reducción de un árbol de decisión ruidoso generalizado y produjo un límite inferior en la profundidad del árbol que aprende la entrada. [6]
En 2003, P. Beame, Saks, X. Sun y E. Vee publicaron la primera compensación de límite inferior espacio-temporal para el cálculo aleatorio de problemas de decisión. [7]
Posiciones
Saks ocupa puestos en los siguientes consejos editoriales de revistas:
Publicaciones Seleccionadas
- Borodin, Allan; Linial, Nathan; Saks, Michael E. (1 de octubre de 1992). "Un algoritmo en línea óptimo para un sistema de tareas métrico". Revista de la ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . ISSN 0004-5411. S2CID 18783826.
- Fredman, M.; Saks, M. (1 de febrero de 1989). "La complejidad de la sonda celular de las estructuras de datos dinámicas". Actas del vigésimo primer simposio anual de ACM sobre teoría de la informática - STOC '89 . Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 345–354. doi : 10.1145/73007.73040 . ISBN 978-0-89791-307-2. S2CID 13470414.
- Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francisco (1 de mayo de 2005). "Un algoritmo de tiempo exponencial mejorado para k-SAT". Revista de la ACM . 52 (3): 337–364. doi :10.1145/1066100.1066101. ISSN 0004-5411.
- Goldberg, Andrés V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrés (1 de mayo de 2006). "Subastas competitivas". Juegos y comportamiento económico . Mini Número Especial: Diseño del Mercado Electrónico. 55 (2): 242–269. doi :10.1016/j.geb.2006.02.003. ISSN 0899-8256.
- Saks, Michael; Zaharoglou, Fotios (1 de enero de 2000). "El acuerdo k-Set sin espera es imposible: la topología del conocimiento público". Revista SIAM de Computación . 29 (5): 1449-1483. doi :10.1137/S0097539796307698. ISSN 0097-5397.
- Saks, Michael; Wigderson, Avi (octubre de 1986). "Árboles de decisión booleanos probabilísticos y la complejidad de evaluar árboles de juegos". 27º Simposio Anual sobre Fundamentos de la Informática (SFCS 1986) . págs. 29-38. doi :10.1109/SFCS.1986.44. ISBN 0-8186-0740-8. S2CID 6130392.
- Saks, Michael; Yu, Lan (5 de junio de 2005). "Una monotonicidad débil es suficiente para la veracidad en dominios convexos". Actas de la sexta conferencia ACM sobre comercio electrónico . CE '05. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 286–293. doi :10.1145/1064009.1064040. ISBN 978-1-59593-049-1. S2CID 2135397.
Referencias
- ^ Saks, Michael Ezra (1980). Propiedades de dualidad de sistemas de conjuntos finitos (tesis doctoral). Instituto de Tecnología de Massachusetts . OCLC 7447661.
- ^ Michael E. Saks en el servidor de bibliografía DBLP
- ^ Personal de Cacm (marzo de 2017), "ACM reconoce nuevos becarios", Comunicaciones de la ACM , 60 (3): 23, doi :10.1145/3039921, S2CID 31701275.
- ^ "Destinatarios". premios.acm.org . Consultado el 1 de julio de 2018 .
- ^ Kahn, J.; Saks, M. (1984). "Cada poset tiene una buena comparación". Actas del decimosexto simposio anual de ACM sobre teoría de la informática - STOC '84 . pag. 299. doi : 10.1145/800057.808694. ISBN 978-0897911337. S2CID 17374296.
- ^ Gallager, RG (1988). "Encontrar la paridad en redes de transmisión simples". Transacciones IEEE sobre teoría de la información . 34 (2): 176–180. CiteSeerX 10.1.1.422.3311 . doi :10.1109/18.2626.
- ^ Beame, P.; Saks, M.; Sol, X.; Vee, E. (2003). "Límites inferiores de compensación tiempo-espacio para el cálculo aleatorio de problemas de decisión". Revista de la ACM . 50 (2): 154. CiteSeerX 10.1.1.16.8696 . doi :10.1145/636865.636867. S2CID 9459178.
enlaces externos