| * Venue | E C G Sudarshan Hall |
| * Speaker | Nitin Saurab |
| * Title | Hardness Condensation for Decision Tree Measures |
| Affiliation | IIT Hyderabad |
| Abstract | For any Boolean function f:{0,1}^n -> {0,1} with a complexity measure k << n, is it possible to restrict the function f to \Theta(k) variables while keeping the complexity preserved at \Theta(k)? This question, in the context of query complexity, was recently studied by G{\"{o}}{\"{o}}s, Newman, Riazanov and Sokolov (STOC 2024). They 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 losslessly? In this work, we show that a host of decision tree measures like block sensitivity, certificate complexity, unambiguous certificate complexity, etc., cannot be condensed losslessly. That is, there exists a Boolean function f such that any restriction of f to O(M(f)) variables has M(.)-complexity at most M(f)^{2/3}, where M \in {(fractional) block sensitivity, (unambiguous) certificate complexity, query complexity}. This also improves upon a result of G{\"{o}}{\"{o}}s, Newman, Riazanov and Sokolov (STOC 2024). We also complement the negative results on lossless condensation with positive results about lossy condensation. In particular, we show that for every Boolean function f there exists a restriction of f to M(f) variables such that its M(.)-complexity is at least \sqrt{M(f)}. This is based on a joint work with Chandrima Kayal (IRIF, Paris). |
| * Announcement? | None |
| * Refreshments? | During the event |
| * Honorarium? | None |
| Special Arrangements? | Digital Projection |
| * Host name and email | Prakash Saivasan @@ prakashs@imsc.res.in |