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 α = M / N 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.