清华大学交叉信息研究院

陈世腾
Email:
地址: 北京市海淀区中关村南四街4号中国科学院软件所5#209
电话: 86-10-62661647


Education Background:


I'm now working for the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, as an assistant researcher.  I was  adivised by Periklis A. Papakonstantinou as a PhD student in IIIS, Tsinghua University, and just get my degree in 2016. I graduated from computer science department.


 Research Interests:


I'm interested in complexity and number theory. Recently, my supervisor and me have just make an interesting progress on the depth reduction algorithm for ACC circuits, which will imply strong unconditional ACC circuit lower bounds. 

Publications:


Remark: the author order is alphabetical.

 

Depth reduction for composites. (with Periklis A. Papakonstantinou) FOCS 2016


Width-Parametrized SAT: Time--Space Tradeoffs. (with Eric Allender, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang) Theory of Computing 10 (2014)

 

Space-bounded communication complexity. (with Joshua Brody, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun) ITCS 2013

 

Exponential Lower Bounds for the PPSZ k-SAT Algorithm. (with Dominik Scheder, Bangsheng Tang,  Navid Talebanfard) SODA 2013