The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                    Foundations of Computer Science Seminar

                    Seminar Room, Room 261, Ziskind Building
                          on Monday, February 7, 2011
                                 14:30 - 15:30





                                  Julia Kempe
                  Tel Aviv University and University of Paris


                                 will speak on


                         A geometric Lovasz Local Lemma
                        and applications to quantum SAT

Abstract:
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show
the existence of combinatorial objects meeting a prescribed collection of {\it
weakly dependent} criteria. We show that the LLL extends to a much more general
geometric setting, where events are replaced with subspaces and probability is
replaced with relative dimension, which allows to lower bound the dimension of
the intersection of vector spaces under certain independence conditions.

We show how our result applies directly to the quantum SAT problem. This
problem is the natural generalisation of SAT to the quantum setting and is
QMA-complete (QMA is ``quantum NP"). We then apply our results to the recently
studied model of random $k$-QSAT. Recent works have shown that the satisfiable
region extends up to a density of 1 in the large $k$ limit, where the density
is the ratio of projectors to qubits. Using our result we greatly extend the
known satisfiable region for random $k$-QSAT.

We will introduce all relevant notions of quantum information.

Joint work with Andris Ambainis (Univ. of Latvia) and Or Sattath (Hebrew
University and Tel Aviv University)