Time & Date: Dec. 3rd (Thu): 14:00 - 16:00
Place: CELC Seminar Room (Tokyo Tech. CIC 4F)
Speaker: Alexander Knop
(St. Petersburg Department of V.A. Steklov Institute of Mathematics)
Title: Complexity of distributions and average-case hardness

Abstract: 
In this talk we address to a natural question in average-case
complexity: does there exist a language L such that for all easy
distributions D the distributional problem (L, D) is easy on
the average while there exists some more hard distribution D'
such that (L, D') is hard on the average? 

We prove that there exists such language L and such distribution D
samplable in n^{\log^2 n} steps and linear-time algorithm A such
that for every polynomial-time samplable distribution F,
A correctly decides L on all inputs from {0, 1}^n except of a set
that has infinitely small F-measure and for every algorithm B
there are infinitely many n such that set of all elements of {0, 1}^n
such that B correctly decides L on them has infinitely small D-measure.

Speaker: Dmitry Sokolov
(St. Petersburg Department of V.A. Steklov Institute of Mathematics)
Title: Lower bound for splitting by linear combinations.

Abstrqact:
A typical DPLL algorithm for the Boolean satisfiability problem
splits the input problem into two by assigning the two possible
values to a variable; then it simplifies the two resulting formulas.
In this talk we consider an extension of the DPLL
paradigm. Our algorithms can split by an arbitrary linear
combination of variables modulo two. These algorithms quickly solve
formulas that explicitly encode linear systems  modulo  two,  which
were used  for  proving  exponential  lower  bounds  for
conventional DPLL algorithms. We prove exponential lower bounds
on the running time of DPLL with splitting by linear combinations
on 2-fold Tseitin formulas.

Raz and Tzameret introduced a system R(lin) which operates with
disjunctions of linear equalities with integer coefficients. We
consider an extension of the resolution proof system that operates
with disjunctions of linear equalities over F_2; we call
this system Res-Lin. Res-Lin can be p-simulated in R(lin) but
currently we do not know any superpolynomial lower bounds in
R(lin). Tree-like proofs in Res-Lin are equivalent
to the behavior of our algorithms on unsatisfiable instances.
We consider relations between Res-Lin semantic version of
Res-Lin and R(lin). We prove a space-size tradeoff for
Res-Lin proofs of 2-fold Tseitin formulas.

(host: watanabe@is.titech.ac.jp)