Tata Institute of Fundamental Research
Tree-like Resolution and Decision Trees
STCS Student Seminar
Speaker:
Farzan Byramji (IIT Kanpur, UCSD)
Organiser:
Varun Ramanathan
Date:
Thursday, 29 Jun 2023, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
It is well-known that tree-like resolution refutations correspond to decision trees solving the associated false clause search problem. We describe this connection and some lower bounds using this. Then we discuss variants of tree-like resolution (resolution with parities and AND-resolution) along with the corresponding decision tree models, and lifting in this setting.
| Speaker: | Farzan Byramji (IIT Kanpur, UCSD) |
| Organiser: | Varun Ramanathan |
| Date: | Thursday, 29 Jun 2023, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
It is well-known that tree-like resolution refutations correspond to decision trees solving the associated false clause search problem. We describe this connection and some lower bounds using this. Then we discuss variants of tree-like resolution (resolution with parities and AND-resolution) along with the corresponding decision tree models, and lifting in this setting.