Sepehr Assadi, que ingressará na Cheriton School of Computer Science como professor associado em julho de 2023, é um dos 125 beneficiários da bolsa Sloan Research Fellowship 2023 da Alfred P. Sloan Foundation. Atualmente, ele é professor assistente no Departamento de Ciência da Computação da Rutgers University e membro do grupo de Teoria da Computação.
Fundadas em 1955 e concedidas anualmente, as Sloan Research Fellowships reconhecem pesquisadores cuja criatividade, inovação e realizações em pesquisa os diferenciam como a próxima geração de líderes científicos. Em reconhecimento ao seu desempenho diferenciado, os premiados recebem uma bolsa de dois anos no valor de US$ 75.000 para continuar suas pesquisas.
“As Sloan Research Fellowships são um prêmio excepcionalmente prestigioso para pesquisadores em início de carreira”, disse Raouf Boutaba, professor e diretor da Cheriton School of Computer Science. “Estamos satisfeitos por Sepehr estar entre os premiados deste ano e ainda mais satisfeitos por ele estar ingressando na Cheriton School of Computer Science, trazendo sua experiência em algoritmos sublineares para nosso grupo de pesquisa de Algoritmos e Complexidade.”
“É um grande privilégio e uma honra ser Sloan Research Fellow, e estou ansioso para aproveitar esta oportunidade para continuar minha pesquisa no desenvolvimento de bases teóricas sólidas que sustentam os problemas da ciência da computação do mundo real”, disse o professor Assadi. “Também estou emocionado com o apoio incrível que recebi do número crescente de mentores maravilhosos que tive ao longo da minha carreira, incluindo os indicados para este prêmio, e sou grato por seu apoio contínuo.”
O professor Assadi estuda os fundamentos teóricos da análise de big data. Sua pesquisa se concentra em algoritmos sublineares e limites inferiores em vários modelos de computação para processamento de conjuntos de dados massivos, como streaming, comunicação distribuída, computação massivamente paralela e algoritmos de tempo sublinear. De forma mais ampla, ele explora a teoria algorítmica dos grafos, a complexidade da comunicação, os algoritmos online e a teoria algorítmica dos jogos.
A pesquisa do Professor Assadi resultou em 74 publicações com um índice h cumulativo de 23 até o momento. Destes artigos, 55 foram apresentados nas principais conferências de ciência da computação, incluindo 21 nas principais conferências em algoritmos e teoria da complexidade, nomeadamente o Simpósio ACM sobre Teoria da Computação, o Simpósio IEEE sobre Fundamentos da Ciência da Computação e o Simpósio ACM-SIAM sobre Algoritmos Discretos.
Suas publicações receberam vários prêmios de melhor artigo em conferências teóricas e aplicadas de ciência da computação, entre elas a Conferência sobre Economia da Web e da Internet em 2015, o Simpósio ACM sobre Paralelismo e Arquiteturas em 2017, o Simpósio ACM-SIAM sobre Algoritmos Discretos em 2019, e o Simpósio Internacional de Computação Distribuída em 2020.
Mais sobre a pesquisa do Professor Assadi
O campo dos algoritmos sublineares abrange o estudo de algoritmos de espaço sublinear que possuem uma quantidade limitada de memória disponível durante a computação, bem como algoritmos de tempo sublinear cujo tempo de execução deve ser significativamente menor que o tamanho de sua entrada. Essas duas grandes categorias de algoritmos incluem algoritmos de streaming, algoritmos de esboço, testadores de propriedades, algoritmos locais, entre muitos outros. Algoritmos sublineares têm sido aplicados em todas as áreas da ciência da computação, e compreender suas capacidades e limitações está entre os problemas práticos mais importantes na pesquisa de algoritmos atualmente. O estudo de algoritmos sublineares também produz insights fundamentais sobre a natureza da computação, e as técnicas matemáticas desenvolvidas nesta pesquisa também permitem novos avanços em muitas outras áreas teóricas da ciência da computação e da matemática.
As contribuições do Professor Assadi incluem resultados inovadores em diversos tópicos, abrangendo algoritmos de tempo sublinear e espaço sublinear que são teoricamente importantes e relevantes na prática.
Entre seus resultados mais famosos está o apresentado em “Sublinear Algorithms for (Δ + 1) Vertex Coloring”, publicação que ganhou o prêmio de melhor artigo no Simpósio ACM-SIAM de Algoritmos Discretos de 2019. Resumindo, dado um gráfico de grau Δ, é sempre possível colorir o gráfico com Δ + 1 cores e isso pode ser feito com um algoritmo simples e ganancioso que possui complexidade linear de tempo e espaço. Mas colorir gráficos com algoritmos que têm acesso apenas a uma quantidade sublinear de tempo ou espaço é muito mais desafiador. Determinar os algoritmos mais eficientes para o problema em vários modelos de algoritmos sublineares é uma das questões centrais na pesquisa de algoritmos.
O professor Assadi e seus co-autores Yu Chen e Sanjeev Khanna introduziram uma nova técnica chamada esparsificação de paleta, que usaram para obter algoritmos eficientes para o problema de coloração em vários modelos de algoritmos sublineares. Muitos desses algoritmos forneceram os primeiros limites não triviais da complexidade para coloração de vértices nos modelos de algoritmos sublineares correspondentes e, em muitos casos, esses algoritmos também se mostraram ótimos. Este resultado abriu uma nova linha de trabalho em problemas de coloração de grafos com algoritmos sublineares, e a técnica de esparsificação de paleta tem sido influente em trabalhos subsequentes em diversas áreas de pesquisa, incluindo algoritmos sublineares, computação distribuída e teoria dos grafos.
O problema de correspondência máxima é outro problema central no estudo de algoritmos sublineares e distribuídos, que avançou significativamente nos últimos anos através da pesquisa do Professor Assadi. Notavelmente, em “Randomized Composable Coresets for Matching and Vertex Cover” — uma publicação que recebeu o prêmio de melhor artigo no Simpósio ACM sobre Paralelismo em Algoritmos e Arquiteturas de 2017 — ele e Sanjeev Khanna, seu orientador de doutorado na época, apresentaram dois algoritmo redondo Map-Reduce que alcança aproximação de fator constante. Este artigo fornece não apenas resultados algorítmicos ideais e resultados de complexidade ideais, mas também obtém resultados com importância prática.
A pesquisa do professor Assadi também vai além do escopo dos algoritmos sublineares. Ele também resolveu, por exemplo, um problema aberto de longa data na teoria algorítmica dos jogos, provando a primeira lacuna entre a complexidade da comunicação de leilões verdadeiros e não-verdadeiros.
Ele também é um mentor para a próxima geração de pesquisadores. Um exemplo recente é “Deterministic Graph Coloring in the Streaming Model”, pesquisa que ele conduziu com os alunos Andrew Chen e Glenn Sun e que foi apresentada no STOC 2022, o 54º Simpósio Anual ACM sobre Teoria da Computação em junho de 2022. Seus alunos de graduação o classificam de forma consistente. como um dos melhores professores em seus programas, citando sua paixão pela ciência da computação, excelência no ensino e disposição para ajudar os alunos a dominar o material do curso.