Nicollas Mocelin Sdroievski

Apresentação

Sou professor do Departamento de Informática (DInf) da Universidade Federal do Paraná (UFPR) desde 2026. Durante o ano de 2025, fui professor da Universidade Estadual do Paraná (UNESPAR).

Formação

Doutor em Ciência da Computação (Computer Sciences PhD) pela University of Wisconsin-Madison (2024).

Mestre em Ciência da Computação (Computer Sciences MS) pela University of Wisconsin-Madison (2022).

Mestre em Informática pela Universidade Federal do Paraná (2018).

Bacharel em Sistemas de Informação pela Universidade Tecnológica Federal do Paraná (2016).

Pesquisa

Confira aqui as minhas publicações.

Meu foco de pesquisa é a Teoria da Computação, em especial a área de Complexidade Computacional. O objetivo da Complexidade Computacional é compreender os recursos necessários para resolver problemas computacionais. Minha pesquisa investiga diferentes tipos de recursos, como tempo, memória, comunicação e aleatoriedade.

Uma subárea de interesse é a desaleatorização, que visa simular algoritmos probabilísticos de maneira determinística com os mesmos recursos ou com poucos recursos a mais (como tempo e espaço). A área é fortemente conectada a limitantes inferiores: resultados que estabelecem a impossibilidade de resolver determinados problemas computacionais com recursos limitados.

Minha pesquisa recente investigou a complexidade de aleatoriedade de protocolos interativos do tipo Arthur-Merlin, conectando a desaleatorização da classe AM com diferentes tipos de limitantes inferiores e obtendo equivalências em alguns casos. Também me interesso nas seguintes questões:

Algoritmos limitados em espaço e catalíticos. Algoritmos catalíticos possuem uma memória principal bastante limitada, além de acesso a uma memória muito maior que já está ocupada (como um HD de computador em uso). O algoritmo pode modificar a memória adicional, porém deve restaurá-la à sua configuração inicial no fim da computação. Algoritmos catalíticos são mais poderosos do que pode parecer a princípio. Como um exemplo, para algoritmos deste tipo, vale uma igualdade semelhante a P = NP.
Meta-complexidade. Qual a complexidade de problemas computacionais que são, por si próprios, sobre complexidade? Um exemplo clássico de problema nessa sub-área é o problema de minimização de circuitos (MCSP de Minimum Circuit Size Problem): dada a tabela verdade de uma função Booleana, qual o tamanho do menor circuito que a computa?
Criptografia. A Criptografia também tem conexões fortes com limitantes inferiores. De fato, se P = NP, então boa parte dos protocolos criptográficos usados atualmente não são seguros. Me interesso em compreender melhor e enfraquecer as hipóteses necessárias para provar a segurança de protocolos criptográficos.

Disciplinas Atuais

Introdução à Teoria da Computação (CI1059).
Algoritmos e Teoria dos Grafos (CI1065).
Página do professor Renato.
(Temporário) Métodos Numéricos (CI181 ELTA)

Página do professor Murilo (com slides).