Research Group on Natural Computing

Speaker: Gabriel Istrate, Ph.D.
Theoretical Computer Science Group
West University of Timisoara (Romania)
The eAustria Research Institute

Title: Phase Transitions in Combinatorial Optimization: a personal perspective.

Abstract: Phase transitions in combinatorial optimization are an approach to the analysis of combinatorial optimization problems that has evolved into an interdisciplinary area, at the crossroads of Complex Systems Theory, Theoretical Computer Science and Artificial Intelligence. Methods from Statistical Physics have led to spectacular advances in the area of satisfiability solving. They have also provided intuition for the rigorous analysis of random instances of combinatorial optimization problems. In this overview presentation I will present an introduction to this exciting research direction. Some of the topics I will deal with include:

• 1. Classification of thresholds and rigorous results on the location of phase transitions in random CSP.
• 2. The connection between first-order phase transitions and exponential bounds for resolution.
• 3. The geometric structure of solution space of random CSP.

Information:

• Date: Wednesday, 18-06-2014
• Time: 17h.
• Place: Seminar room H1.50 (First floor, Módulo H, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla)
• Language: English

Organized by: Research Group on Natural Computing