Prof.
Uriel Feige
(Weizmann Institute)
24/05/2012, 09:00
A 3SAT algorithm needs to correctly decide for every
3CNF formula whether it is satisfiable or not. We do not
expect a 3SAT algorithm to run in polynomial time,
because 3SAT is NP-hard. Nevertheless, a 3SAT
algorithm may run in polynomial time on a substantial
fraction of all 3SAT instances. Of particular interest to
this talk are random instances of 3CNF formulas with
very large...
Prof.
Tomi Janunen
(Aalto University)
24/05/2012, 09:45
Propositional satisfiability (SAT) solvers provide a promising
computational platform for declarative problem solving. Over
the years, a great variety of benchmark problems has
emerged to help with the systematic evaluation of SAT
solvers under development. Both highly structural and
random benchmark instances are used and the
performance of SAT solvers on such instances depends...
Prof.
Elitza Maneva
(University of Barcelona)
24/05/2012, 10:45
The Weisfeiler-Lehman (WL) algorithm is an iterative
algorithm for certifying that two graphs are not isomorphic.
At every iteration a label is generated for each vertex based
on the mutliset of labels of its neighbors at the previous
iteration. The starting label is the degree of the vertex.
When a fixed point is reached the multisets of labels of the
vertices of the two graphs...
Dr
Chi Ho Yeung
(Aston University)
24/05/2012, 11:30
Optimal paths connecting randomly selected node pairs, as
well as multiple nodes and their fixed routers are studied
analytically in the presence of non-linear overlap cost that
penalizes congestion or encourages aggregation. Routing
becomes more difficult as the number of selected nodes
increases and exhibits interesting physical phenomena such
as ergodicity breaking. The ground...
Prof.
Dmitris Achlioptas
(CTI)
24/05/2012, 14:00
We consider random CNF formulas consisting of 2- and
3-clauses, also known as the random (2+p)-SAT model.
Such mixtures arise naturally in the execution of
satisfiability algorithms on random 3-CNF formulas and
their properties are closely connected to algorithmic
performance. It is known that such mixtures are
satisfiable as long as r_2 < 1 and r_3 < 2/3, where r_k is
the ratio...
Prof.
Stefan Szeider
(Vienna University of Technology)
24/05/2012, 15:15
Parameterized complexity is a new framework for the
theoretical analysis of computational problems. It
considers -- in addition to the problem input size -- a
secondary measurement, the parameter. The parameter
can represent a qualitative aspect of the input and
indicate how well the input is structured. This two-
dimensional setting admits a more fine-grained worst-
case...
