Title: Lower Bound Techniques for QBF Proof Systems

Description: Speaker: Prof. Meena Mahajan

Time: Tuesday, 17 April 2018, 11:30am
Venue: Room no. 109, 01st Floor, Department of Computer Science and Engineering, New CSE/CC Building

Abstract:
How do we prove that a false QBF is indeed false? How big a proof is needed? The special case when all quantifiers are existential is the well-studied setting of propositional proof complexity. Expectedly, universal quantifiers change the game significantly. Several proof systems have been designed in the last couple of decades to handle QBFs. Lower bound paradigms from propositional proof complexity cannot always be extended - in most cases feasible interpolation and consequent transfer of circuit lower bounds works, but obtaining lower bounds on size by providing lower bounds on width fails dramatically. A new paradigm with no analogue in the propositional world has emerged in the form of strategy extraction, allowing for transfer of circuit lower bounds, as well as obtaining independent genuine QBF lower bounds based on a semantic cost measure.

This talk will provide a broad overview of some of these developments.

Speaker Profile:
Details about the speaker are available at https://www.imsc.res.in/~meena/.

Organization:
The Institute of Mathematical Sciences, Chennai



Host:
Prof. Nutan Limaye

Date: Tuesday, 17 April, 2018
Time: 11:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 10 October, 2021 10:42am IST
Send Reminder: Yes  -  264 hours 38 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)