Invited Talks
We are proud to present the invited speakers of CASC conference:
-
George Labahn, Professor in the David R. Cheriton School of Computer Science,
University of Waterloo, Ontario, Canada
Title of the talk: Normal Forms for Integer Matrices
Abstract: Normal forms for integer matrices, such as Hermite and Smith
normal forms, have a long history both in terms of algorithms for
computation and uses in applications. In this talk we discuss a number
of algorithms including two recent approaches for fast Smith normal form
computation along a new algorithm for computation of the Hermite normal
form.
This is joint work with Stavros Birmpilis and Arne Storjohann
-
Roberto Mulet, Professor at the University of Havana
Title of the talk: On the performance of local search algorithms for K-SAT problems in random graphs
Abstract: K-SAT is one of the most studied NP-complete problems. Early this century a new version
of this problem received a lot of attention. In this version the K-SAT is defined through a bipartite random graph.
Variables and logical clauses form the nodes of the graph and they are connected if one variable belongs to one clause.
The main parameter of the problem is
the ratio between the number of clauses
and the number of variables. When α is small the problem is satisfiable, when α is large it is unsatisfiable.
However, for intermediate values of α the problem becomes statistically hard.
Theoretical results, obtained using techniques from the statistical physics of disordered systems, predict a range of α
in which most K-SAT problems are still satisfiable, but where local search algorithms can't find
a solution. In this talk I will review these results and test them showing the actual performance of three different
local search algorithms on this problem. I will conclude by presenting analytical approximations, derived from
a microscopic theory, for the dynamics of these algorithms.