Michael Saks (matemático)

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] ${\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 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:

• Revista SIAM de Computación , Editor Asociado
• Combinatoria , miembro del consejo editorial
• Revista de teoría de grafos , miembro del consejo editorial
• Matemática Aplicada Discreta , miembro del Consejo Editorial

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

1. Saks, Michael Ezra (1980). Propiedades de dualidad de sistemas de conjuntos finitos (tesis doctoral). Instituto de Tecnología de Massachusetts . OCLC  7447661.
2. Michael E. Saks en el servidor de bibliografía DBLP
3. Personal de Cacm (marzo de 2017), "ACM reconoce nuevos becarios", Comunicaciones de la ACM , 60 (3): 23, doi :10.1145/3039921, S2CID  31701275.
4. "Destinatarios". premios.acm.org . Consultado el 1 de julio de 2018 .
5. 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.
6. 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. 
7. 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

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