Bangsheng Tang
Ph.D Candidate
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

Education Background:

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.

Publications & Manuscripts:

  1. On Isomorphism Testing of Groups with Normal Hall Subgroups, Youming Qiao and Jayalal Sarma M.N. and Bangsheng Tang, STACS 2011, [PDF]
  2. Some Remarks on the Incompressibility of Width-Parameterized SAT Instances, Bangsheng Tang, FAW AAIM 2012, [PDF]
  3. Exponential Lower Bounds for the PPSZ k-SAT Algorithm, Shiteng Chen, Dominik Scheder, Navid Talebanfard and Bangsheng Tang, SODA 2013, [PDF]
  4. Some Trade-off Results for Polynomial Calculus, Chris Beck, Jakob Nordström and Bangsheng Tang, STOC 2013
  5. Width-parameterized SAT: Time-Space Tradeoffs, Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou and Bangsheng Tang, ECCC, [PDF]
  6. Towards Efficient Group Isomorphism Testing, Periklis A. Papakonstantinou, Youming Qiao and Bangsheng Tang, manuscript


  1. On Isomorphism Testing of Groups with Normal Hall Subgroups. STACS 2011, Dortmund.
  2. Width-parameterized SAT: Time-Space Tradeoffs. CTW 2011, Aarhus.

Teaching Assistant:

  1. Advanced Algorithms, 2009 Spring, Lecturer: Elad Verbin
  2. Advanced Algorithms, 2010 Spring, Lecturers: Frans Schalekamp, Anke van Zuylen
  3. Advanced Theoretical Computer Science II, 2011 Spring, Lecturers: Andrew Wan, John Steinberger
  4. Advanced Algorithms, 2012 Fall, Lecturer: Periklis A. Papakonstantinou