Michael Saks (matemático)

Matemático estadounidense

Michael Ezra Saks es un matemático estadounidense. Actualmente es el director del Departamento de Matemáticas de la Universidad Rutgers (2017–) y desde 2006 hasta 2010 fue director del Programa de Posgrado en Matemáticas de la Universidad Rutgers . Saks recibió su doctorado en el Instituto Tecnológico 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 .

Una lista de sus publicaciones y colaboraciones se puede encontrar 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 , el cálculo aleatorio y el equilibrio espacio-tiempo .

En 1984, Saks y Jeff Kahn demostraron que existe un límite inferior teórico de la información estricto para la clasificación bajo información parcialmente ordenada hasta una constante multiplicativa. ^[5]

En [1] se demostró el primer límite inferior superlineal para el problema de transmisión ruidosa. En un modelo de transmisión ruidosa, 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 independientemente con una probabilidad fija. El problema es que el procesador determine para alguna función . Saks et al. demostró que un protocolo existente de Gallager era de hecho óptimo mediante una reducción a partir de un árbol de decisión ruidoso generalizado y produjo un límite inferior en la profundidad del árbol que aprende la entrada. ^[6] ${\displaystyle n+1}$ ${\displaystyle P_{0},P_{1},\ldots ,P_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle P_{0}}$ ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle f}$ ${\displaystyle \Omega (n\log(n))}$

En 2003, P. Beame, Saks, X. Sun y E. Vee publicaron la primera demostración del equilibrio entre el tiempo y el espacio en el límite inferior para el cálculo aleatorio de problemas de decisión. ^[7]

Posiciones

Saks ocupa puestos en los siguientes consejos editoriales de revistas:

• Revista SIAM sobre Informática , Editor Asociado
• Combinatorica , miembro del consejo editorial
• Miembro del Consejo Editorial de la Revista de Teoría de Grafos
• Miembro del Consejo Editorial de Matemáticas Aplicadas Discretas

Publicaciones seleccionadas

• Borodin, Allan; Linial, Nathan; Saks, Michael E. (1992-10-01). "Un algoritmo en línea óptimo para el sistema de tareas métricas". Revista de la ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . ISSN  0004-5411. S2CID  18783826.
• Fredman, M.; Saks, M. (1989-02-01). "La complejidad de la sonda celular de las estructuras de datos dinámicas". Actas del vigésimo primer simposio anual de la ACM sobre teoría de la computación - STOC '89 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 345–354. doi : 10.1145/73007.73040 . ISBN. 978-0-89791-307-2. Número de identificación del sujeto  13470414.
• Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis (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, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew (1 de mayo de 2006). "Subastas competitivas". Juegos y comportamiento económico . Mininúmero especial: Diseño de mercados electrónicos. 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 de k-set sin espera es imposible: la topología del conocimiento público". Revista SIAM de informática . 29 (5): 1449–1483. doi :10.1137/S0097539796307698. ISSN  0097-5397.
• Saks, Michael; Wigderson, Avi (octubre de 1986). "Árboles de decisión probabilísticos booleanos 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. Número de identificación del sujeto  6130392.
• Saks, Michael; Yu, Lan (5 de junio de 2005). "La monotonía débil es suficiente para la veracidad en dominios convexos". Actas de la sexta conferencia de la ACM sobre comercio electrónico . EC '05. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 286–293. doi :10.1145/1064009.1064040. ISBN. 978-1-59593-049-1. Número de identificación del sujeto  2135397.

Referencias

1. Saks, Michael Ezra (1980). Propiedades de dualidad de sistemas de conjuntos finitos (tesis doctoral). Instituto Tecnológico de Massachusetts . OCLC  7447661.
2. Michael E. Saks en el servidor de bibliografía DBLP
3. Personal de Cacm (marzo de 2017), "ACM reconoce a nuevos miembros", Communications of the ACM , 60 (3): 23, doi :10.1145/3039921, S2CID  31701275.
4. "Destinatarios". awards.acm.org . Consultado el 1 de julio de 2018 .
5. Kahn, J.; Saks, M. (1984). "Cada conjunto parcial tiene una buena comparación". Actas del decimosexto simposio anual de la ACM sobre teoría de la computación - STOC '84 . p. 299. doi :10.1145/800057.808694. ISBN 978-0897911337.S2CID 17374296  .
6. Gallager, RG (1988). "Encontrar paridad en redes de difusión simples". IEEE Transactions on Information Theory . 34 (2): 176–180. CiteSeerX 10.1.1.422.3311 . doi :10.1109/18.2626. 
7. Beame, P.; Saks, M.; Sun, X.; Vee, E. (2003). "Límites inferiores de compensación espacio-temporal para el cálculo aleatorio de problemas de decisión". Journal of the ACM . 50 (2): 154. CiteSeerX 10.1.1.16.8696 . doi :10.1145/636865.636867. S2CID  9459178. 

Enlaces externos

• Michael Ezra Saks en el Proyecto de Genealogía Matemática