Benjamín Rossman

matemático americano

Benjamin E. Rossman es un matemático e informático teórico estadounidense, especializado en teoría de la complejidad computacional . ^[1] Actualmente es profesor asociado de informática y matemáticas en la Universidad de Duke .

Biografía

Se graduó de la Universidad de Pensilvania con una licenciatura en 2001 y una maestría en 2002. ^[2] Recibió en 2011 su doctorado. con el asesor Madhu Sudan del MIT con la tesis Average-Case Complexity of Detecting Cliques . ^{[3] [4]} De 2010 a 2013, Rossman realizó un postdoctorado en el Instituto de Tecnología de Tokio . De 2013 a 2016 fue profesor asistente en el Proyecto Kawarabayashi Large Graph del Instituto Nacional de Informática . Durante el año académico 2014-2015 fue becario de investigación Simons-Berkeley en el Instituto Simons de Teoría de la Computación . Fue profesor asistente en los departamentos de matemáticas e informática de la Universidad de Toronto hasta principios de 2019, antes de incorporarse a la Universidad de Duke . ^[2] En el otoño de 2018 fue científico visitante en el Instituto Simons de Teoría de la Computación. ^[5]

Su investigación busca cuantificar los recursos mínimos necesarios para resolver problemas básicos en modelos combinatorios como los circuitos booleanos . A través de técnicas creativas basadas en la lógica y el método probabilístico, Ben ha obtenido límites inferiores innovadores en la complejidad de detectar camarillas y determinar la conectividad en gráficos aleatorios . Sus otros resultados notables incluyen teoremas de jerarquía de tamaño y profundidad para circuitos de profundidad limitada , respondiendo preguntas de larga data. ^[6]

Rossman fue becario de investigación de Sloan durante el año académico 2017-2018. Ganó el Premio Aisenstadt en 2018. ^[6] Fue orador invitado en el Congreso Internacional de Matemáticos en 2018 en Río de Janeiro . ^[7]

Publicaciones Seleccionadas

• Gurevich, Yuri ; Rossman, Benjamín; Schulte, Wolfram (2005). "Esencia semántica de AsmL". Informática Teórica . 343 (3): 370–412. doi : 10.1016/j.tcs.2005.06.017.
• Rossman, B. (2005). "Tipos existenciales positivos y preservación bajo homomorfismos". 20.º Simposio anual del IEEE sobre lógica en informática (LICS' 05) . págs. 467–476. doi :10.1109/LICS.2005.16. ISBN 0-7695-2266-1. S2CID  18553513.
• Demaine, Erik D .; Moisés, Shay; Rossman, Benjamín; Weimann, Oren (2007). "Un algoritmo de descomposición óptimo para la distancia de edición de árboles". Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 4596, págs. 146-157. doi :10.1007/978-3-540-73420-8_15. ISBN 978-3-540-73419-2.
• Blas, Andrés ; Gurevich, Yuri; Rosenzweig, decano; Rossman, Benjamín (2007). "Algoritmos interactivos de pequeños pasos II: máquinas de estados abstractos y el teorema de caracterización". Métodos lógicos en informática . 3 (4). arXiv : 0707.3789 . doi :10.2168/LMCS-3(4:4)2007. S2CID  99659.
• Rossman, Benjamín (2008). "Teoremas de preservación del homomorfismo". Revista de la ACM . 55 (3): 1–53. doi :10.1145/1379759.1379763. S2CID  306577.
• Rossman, Benjamín (2008). "Sobre la complejidad constante de k-clique". Actas del cuadragésimo simposio anual ACM sobre teoría de la computación - STOC 08 . págs. 721–730. doi :10.1145/1374376.1374480. ISBN 9781605580470. S2CID  9362397.
• Demaine, Erik D.; Moisés, Shay; Rossman, Benjamín; Weimann, Oren (2009). "Un algoritmo de descomposición óptimo para la distancia de edición de árboles". Transacciones ACM sobre algoritmos . 6 : 1–19. arXiv : cs/0604037 . doi :10.1145/1644015.1644017. S2CID  7878119.
• Kopparty, Swastika; Rossman, Benjamín (2011). "El exponente de dominación del homomorfismo". Revista europea de combinatoria . 32 (7): 1097-1114. arXiv : 1004.2485 . doi :10.1016/j.ejc.2011.03.009. S2CID  6624366.
• Rossman, Benjamín; Servedio, Rocco A.; Tan, Li-Yang (2015). "Un teorema de jerarquía de profundidad de caso promedio para circuitos booleanos". 56º Simposio Anual del IEEE de 2015 sobre fundamentos de la informática . págs. 1030-1048. arXiv : 1504.03398 . doi :10.1109/FOCS.2015.67. ISBN 978-1-4673-8191-8. S2CID  7722713.

Referencias

1. "Benjamin Rossman, profesor asociado de informática". Universidad de Duke .
2. "Benjamin Rossman, CV" (PDF) . Universidad de Toronto .
3. Benjamin E. Rossman en el Proyecto de genealogía de matemáticas
4. Rossman, Benjamín (2010). Complejidad de caso promedio de la detección de camarillas (Tesis doctoral, Instituto de Tecnología de Massachusetts) (Tesis). Instituto de Tecnología de Massachusetts. hdl :1721.1/62441.
5. "Benjamín Rossman". Instituto Simons de Teoría de la Computación, campus de UC Berkeley . 11 de abril de 2014.
6. "Premio André Aisenstadt de Matemáticas 2018, Ben Rossman (Universidad de Toronto)". Centro de Investigaciones Matemáticas .
7. Rossman, Benjamín (2019). "Límites inferiores del isomorfismo de subgrafos". En Boyan, Sirakov; De Souza, Paulo Ney; Viana, Marcelo (eds.). Actas del Congreso Internacional de Matemáticos (ICM 2018) . vol. 4. págs. 3425–3446. doi :10.1142/9789813272880_0187. ISBN 978-981-327-287-3. S2CID  19175568.

enlaces externos

• "Límites inferiores del isomorfismo de subgrafos - Benjamin Rossman - ICM2018". Río ICM2018website=YouTube.
• "Tiempo polinomial sin elección - Ben Rossman". YouTube . Instituto de Estudios Avanzados.