演讲人： Mario Szegedy Rutgers University
时间： 2010-10-14 14:00-2010-10-14 15:00
地点：FIT 1-222
内容：

Beck's early work gave an Efficient Version of the Variable Version of the Lovasz Local Lemma (LLL), but with compromised parameters. This was followed by several improvements (Noga Alon, Artur Czumaj and Christian Scheideler, Michael Molloy and Bruce Reed, Aravind Srinivasan). Most recently Moser and Moser and Tardos obtained asymptotically optimal results (in terms of the maximal degree), employing a remarkable and very natural argument.

As for the original (non-algorithmic, non-variable) version of LLL, Shearer gives the exact criterion when LLL applies. For a dependency structure $G$ let Shearer(G) be the set of those vectors $p=p_{1},\ldots,p_{n}$ of probabilities for which in every setting the LLL applies. We show that whenever $p\in \Shearer(G)/(1+\epsilon)$, the TM algorithm runs in expected time at most $n /\epsilon$. Thus, whenever LLL holds, it can be made efficient, not only asymptotically, and for equal probabilities as in TM, but always.

We prove this sharp statement, which improves upon the MT result, without compromising the elegance of their argument. We uncover new mathematics that highlights the connection between the efficient and non-efficient versions of LLL. The central object is a matrix associated with the independent sets of the dependency graph.

个人简介:

Mario Szegedy is a Hungarian-born computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science from the University of Chicago.

Szegedy's research areas include complexity theory, combinatorics and quantum computing.

He was awarded the Gödel Prize twice in 2001 and 2005 for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data.