Benjamin Rossman - Benjamin Rossman

Benjamin E. Rossman (nascido em 10 de fevereiro de 1980) é um matemático americano e cientista da computação teórico, especializado em teoria da complexidade computacional . Atualmente é professor associado de ciência da computação na Duke University .

Ele se formou na University of Pennsylvania com BA em 2001 e MA em 2002. Ele recebeu em 2011 seu Ph.D. com o conselheiro Madhu Sudan do MIT com a tese Average-Case Complexity of Detecting Cliques . De 2010 a 2013, Rossman fez pós-doutorado no Instituto de Tecnologia de Tóquio . De 2013 a 2016 foi professor assistente no Projeto Grande Gráfico Kawarabayashi do Instituto Nacional de Informática . Para o ano letivo de 2014-2015, ele foi Simons-Berkeley Research Fellow no Simons Institute for the Theory of Computing . Ele foi professor assistente nos departamentos de matemática e ciência da computação da Universidade de Toronto até o início de 2019, antes de ingressar na Duke University . No outono de 2018, ele foi um professor visitante no Simons Institute for the Theory of Computing.

Sua pesquisa busca quantificar os recursos mínimos necessários para resolver problemas básicos em modelos combinatórios como os circuitos booleanos . Por meio de técnicas criativas baseadas na lógica e no método probabilístico, Ben derivou limites inferiores inovadores sobre a complexidade da detecção de cliques e da determinação da conectividade em gráficos aleatórios . Seus outros resultados notáveis ​​incluem teoremas de hierarquia de tamanho e profundidade para circuitos de profundidade limitada , respondendo a perguntas de longa data.

Rossman foi Sloan Research Fellow no ano acadêmico de 2017–2018. Ele ganhou o Prêmio Aisenstadt em 2018. Foi palestrante convidado no Congresso Internacional de Matemática de 2018 no Rio de Janeiro .

Publicações selecionadas

  • Gurevich, Yuri ; Rossman, Benjamin; Schulte, Wolfram (2005). "Essência semântica de AsmL" . Ciência da Computação Teórica . 343 (3): 370–412. doi : 10.1016 / j.tcs.2005.06.017 .
  • Rossman, B. (2005). "Tipos existenciais positivos e preservação sob homomorfismos". 20º Simpósio Anual do IEEE em Lógica em Ciência da Computação (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). "Um algoritmo de decomposição ideal para distância de edição de árvore". Autômatos, Linguagens e Programação . Notas de aula em Ciência da Computação. 4596 . pp. 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 interativos de pequeno passo II: máquinas de estado abstratas e o teorema de caracterização". Métodos Lógicos em Ciência da Computação . 3 (4). arXiv : 0707.3789 . doi : 10.2168 / LMCS-3 (4: 4) 2007 . S2CID  99659 .
  • Rossman, Benjamin (2008). "Teoremas de preservação do homomorfismo". Jornal do ACM . 55 (3): 1–53. doi : 10.1145 / 1379759.1379763 . S2CID  306577 .
  • Rossman, Benjamin (2008). "Sobre a complexidade de profundidade constante do k-clique". Anais do quadragésimo simpósio anual da ACM em Teoria da Computação - STOC 08 . p. 721. doi : 10.1145 / 1374376.1374480 . ISBN 9781605580470. S2CID  9362397 .
  • Rossman, Benjamin (2008). "Teoremas de preservação do homomorfismo". Jornal do ACM . 55 (3): 1–53. doi : 10.1145 / 1379759.1379763 . S2CID  306577 .
  • Demaine, Erik D .; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2009). "Um algoritmo de decomposição ideal para a distância de edição da árvore". Transações ACM em Algoritmos . 6 : 1-19. arXiv : cs / 0604037 . doi : 10.1145 / 1644015.1644017 . S2CID  7878119 .
  • Kopparty, Swastik; Rossman, Benjamin (2011). “O expoente da dominação do homomorfismo”. European Journal of Combinatorics . 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). "Um Teorema da Hierarquia de Profundidade de Caso Médio para Circuitos Booleanos". 2015 IEEE 56º Simpósio Anual sobre Fundamentos de Ciência da Computação . pp. 1030–1048. arXiv : 1504.03398 . doi : 10.1109 / FOCS.2015.67 . ISBN 978-1-4673-8191-8. S2CID  7722713 .

Referências

  1. ^ "Benjamin Rossman, Professor Associado de Ciência da Computação" . Duke University .
  2. ^ a b "Benjamin Rossman, CV" (PDF) . Universidade de Toronto .
  3. ^ Benjamin E. Rossman no projeto da árvore genealógica da matemática
  4. ^ Rossman, Benjamin (2010). "Complexidade de caso médio de detecção de cliques (dissertação de doutorado, Massachusetts Institute of Technology)". hdl : 1721,1 / 62441 . Citar diário requer |journal=( ajuda )
  5. ^ "Benjamin Rossman" . Instituto Simons de Teoria da Computação, campus da UC Berkeley .
  6. ^ a b "Prêmio 2018 de André Aisenstadt no recebedor da matemática, Ben Rossman (Universidade de Toronto)" . Centre de Recherches Mathématiques .
  7. ^ Rossman, Benjamin (2019). "Limites inferiores para isomorfismo subgráfico" . Em Boyan, Sirakov; De Souza, Paulo Ney; Viana, Marcelo (eds.). Anais do Congresso Internacional de Matemáticos (ICM 2018) . vol. 4. pp. 3425–3446. doi : 10.1142 / 9789813272880_0187 . ISBN 978-981-327-287-3. S2CID  19175568 . |volume=tem texto extra ( ajuda )

links externos