Nilton Volpato
Doutorando do IC-UNICAMP
Sexta-feira, 13 de abril de 2007, 15:00
Anfiteatro do NUMEC-USP
Resumo:
Nesta palestra será apresentado um algoritmo quântico para encontrar um par de elementos que é mínimo sobre uma relação de ordem definida arbitrariamente. Este algoritmo pode ser usado para resolver inúmeros problemas em geometria computacional, usando, a menos de fatores logarítmicos, um número assintoticamente ótimo de consultas a um oráculo. Este resultado oferece melhorias sobre os anteriores em vários aspectos, e fecha um problema em aberto proposto por Bahadur, Dürr et al: apresentar um limitante superior para o problema do par mais distante.