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

 Pavel Pudlák, Jiří Sgall

K. Amano, A. Maruoka:
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most  (1/6) log log n  Negation Gates
(přednáší J. Sgall) O. Čepek:
Nonpreemtive Flowshop Scheduling with Machine Dominance
(joint research with Masanori Okada and Milan Vlach)

Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. In this talk we concentrate on a special case of flowshop defined by additional machine dominance constraints. We build up on works by Adiri and Pohoryles [1] and by Ho and Gupta [2]. First of all we prove that the algorithms presented in [1,2] which generate the best permutation schedules for certain objective functions in fact generate optimal schedules. This is achieved by showing, that the set of permutation schedules is a dominant set for this specially structured flowshop problem. Moreover, we extend this result from the objective functions studied in [1,2] to all regular objective functions. Secondly we show, that for a quite broad class of regular objective functions (which includes all commonly used ones), the studied flowshop problem can be effectively reduced to a single machine problem. This reduction yields a polynomial time optimization algorithm for the studied flowshop problem whenever a polynomial time optimization algorithm for the corresponding single machine problem is known.

J. Sgall
Aproximační schémata pro rozvrhování na paralelních počítačích
(spol. s L. Epstein)
 
Prezentujeme aproximační algoritmz pro royvrhování na paralelních počítačích s růynou rychlostí, pro širokou třídu optimalizovaných hodnotících funkcí. Výsledky zobecňují dřívější práce týkající se identických počítačů, navíc nové algoritmy jsou jednodušší. R. Impagliazzo, R. Paturi
Complexity of k-SAT
(referuje J. Sgall)

Článek ukazuje, že pokud k-SAT vyžaduje exponenciální čas O(2^{s_k n}), pak posloupnost s_k roste s k.

Ran Raz (Weizmann Institute, Israel),  Pierre McKenzie (Montreal, Canada)
Separation of the Monotone NC Hierarchy
(referuje J. Červenka)

We prove tight lower bounds for the monotone depth of functions in monotone­P. As a result we achieve the separation of the following classes.
1. monotone­NC and monotone­P.
2. For every i >0, monotone­NC^i  and monotone­NC^{i+1}.
Only a separation of monotone­NC^1 from monotone­NC^2 was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions.

P. Pudlák
O složitosti algoritmů pro k-SAT

Dokážeme, že tzv. DLL algoritmy (také zavane Davis-Putnam) pro splňování k-CNF vyžadují čas 2^{n(1-\epsilon_k)}, kde \epsilon_n jde k 0 s k rostoucím do nekonečna.

M. Alekhnovich, S. Buss, S. Moran, T. Pitassi
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
(referuje J. Sgall)

We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within any constant factor. These results are very robust in that they hold for almost all natural proof systems.

Russell Impagliazzo (UC San Diego, CA, U.S.A.)
Which Problems Have Strongly Exponential Complexity?
(joint work with Ramamohan Paturi and Francis Zane)

For several NP-complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction which we call Sub-Exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP-search problems, and that for any fixed $k$, $k$-SAT, $k$-Colorability, $k$-Set Cover, Independent Set, Clique, Vertex Cover, are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others.

We also look at the issue of proving strongly exponential lower bounds (that is, bounds of the form $2^{\Omega(n)}$) for AC. This problem is even open for depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most $n^{\epsilon}$) fan-in for bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even degree 2 random GF(2) polynomials require strongly exponential size for $\Sigma^k_3 $ circuits for $k=o(\log\log n)$. We thus exhibit a much smaller space of $2^{O(n^2 )}$ functions such that almost every function in this class requires strongly exponential size $\Sigma_3^k$ circuits. As a corollary, we derive a pseudorandom generator (requiring $O(n^2)$ bits of advice) that maps $n$ bits into a larger number of bits so that computing parity on the range is hard for $\Sigma_3^k$ circuits.

Our main technical lemma is an algorithm that, for any fixed $\epsilon>0$, represents an arbitrary $k$-CNF formula as a disjunction of $2^{\epsilon n}$ $k$-CNF formulas that are sparse, e.g., each having $O(n)$ clauses.

Russell Impagliazzo (UC San Diego, CA, U.S.A.)
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes
(joint work with Samuel Buss and Toniann Pitassi)

This paper gives nearly optimal lower bounds on the minimum degree of Polynomial Calculus refutations of Tseitin's graph tautologies and the mod p counting principles. These are the first bounds for polynomial calculus that distinguish linearly between proofs over fields of characteristic $p$ and $q$, where $p$ and $q$ are distinct primes.

Petr Savický (UI, Praha)
O funkcích s mnoha dobrými uspořádáními pro paritní OBDD
 
Problém nalezení dobrého uspořádání pro OBDD pro zadanou funkci je výpočetně velmi naročný. Pro lepší pochopení struktury dobrých uspořádání se zkoumají vlastnosti náhodných uspořádání. Ukážeme, ze pokud náhodné uspořádání dáva polynomiální paritní OBDD pro funkci f s pravděpodobností vetší než nějaké kladné epsilon, pak každé uspořádání dává pro f polynomialní paritní OBDD. To ukazuje rozdíl proti (obyčejným) OBDD, pro které analogické tvrzení neplatí. Andris Ambainis (UC Berkeley, U.S.A.)
Constant depth arithmetic circuits with and without negative constants
(joint work with E.Allender, S. Datta, D.M. Barrington, H. LeThanh)

The counting class #P was first defined by Valiant as the class of functions, which can be computed as the number of accepting computations of a nondeterministic Turing machine working in polynomial time. Later, other counting classes #L, #NC^1, #AC^0, etc. were defined. To capture functions which might have negative values, GapP, GapL, GapAC^0 are considered.
Two definitions of GapAC^0 were proposed: as #AC^0 -#AC^0 (referred to as DiffAC^0), and as the class of functions computables by arithmetized AC^0 circuits augmented by the constant -1. It was an open question whether GapAC^0=DiffAC^0. We will anwser this question positively.
After that, we will consider the question whether #AC^0 and GapAC^0 are closed under division by a constant. It appears that GapAC^0 is closed under division by a constant m iff m is a power of 2. #AC^0 is not closed under division by any constant.

Ingo Wegener (Dortmund, SRN)
Remarks and open problems on BDDs.
 
In this talk some recent developments on BDDs (complexity and algorithms) are reported and some open problems are presented and discussed. So the talk will consist of some mini-talks.

and
Matthias Krause (Mannheim, SRN)
On connections between learning and communication complexity