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

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, letní semestr 2003 [Previous program, spring 2003]
20. 5. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Pavel Pudlák: Shrnutí a otevřené problémy

13. 5. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Marek Chrobak: Broadcasting and Gossiping in Radio Networks with Unknown Topoplogy
(joint work with L.Gasieniec and W.Rytter)

We consider the problem of information dissemination in multi-hop radio networks with unknown topology. We give the following upper bounds:

O(n log^2 n)-time algorithm for deterministic broadcasting. This nearly matches the known lower bound of Omega(n log n). The fastest previously known algorithm for this problem works in time O(n^1.5).
O(n^1.5 log^2n)-time algorithm for deterministic gossiping.
O(n log^4 n)-time algorithm for randomized gossiping.

29. 4. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Dima Grigoriev, Alexander Razborov: Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields
(referuje Martin Pergel)
A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F

22. 4. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Michael H. Goldwasser: Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control
(referuje J. Sgall)

We consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. Our work examines this model when parameterizing an instance by a new value which we term the patience. This parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. Specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. We say that a problem instance has patience κ, if each job with length |J| has a slack of at least κ · |J|. Without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. Previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. Our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. We are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations. If viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis then parameterizing solely on the ratio of the job lengths. For example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ >= 0 is exactly 1+1/(⌊κ⌋+1).

15. 4. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Pavel Pudlák: A note on monotone complexity and the rank of matrices
(s A. Gál)

8. 4. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Daniel Král´: Formulas without 4 Contradicting Clauses

We consider the following extremal problem: What is the largest ratio r_k such that for each k-satisfiable CNF formula with m clauses, there is a truth assignment which satisfies at least r_k*m of its clauses? A CNF formula is said to be k-satisfiable if any subset of k clauses of it is satisfiable. So far, the values of r_1, r_2 and r_3 have been known. We determine the exact value of r_4.

1. 4. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Susanne Albers: On randomized online scheduling. STOC 2002: 134-143
(referuje J. Sgall)

Tento článek dává nový pravděpodobnostní algoritmus pro základní problém online rozvrhování. Zároveň ukazuje, že tento algoritmus je lepší než jakýkoliv deterministický pokud se omezíme na současné metody jejich analýzy.

25. 3. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

R. Paturi: The complexity of Unique k-SAT: An isolation lemma for k-CNFs
(joint work with Chris Calabro, Russell Impagliazzo, and Valentine Kabanets)

We provide some evidence that Unique k-SAT is as hard to solve as general k-SAT. Our main technical result is an Isolation Lemma for k-CNFs, which shows that a given satisfiable k-CNF can be efficiently probabilistically reduced to a uniquely satisfiable k-CNF, with non-trivial (albeit exponentially small) success probability.

11. 3., 18. 3. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

J. Rudin, R. Chandrasekaran: Improved bounds for the online scheduling problem
(referuje Tomáš Tichý)

V tomto článku a stejnojmenné Rudinově dizertaci se zlepšují odhady na jeden ze základních problémů o online rozvrhování.

25. 2., 4. 3. 2003 (úterý [Tuesday], 10.00, MÚ Žitná 25, 1. patro)

Straubing, H. and Therien, D., A Note on MOD p - MOD m Circuits. submitted to Theoretical Computer Science, 1998.
Frederic Green: The Correlation Between Parity and Quadratic Polynomials Mod 3. IEEE Conference on Computational Complexity 2002: 65-72
(referuje Martin Pergel)