Universidade Federal do Rio de Janeiro COPPE

Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia

Instituto de Matemática

 
Visualizar Meses
Visualizar Meses
Visualizar Flat
Visualizar Flat
Visualizar Semanas
Visualizar Semanas
Visualizar Dias
Visualizar Dias
Categorias
Categorias
Procurar
Procurar

Evento: 'Seminário: Vadim Lozin (University of Warwick)'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Wednesday, November 05, 2014 At 11:00
Duração: 2 Horas
Contato - Info:
Email:

O Ciclo de Seminários PESC volta a acontecer semana que vem trazendo o Prof. Vadim Lozin da University of Warwick, UK. Vadim tem forte atuação na área de algoritmos e grafos, atacando problemas clássicos e difíceis, como o de satisfatibilidade booleana (SAT) que será tema de sua palestra.

Data: 05/11 (quarta) - 11 horas
Sala: H-324B

---

Título:
Boundary properties of the Satisfiability problem

Resumo:
The satisfiability problem is known to be NP-complete in general and for many restricted instances, such as formulas with at most 3 variables per clause and at most 3 occurrences per variable, or planar formulas. The latter example refers to graphs representing satisfiability instances. These are bipartite graphs with vertices representing clauses and variables, and edges connecting variables to the clauses containing them.

Finding the strongest possible restrictions under which the problem remains NP-complete is important for at least two reasons. First, this can make it easier to establish the NP-completeness of new problems by allowing easier transformations. Second, this can help clarify the boundary between tractable and intractable instances of the problem. In this talk, we address the second issue and reveal the first boundary property of graphs representing satisfiability instances.

Short Bio:
Vadim Lozin received his Ph.D. in Theoretical Computer Science in 1995 from the University of Nizhny Novgorod, Russia. In 2000, he moved to Rutgers University (USA) and in 2007, to the University of Warwick (UK), where he now is an Associate Professor (Reader) of Mathematics. He also held a number of short-term visiting academic positions in Sweden, Portugal, Switzerland, Canada, Germany, Saudi Arabia, France. He is an author of more than 100 publications in the area of Discrete Mathematics and Theoretical Computer Science. Six Ph.D. students defended their dissertations under the direction of Vadim Lozin. He is an Associate Editor of the journal "Discrete Applied Mathematics", Managing Editor of the journal "Electronic Notes in Discrete Mathematics", and a member of the editorial board of the journal "Discussiones Mathematicae Graph Theory".


Procurar no Calendário

Powered by ExtCalendar 2

© 2017 PESC/COPPE - Programa de Engenharia de Sistemas e Computação

Cidade Universitária, Centro de Tecnologia, Bloco H, Sala 319
Caixa Postal: 68511 CEP: 21941-972 Fones: +55 21 3938-8672 / +55 21 3938-8673 Fax: +55 21 3938-8676
Rio de Janeiro - RJ - Brasil
Horário de atendimento da Secretaria: 2a. a 6a. de 7:00 às 16:00 horas (exceto feriados escolares)