# 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.