Group:Theory Lunch
Title: Presentation
Speaker: Wei Yu, Bangsheng Tang, Shiteng,Chen Tsinghua university
Time: 2010-05-20 12:00-2010-05-20 13:30
Venue: FIT 1-222


Presenter: Yu Wei


We talk about the following problem proposed in the paper by Bille et al.

For a grammar G of size n representing a string of length L, the problem is to build a data structure that the query with argument i will return the i-th character in the string.* PREPROCESS(G): preprocess the grammar with $S$ space, the grammar is given by n rules of form G_i = G_j + G_k or G_i = \sigma, where j, k < i and \sigma \in {0,1}, * QUERY(i): return the i-th character.

We are here to give a lowerbound for this problem in the cell-probe model , by using a reduction from the Blocked-LSD problem. Alice has a set X = {(1,a_1), (2,a_2), ..., (N,a_N)} of size N where a_i \in [B], and Bob has a set Y \subseteq [B]^N, the problem is to see if X \cap Y = \emptyset. The Blocked-LSD was proposed in Patrascu and the following theorem is paraphrased from the same reference. Fix $\delta > 0$. For \blsd\ problem either Alice needs to send $\Omega(\delta N \log B)$ bits or Bob needs to send $\Omega(N B^{1-\delta})$ bits.


Presenters: Bangsheng Tang and Shiteng Chen


In this lunch meeting, we will continue to discuss about the current project that we are doing, the bounded tree width SAT problem.

If we denote n as the input size, w(n) as the tree width. We have two easy algorithms,

1. 2^{O(w(n))} time, 2^{O(w(n))} space This is showed by Alekhnovich and Razborov at 2002 in their paper "satisfiability,branch-width and tseitin tautologies"

2. 2^{O(w(n)log n)} time, O(w(n)log n) space. This is showed by Konstantinos Georgiou1 and Periklis A. Papakonstantinou in their paper "Complexity and Algorithms for Well-Structured k-SAT Instances"

We will sketch the algorithms in the simple case of the decompositions are paths. And, we also have a hybrid algorithm for this problem which can increase the running time of algorithm 1 and decrease the space. Ultimately, we want to find an algorithm runs in 2^{O(w(n)) time, O(poly(n)) space, which will answer Alekhnovich and Razborov's open problem. However, it seems difficult to remove log n factor in the exponent. It is even hard to find out an intermediate state in between the two extreme algorithms.

Short Bio: