Guilhem Semerjian: "Random Constraint Satisfaction Problems, Classical and Quantum Results"

Guilhem Semerjian visited the Quantum AI Lab at Google LA to give a talk on "Random Constraint Satisfaction Problems, Classical and Quantum Results". This talk took place on May 29, 2014. Abstract: In the 90's numerical simulations have unveiled interesting properties of random ensembles of constraint satisfaction problems (satisfiability and graph coloring in particular). When a parameter of the ensemble (the density of constraints per variable) increases the probability of a satisfying instance drops abruptly from 1 to 0 in the large size limit. This threshold phenomenon has motivated a lot of research activity in theoretical computer science and in mathematics. In addition non-rigorous methods borrowed from theoretical physics (more precisely from mean-field spin glasses) have been applied to such problems, yielding a series of new results, including quantitative conjectures on the location of the satisfiability threshold and a much more detailed description of the structure of the satisfiable phase. I will survey some of these results, and their extensions to the quantum case where a transverse field is added to these classical Hamiltonians. Bio: Guilhem Semerjian has applied techniques developed in statistical mechanics to interdisciplinary problems arising at the frontier of theoretical computer science and discrete mathematics, in particular satisfaction of random constraint satisfaction problems. He has also been interested in the effect of quantum fluctuations on these problems, within the perspective of adiabatic quantum computing.