Tata Institute of Fundamental Research
Hardness Condensation for Decision Tree Measures
STCS Seminar
Speaker:
Nitin Saurabh (IIT Hyderabad)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 11 Mar 2025, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Can every Boolean function on n variables with query complexity k << n be restricted to O(k) variables such that the query complexity remains $\Omega(k)$? In other words, can query complexity be condensed by restrictions? Goos-Newman-Riazanov-Sokolov (STOC'24) studied such hardness condensation questions and showed, among other results, that query complexity can not be condensed losslessly. They asked if complexity measures like block sensitivity or unambiguous certificate complexity can be condensed?
In this talk, we will see that a host of complexity measures, like block sensitivity, unambiguous certificate complexity, certificate complexity etc. cannot be condensed losslessly. In the process we will improve upon the condensation result for query complexity of [GNRS'24] and also obtain some positive results on condensation.
This talk is based on a joint work with Chandrima Kayal (IMSc, Chennai --> IRIF, Paris).
Short Bio:
Nitin Saurabh is a faculty member in the CSE department at IIT Hyderabad since 2022. His research interests lie broadly in theoretical computer science, and especially in complexity theory, Boolean function analysis, algebraic complexity, etc.
| Speaker: | Nitin Saurabh (IIT Hyderabad) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 11 Mar 2025, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Can every Boolean function on n variables with query complexity k << n be restricted to O(k) variables such that the query complexity remains $\Omega(k)$? In other words, can query complexity be condensed by restrictions? Goos-Newman-Riazanov-Sokolov (STOC'24) studied such hardness condensation questions and showed, among other results, that query complexity can not be condensed losslessly. They asked if complexity measures like block sensitivity or unambiguous certificate complexity can be condensed?
In this talk, we will see that a host of complexity measures, like block sensitivity, unambiguous certificate complexity, certificate complexity etc. cannot be condensed losslessly. In the process we will improve upon the condensation result for query complexity of [GNRS'24] and also obtain some positive results on condensation.
This talk is based on a joint work with Chandrima Kayal (IMSc, Chennai --> IRIF, Paris).
Short Bio:
Nitin Saurabh is a faculty member in the CSE department at IIT Hyderabad since 2022. His research interests lie broadly in theoretical computer science, and especially in complexity theory, Boolean function analysis, algebraic complexity, etc.