Tata Institute of Fundamental Research
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution
STCS Seminar
Speaker:
Meena Mahajan (IMSc, Chennai)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 29 Sep 2020, 16:00 to 17:00
Venue:
(Scan to add to calendar)
Abstract:
This talk will start with an overview of the relatively young field of QBF proof complexity, explaining the QBF proof system QURes, and an assessment of existing lower bound techniques. In the main part of the talk, I will describe a characterisation of QURes proof size in terms of a model in circuit complexity called term decision lists, yielding very direct connections between circuit lower bounds and QURes proof size lower bounds. Joint work with Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl.
YouTube Live : https://www.youtube.com/watch?v=Zn7ZzaELF6A
| Speaker: | Meena Mahajan (IMSc, Chennai) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 29 Sep 2020, 16:00 to 17:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
This talk will start with an overview of the relatively young field of QBF proof complexity, explaining the QBF proof system QURes, and an assessment of existing lower bound techniques. In the main part of the talk, I will describe a characterisation of QURes proof size in terms of a model in circuit complexity called term decision lists, yielding very direct connections between circuit lower bounds and QURes proof size lower bounds. Joint work with Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl.
YouTube Live : https://www.youtube.com/watch?v=Zn7ZzaELF6A
YouTube Live : https://www.youtube.com/watch?v=Zn7ZzaELF6A