Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Seminar On Dec. 23, 2011

Date: Friday, Dec. 23rd, 2011

Place: Shanghai JiaoTong University Minhang Campus


11:00 -12:00

Title: Complexity Dichotomy Theorems for Counting Problems

Speaker: Jin-Yi Cai (University of Wisconsin, Madison)


I will describe several complexity dichotomy theorems for counting problems. Lov\'asz (1967) defined graph homomorphism to encompass a very general class of graph properties. The computational problem can be stated as follows: Given an $m \times m$ symmetric matrix $A$ over the complex field, compute the function $Z_A(\cdot)$, where for an arbitrary input graph~$G$, \[ Z_A(G) = \sum_{\xi:V(G)\rightarrow [m]} \ \prod_{(u,v)\in E(G)} A_{\xi(u),\xi(v)}.\] Recently a complete dichotomy theorem has been achieved for this problem. I will give an introduction to this proof.

I also plan to discuss a dichotomy theorem which characterizes all solvable planar Holant and CSP problems over the Boolean domain. This assumes arbitrary symmetric real-valued local constraint functions. The interesting characterization is that, within the stated framework, Valiant's holographic algorithms with matchgates provide a universal methodology to all counting problems which are #P-hard on general graphs, but solvable on planar graphs in polynomial time.

(Based on joint work with Xi Chen, Pinyan Lu, and Mingji Xia.)


Lunch (蜀乡村川菜(东川路店):东川路8111)


Title A Rely-Guarantee-Based Simulation for Verifying Concurrent Program Transformations

Speaker: Xinyu Feng (University of Science and Technology of China)


Verifying program transformations usually requires proving that the resulting program (the target) refines or is equivalent to the original one (the source). However, the refinement relation between individual sequential threads cannot be preserved in general with the presence of parallel compositions, due to instruction reordering and the different granularities of atomic operations at the source and the target. On the other hand, the refinement relation defined based on fully abstract semantics of concurrent programs assumes arbitrary parallel environments, which is too strong and cannot be satisfied by many well-known transformations.

In this talk, I propose a Rely-Guarantee-based Simulation (RGSim) to verify concurrent program transformations. The relation is parametrized with constraints of the environments that the source and the target programs may compose with. It considers the interference between threads and their environments, thus is less permissive than relations over sequential programs. It is compositional w.r.t.

parallel compositions as long as the constraints are satisfied. Also, RGSim does not require semantics preservation under all environments, and can incorporate the assumptions about environments made by specific program transformations in the form of rely/guarantee conditions. We use RGSim to reason about optimizations and prove atomicity of concurrent objects. We also propose a general garbage collector verification framework based on RGSim, and verify the Boehm et al. concurrent mark-sweep GC.

3:00-3:30 Tea Break


Title: Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Speaker: Jia Zheng (Harvard University)


We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there is no probabilistic polynomial-time $S$ such that $(X,S(X))$ has small KL divergence from $(X,B)$. This can be viewed as an analogue of the Impagliazzo Hardcore Theorem (FOCS `95) for Shannon entropy (rather than min-entropy).

Using this characterization, we show that if $f$ is a one-way function, then $(f(U_n),U_n)$ has ``next-bit pseudoentropy'' at least $n+\log n$, establishing a conjecture of Haitner, Reingold, and Vadhan (STOC `10). Plugging this into the construction of Haitner et al., this yields a simpler construction of pseudorandom generators from one-way functions. In particular, the construction only performs hashing once, and only needs the hash functions that are randomness extractors (e.g.\ universal hash functions) rather than needing them to support ``local list-decoding'' (as in the Goldreich--Levin hardcore predicate, STOC `89).

With an additional idea, we also show how to improve the seed length of the pseudorandom generator to $\tilde{O}(n^3)$, compared to $O(n^4)$ in the construction of Haitner et al.

Joint work with Salil Vadhan. ECCC version at