Speaker: |
Tulasi mohan Molli |

Organiser: |
Nikhil S Mande |

Date: |
Friday, 25 Nov 2016, 16:00 to 17:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Arithmetic circuits and Branching programs are two computational models for computing polynomials. Branching programs can be efficiently simulated by Circuits. But, we don't know if Circuits are strictly more powerful than branching programs.

In this talk, we will see the usage of isoperimetric profiles to prove a sharp super-polynomial separation between monotone arithmetic circuits and monotone arithmetic branching programs. This is a result of Hrubes and Yehudayoff [ICALP 2016].

A key ingredient in the proof is an accurate analysis of isoperimetric profile of finite full binary trees.