Benjamín Rossman

Matemático estadounidense

Benjamin E. Rossman es un matemático y científico 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 BA en 2001 y MA 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 fue un postdoctorado en el Instituto Tecnológico de Tokio . De 2013 a 2016 fue profesor asistente en el Kawarabayashi Large Graph Project del Instituto Nacional de Informática . Para el año académico 2014-2015 fue Simons-Berkeley Research Fellow en el Simons Institute for the Theory of Computing . Fue profesor asistente en los departamentos de matemáticas y ciencias de la computación de la Universidad de Toronto hasta principios de 2019, antes de unirse a la Universidad de Duke . ^[2] En el otoño de 2018 fue científico visitante en el Simons Institute for the Theory of Computing. ^[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 derivado límites inferiores innovadores sobre la complejidad de detectar camarillas y determinar la conectividad en grafos aleatorios . Otros resultados notables incluyen teoremas de jerarquía de tamaño y profundidad para circuitos de profundidad limitada , que responden a preguntas de larga data. ^[6]

Rossman fue becario de investigación 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, Benjamin; Schulte, Wolfram (2005). "Esencia semántica de AsmL". Ciencias Informáticas Teóricas . 343 (3): 370–412. doi :10.1016/j.tcs.2005.06.017.
• Rossman, B. (2005). "Tipos positivos existenciales y preservación bajo homomorfismos". 20.º Simposio anual IEEE sobre lógica en informática (LICS' 05) . pp. 467–476. doi :10.1109/LICS.2005.16. ISBN 0-7695-2266-1.S2CID 18553513  .
• Demaine, Erik D .; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2007). "Un algoritmo de descomposición óptima para la distancia de edición de árboles". Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 4596. págs. 146–157. doi :10.1007/978-3-540-73420-8_15. ISBN 978-3-540-73419-2.
• Blass, Andreas ; Gurevich, Yuri; Rosenzweig, Dean; Rossman, Benjamin (2007). "Algoritmos interactivos de pasos pequeños II: máquinas de estados abstractas 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, Benjamin (2008). "Teoremas de preservación del homomorfismo". Revista de la ACM . 55 (3): 1–53. doi :10.1145/1379759.1379763. S2CID  306577.
• Rossman, Benjamin (2008). "Sobre la complejidad de profundidad constante de k-clique". Actas del cuadragésimo simposio anual de la 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.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2009). "Un algoritmo de descomposición óptimo para la distancia de edición de árboles". ACM Transactions on Algorithms . 6 : 1–19. arXiv : cs/0604037 . doi :10.1145/1644015.1644017. S2CID  7878119.
• Kopparty, Swastik; Rossman, Benjamin (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, Benjamin; Servedio, Rocco A.; Tan, Li-Yang (2015). "Un teorema de jerarquía de profundidad de caso promedio para circuitos booleanos". 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . 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 Matemática
4. Rossman, Benjamin (2010). Complejidad de casos promedio en la detección de camarillas (tesis doctoral, Massachusetts Institute of Technology) (tesis). Massachusetts Institute of Technology. hdl :1721.1/62441.
5. "Benjamin Rossman". Instituto Simons de Teoría de la Computación, campus de la Universidad de California en 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, Benjamin (2019). "Límites inferiores para el 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 para el isomorfismo de subgrafos – Benjamin Rossman – ICM2018". Rio ICM2018website=YouTube.
• "Tiempo polinomial sin elección - Ben Rossman". YouTube . Instituto de Estudios Avanzados.