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

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, zimní semestr 2003 [Previous program, fall 2003]

14. 1. 2004 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)
Tomáš Ebenlendr: Preemptivní rozvrhování na počítačích různých rychlostí

Abstract: We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4 competitive deterministic and $e\approx 2.71$ competitive randomized online algorithms. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.
7. 1. 2004 (středa [Wednesday], 13.30, MÚ Žitná 25, 3. patro)
POZOR: Posunutý začátek semináře
M. Koucky: Co se da efektivne spocitat s pomoci Kolmogorovsky nahodnych retezcu?
 (Spolecna prace s Erikem Allenderem a Harry Buhrmanem.)

Abstrakt: Kolmogorovska slozitost je mira nahodnosti konecnych retezcu. V teto prednasce se budeme zabyvat otazkou, zda je mozne charakterizovat slozitostni tridy jako tridy problemu, ktere se daji efektivne zredukovat na mnozinu R Kolmogorovsky nahodnych retezcu. Ukazeme, ze tato otazka a odpoved na ni zavisi na vyberu univerzalniho Turingova stroje v definici Kolmogorovske slozitosti. Pro sirokou tridu redukci pak ukazeme, ze problemy redukovatelne na mnozinu R pomoci techto redukci maji malou vypocetni slozitost. Zminime tez dalsi vlastnosti mnoziny R, ktere zavisi na vyberu univerzalniho Turingova stroje.
17. 12. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)
Wojciech Jawor (UC Riverside, CA, U.S.A.): Online competitive algorithms for maximizing weighted throughput of unit jobs
(joint work with Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Ron Lavi, Jiri Sgall and Tomas Tichy)

Abstract: We will consider an online problem of scheduling unit length jobs to maximize the throughput. Each job will be specified by the release time, deadline, and weight. The goal of the algorithm will be to schedule the maxium weighted number of jobs. Each job needs to be scheduled between its release time and deadline, otherwise it brings no profit. The problem we consider is online, that is jobs arrive over time and the algorithm needs to make the decision of which job to schedule without the knowledge of the future. I will present a 1.58-competitive randomized algorithm and a 1.25 lower bound for randomized algorithms. For deterministic case I will show a 1.618 lower bound, some known 2-competitive algorithms and a brand new (2-eps)-competitive deterministic algorithm.

10. 12. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)
Andrew C.-C. Yao: On the power of quantum fingerprinting
ECCC Technical report TR2002-074
(referuje Daniel Král')
Abstract: In the simultaneous message model, two parties holding n-­bit integers x, y send messages to a third party, the referee, enabling him to compute a boolean function f(x, y). Buhrman et al [BCWW01] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short ``quantum fingerprints'' sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well­known classical case for which Omega(n^1/2 ) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R(f) = O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits su#ce for the bounded Hamming distance function, defined by f(x, y) = 1 if  and only if x and y have a constant Hamming distance d or less. 
26. 11., 3. 12. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)
René A. Sitters, Leen Stougie , Willem E. de Paepe: A Competitive Algorithm for the General 2-Server Problem
(referuje Tomáš Tichý)

Článek řeší (částečně) jeden z nejzajímavějších otevřených problémů v této oblasti. Je ke stažení na http://www.win.tue.nl/bs/spor/2003-23.pdf
Abstract: We consider the general on-line two server problem in which at each step both servers receive a request, which is a point in a metric space. One of the servers has to be moved to its request. The special case where the requests are points on the real line is known as the CNN-problem. It has been a well-known open question if an algorithm with a constant competitive ratio exists for this problem. We answer this question in the affirmative sense by providing the first constant competitive algorithm for the general two-server problem on any metric space.
12. 11., 19. 11. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)
Nathan Segerlind, Sam Buss and Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. FOCS 2002.
(referuje Emil Jeřábek)

Článek je ke stažení na http://www-cse.ucsd.edu/users/russell/resk.ps

Abstract: We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to DNFs with small conjunctions. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution which works with k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of k + 1.

5. 11. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25)

T.S. Jayram, S. Khot, R. Kumar, and Y. Rabani. Cell-Probe Lower Bounds for the Partial Match Problem. STOC'03.
(referuje Petr Kučera)

Článek je ke stažení na http://www.cs.technion.ac.il/~rabani/pss/Publications/JayramKKR02.ps.gz

Abstract:  In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem  Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem. This is an exponential improvement over the previously known lower bounds.

22. 10., 29. 10. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)

Anna Gál and Peter Bro Miltersen: The cell probe complexity of succinct data structures. ICALP 2003, pp. 332-344.
(referuje Martin Pergel)

Článek byl oceněn jako nejlepší na letošním ICALPu. Je ke stažení na http://www.daimi.au.dk/~bromille/Papers/succinct.pdf

Abstract: We show lower bounds in the cell probe model for the redundancy vs. query time tradeoff of solutions to static data structure problems.
15. 10. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)

Jiří Sgall: O asymetrickém problému obchodního cestujícího

Budeme refereovat následující článek s mírným vylepšením. Jedná se o zvláštní variantu problému obchodního cestujícího, kdy vzdálenost není symetrická a navíc trojúhelníková nerovnost platí v zesílené podobě.

Markus Bläser: An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. ICALP 2003: 157-163.
8. 10. 2003 (středa [Wednesday], 13.00, MÚ Žitná 25, 3. patro)

Pavel Pudlák: O jednom výpočetním problému o konečných hrách.

Je dana konecna hra. Alice tvrdi, ze ma strategii takovou, ze vyhraje alespon jednou, kdyz se hra hraje simultanne na n deskach a Alice zacina, a take strategii takovou, ze vyhraje alespon jednou kdyz se hra hraje simultanne na n deskach a Bob zacina. Lze Alici usvedcit ze lze v polynomialne mnoha krocich? Hastad dokazal, ze pokud je pocet tahu ve hre omezen na 4, je to mozne. Pro 5 a vice je to otevreny problem.