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

Pavel Pudlák, Jiří Sgall

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

12. 1. 2005 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, S. Venkatesh: Communication vs. Computation
(ICALP 2004)
(referuje David Kronus)

Abstract: We initiate a study of tradeoffs between communication and computation in well-known communication models and in other related models. The fundamental question we investigate is the following: Is there a computational task that exhibits a strong tradeoff behavior between the amount of communication and the amount of time needed for local computation? Under various standard assumptions, we exhibit boolean functions that show strong tradeoffs in the following computation models: (1) two-party randomized communication complexity; (2) query complexity; (3) property testing. For the model of deterministic communication complexity, we show a similar result relative to a random oracle. Finally, we study a time-degree tradeoff problem that arises in arithmetization of boolean functions, and relate it to time-communication tradeoff questions in multi-party communication complexity and in cryptography.

5. 1. 2005 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Michal Koucký: NNJAGs and incremental branching programs

8. 12., 15. 12. 2004 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Mikhail Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3CNFs 

ECCC Report TR04-016
(referuje Tomáš Ebenlendr)

Abstract: We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the first sub-exponential upper bound on the running time of a local improvement algorithm on random instances. Our proof introduces a simple, yet powerful tool for analyzing such algorithms, which may be of further use. This object, called a terminator, is a weighted satisfying assignment. We show that any CNF having a good (small weight) terminator, is assured to be solved quickly by the random walk algorithm. This raises the natural question of the terminator threshold which is the maximal clause density for which such assignments exist (with high probability). We use the analysis of the pure literal heuristic presented by Broder, Frieze and Upfal and show that for small clause densities good terminators exist. Thus we show that the Pure Literal threshold (~ 1.63) is a lower bound on the terminator threshold. (We conjecture the terminator threshold to be in fact higher). One nice property of terminators is that they can be found efficiently, via linear programming. This makes tractable the future investigation of the terminator threshold, and also provides an efficiently computable certificate for short running time of the simple random-walk heuristic.

10. 11., 1. 12. 2004 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Pavel Pudlák: Bounded-depth circuits: separating wires from gates
(joint work with Michal Koucký and Denis Thérien)

Abstract: We develop a new method to analyze the flow of communication in constant-depth circuits. This point of view allows us to prove new lower bounds on the number of wires required to recognize certain languages. We are able to provide explicit languages that can be recognized by $AC^0$~circuits with $O(n)$ gates but not with $O(n)$ wires, and similarly for $ACC^0$ circuits. We are also able to characterize exactly the regular languages that can be recognized with $O(n)$ wires, both in $AC^0$ and $ACC^0$ framework.

24. 11. 2004 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Omer Reingold: Undirected ST-Connectivity in Log-Space, ECCC Report TR04-094
(referuje Antonina Kolokolova)

Abstract: We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and Zhou. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that SL=L (where L is the class of problems solvable by deterministic log-space computations). Our algorithm also implies log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.

3. 11. 2004 (středa [Wednesday], 12.45, MÚ Žitná 25, 1. patro)

Stasys Jukna: On the P versus NP intersected with co-NP question in communication complexity
ECCC Report TR04-062
(referuje Petr Kučera)

Abstract: We consider the analog of the P versus NP intersectin co-NP question for the classical two-party communication protocols where polynomial time is replaced by polylogarithmic communication: if both a boolean function f and its negation have small (polylogarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and Yannakakis in 1983: here P = NP\cap co-NP. We show that in the best-partition case the situation is entirely different: here P is a proper subset even of RP\cap co-RP, and NP\cap co-NP is no longer a subset of BPP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982. We also extend to the best-partition case the result of Rabin and Yao that BPP is not a subset of NP in the fixed-partition model.

27. 10. 2004 (středa [Wednesday], 12.30, MÚ Žitná 25, 1. patro)

Stasys Jukna: On Graph Complexity
ECCC Report TR04-005
(referuje M. Pergel)

Abstract: A boolean circuit $f(x_1,ldots,x_n)$ emph{represents} a graph $G$ on $n$ vertices if for every input vector $ain{0,1}^n$ with precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$ precisely when $i$ and $j$ are adjacent in $G$; on inputs with more or less than two $1$'s the circuit can output arbitrary values. We consider several types of boolean circuits (depth-$3$ circuits and boolean formulas) and show that some explicit graphs cannot be represented by small circuits. As a consequence we obtain that an explicit boolean function in $2m$ variables cannot be computed as an OR of fewer than $2^{Omega(m)}$ products of linear forms over $GF(2)$. Lower bounds for this model obtainable by previously known (algebraic) arguments do not exceed $2^{O(sqrt{m})}$. We conclude with a graph-theoretic problem whose solution would have some intriguing consequences in computational complexity.
Keywords: Graph complexity, depth-$3$ circuits, $C_4$-free graphs, clique covering number

20. 10. 2004
(středa [Wednesday], 12.30, MÚ Žitná 25, 1. patro )

Jan Krajíček: Diagonalization in proof complexity

ECCC Report TR04-018

Abstract: We study the diagonalization in the context of proof complexity. We prove that at least one of the 1. There is a boolean function computable in E that has circuit complexity $2^{Omega(n)}$. 2. NP is not closed under the complement. 3. There is no p-optimal propositional proof system. We note that a variant of the statement seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant of a recent conjecture of Razborov is true (stating conditional lower bounds for the Extended Frege proof system EF) then actually unconditional lower bounds would follow for EF.

13. 10. 2004 (středa [Wednesday], 12.30, MÚ Žitná 25, 1. patro)

Nayantara Bhatnagar, Parikshit Gopalan, Richard Lipton: The Degree of Threshold Mod 6 and Diophantine Equations 
ECCC Report TR04-022
(referuje Pavel Pudlák)

Abstract: We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to counting the number of solutions to certain Diophantine equations. This allows us to use tools from number theory to study such polynomial representations.

More information about discussed abc-conjecture can be found at