-
Prof. Uriel Feige (Weizmann Institute)24/05/2012, 09:00A 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...Go to contribution page
-
Prof. Tomi Janunen (Aalto University)24/05/2012, 09:45Propositional 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...Go to contribution page
-
Prof. Elitza Maneva (University of Barcelona)24/05/2012, 10:45The 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...Go to contribution page
-
Dr Chi Ho Yeung (Aston University)24/05/2012, 11:30Optimal 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...Go to contribution page
-
Prof. Dmitris Achlioptas (CTI)24/05/2012, 14:00We 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...Go to contribution page
-
Prof. Stefan Szeider (Vienna University of Technology)24/05/2012, 15:15Parameterized 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...Go to contribution page
Choose timezone
Your profile timezone: