Seminář z výpočetní složitosti

 Pavel Pudlák, Jiří Sgall

Pudlak P., Paturi R., Zane F.:  Satisfiability coding lemma
in Proc. 38-th FOCS, IEEE Computer Society 1997, pp. 566-574
(referuje Martin Pergel)

Putovaní po exponenciálních algoritmech zakončíme u domácího zdroje a problému splnitelnosti. R. Beigel, D. Epstein: 3-coloring in time O(x_i^n)
(referuje Petr Kučera)

Budeme referovat dva články uvedených autorů s x_1=1.3446 a x_2=1.3289.

J. M. Robson: Algorithms for Maximum Independent Sets
(referuje Emil Jerabek)

An algorithm is presented which finds (the size of) a maximum independent set of an n vertex graph in tim O(2^(0.276 n)) improving on a previous bound of O(2^(n/3)).

N. Karmarkar and R. M. Karp: An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem
(referuje Tomas Tichy)

We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem, using a subroutine to solve a certain linear programming relaxation of the problem. Our main results is: There is a polynomial-time algorithm A such that A(I)<=OPT(I)+O(log^2(OPT(I))).

Jan Kára, Daniel Kráľ: Optimal Free Binary Decision Diagrams for Computation of EAR_n
(referuje Daniel Kral)

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested during the computation at most once. The function EAR_n is a Boolean function on n x n Boolean matrices; EAR_n(M)=1 iff the matrix M contains two equal adjacent rows. We prove that the size of optimal FBDDs computing EAR_n is 2^{Theta(log^2 n)}.

V. Guruswami, S. Khanna: On the Hardness of 4-coloring a 3-colorable Graph
(referuje Jiri Hanika)

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does.

T. Hofmeister, U. Schoening, R. Schuler, O. Watanabe: A probabilistic 3-SAT algorithm further imporved
(referuje Tomáš Ebenlendr)

Probereme Schoeningův algoritmus pro 3-SAT pracující v průměrném čase cca (4/3)^n a jeho zlepšení z tohoto článku.

Madhu Sudan: List decoding: Algorithms and applications
(referuje Petr Kučera)

Over years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of "list-decoding" for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory.