Institute for Interdisciplinary Information Sciences
Address: Room 4-609 FIT Building,Tsinghua University, Beijing, P. R. China
Tel: 86-10-62797304 86-10-62783817 Ext.1650
I received my bachelor’s degree from Department of Computer Science and Technology, Tsinghua University in 2008. After that I joined Institute of Theoretical Computer Science(later became one part of Institute for Interdisciplinary Information Sciences) to pursuit my Ph.D degree. Now I am a Ph.D candidate in my fifth year, supervised by Prof. Periklis A. Papakonstantinou.
Recently, I enrolled in the Laboratory for the Study of Randomness in Computation and Cryptographic Complexity (RC^3).
In General, I am interested in Complexity Theory and Algorithm Design, and also Computational Group Theory.
Currently I am mainly working on width-parameterized SAT. This is a special case of SAT where instances are parameterized by tree-width or other width parameters associated with its instance graph. It can be proved that when this parameter is small, SAT can be solved efficiently. Together with co-authors, two basic algorithms are discovered for this type of SAT, one is space-efficient, the other is time-efficient; also a hybrid algorithm is developed which has better running time and space than both basic ones when the parameters are tuned correctly.
We also characterize bounded width-parameter SAT using bounded space Turing machines. By utilizing the basic relation between tree-decomposition and path-decomposition, a brand new hierachy inside NP can be derived. It is conjectured by us there can be no algorithm running asymptotically in between these two basic algorithms. We also give verifiable evidences supporting the truthfulness of the conjecture. There are follow-ups based on our conjecture. I also participated in a project to prove simultaneous time and space lower bounds for solving width-parameterized SAT in the context of proof complexity.
The study of width-parameterized SAT also opens the venue of studying space-bounded group isomorphism testing algorithms. Along with coauthors, a few simple but interesting facts are observed. This project is still ongoing.