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
http://www.math.unicaen.fr/~nitaj/abc.html