清华大学交叉信息研究院

乔友明
Email:
地址: 中国北京市清华大学信息科学技术大楼(FIT楼)4区609房间
电话: 86-10-62797304 86-10-62783817 Ext.1623


Education and CV:


 

I am a second year Ph.D. student at ITCS. Before joining this institute, I received my Bachelor's Degree of Engineer at Department of Computer Science and Technology, Tsinghua Univ. in 2008.
Here's
my CV.


 
Research Interests:


 

I used to do some cryptography, but now I am more involved in complexity theory. Here's the entry 计算复杂性理论 (computational complexity theory) in Chinese Wikipedia, which I've contributed to.
Now I care more about Algebraic Complexity theory, like arithmetic circuits, polynomial identity testing as well as "weird problems" like group isomophism problem. Regarding my motivation to study them, please take a look at my
research statement.



My research  


1

Maurice Jansen, Youming Qiao and Jayalal Sarma: Deterministic Black-Box Identity Testing Π-Ordered Algebraic Branching Programs. Submitted.

2

Maurice Jansen, Youming Qiao and Jayalal Sarma: Deterministic Identity Testing of Read-Once Algebraic Branching Programs. Submitted.

3

Andrej Bogdanov and Youming Qiao: On the Security of Goldreich's One-Way Function. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 2009.
With
slides
.

4

Christophe Tartary and Youming Qiao. Counting Method for Multi-party Computation over Non-abelian Groups. In Proceedings of the 7th International Conference on Cryptology and Network Security (CANS), 2008.
With
slides.

Talks and Slides  


I believe that good slides are necessary companion to understanding a topic :)

1

A Glimpse at Group Theory in Computation. A talk given at the students' seminar at ITCS. Introduce group tower method for graph isomorphism with bounded degrees, the group-theoretic framework for matrix multiplication and tight bound for convergent rate of random walk on boolean cube. (Some of the content is copied from the talk by Chris Umans. )

1

Pseudorandom Generator for Polynomial Identity Testing Problem.. A talk given at the theory seminar at University of Chicago. Cover the basic status of current research, and introduce the work with Maurice Jansen, Jayalal Sarma using elementary algebraic geometry to give quasi-polynomial testing for oblivious ABP, as well as Kabanets and Impagliazzo's arithmetic Nisan-Widgerson generator.