Presenter: Yu Wei

Abstract:

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

Abstract:

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.