Youming Qiao

Youming Qiao

Institute for Theoretical Computer Science

Name: Youming  Qiao

Address: Room 4-609 FIT Building,Tsinghua University, Beijing, P. R. China

Telephone: 86-10-62797304 86-10-62783817 Ext.1623

Research Interest: Complexity, Cryptography

Email: Jimmyqiao86@gmail.com

Education and CV:

 

I am a third 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 László Babai , Paolo Codenotti, Joshua A. Grochow, Youming Qiao. Code Equivalence and Group Isomorphism. To appear in Symposium on Discrete Algorithms (SODA) 2011.
2 Youming Qiao, Jayalal Sarma and Bangsheng Tang: On Isomorphism Testing of Groups with Normal Hall Subgroups. Accepted to Symposium on Theoretical Aspects of Computer Science (STACS) 2011.

3

 Maurice Jansen, Youming Qiao and Jayalal Sarma: Deterministic Black-Box Identity Testing Π-Ordered Algebraic Branching Programs. To appear in Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2010.

4

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

5

 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.

6

 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. )

2

 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.