Group:Theory Lunch
Title: Partial Derivative Method for Arithmetic Circuit Lower Bound;Two Open Problems
Speaker: Youming Qiao, Hongyu Liang University
Time: 2010-10-14 12:00-2010-10-14 13:30
Venue: FIT 1-222

Abstract:

Title: Partial derivative method for arithmetic circuit lower bound

Abstract:

In this talk I will give a soft introduction to partial derivative method for proving arithmetic circuit lower bound. It has been successfully applied to, most notably, non-commutative arithmetic circuit (by Nisan) and multilinear formula (by Raz). The talk aims for introducing the method and the background of arithmetic circuit complexity.

 

Title: Two Open Problems

In this talk I'll mention two (open) problems that I've worked on for some time, one is in circuit complexity and another is about graph algorithm.

The first problem asks how many negation gates are needed for computing a boolean function f by various circuit models. Tight results were obtained for the circuit model and formula model. In a paper with Jing He and Jayalal Sarma, we obtained upperbounds on the number of required negation gates when considering circuits of bounded-treewidth, which smoothly interpolates between the upperbounds for formulas and circuits. However, we do not have a matching lowerbound -- this is the first open question that I want to discuss.

The second problem is called rainbow connection. An edge-colored graph is called rainbow-connected if every two vertices have a path of distinct colors connecting them. It is known that even deciding if a graph can be rainbow-colored with 2 colors is NP-complete. An open question from [Chakraborty, Fischer, Matsliah, Yuster, STACS 2009] asks that, given a 2-rainbow-colorable graph, can we rainbow-color it with o(n) colors in polynomial time? We'll show some of our partial results towards attacking this problem.




Short Bio: