Chandrima Kayal

Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli et al.

For any Boolean function $f:\{0,1\}^n \to \{0,1\}$ with a complexity measure having value $k \ll n$, is it possible to restrict the function $f$ to $Θ(k)$ variables while keeping the complexity preserved at $Θ(k)$? This question, in the context of query complexity, was recently studied by G{ö}{ö}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 decision tree measures like block sensitivity and certificate complexity, cannot be condensed losslessly. That is, there exists a Boolean function $f$ such that any restriction of $f$ to $O(\mathcal{M}(f))$ variables has $\mathcal{M}(\cdot)$-complexity at most $\tilde{O}(\mathcal{M}(f)^{2/3})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{D}\}$. This also improves upon a result of G{ö}{ö}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 $O(\mathcal{M}(f))$ variables such that its $\mathcal{M}(\cdot)$-complexity is at least $Ω(\mathcal{M}(f)^{1/2})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{UC}_{min},\mathsf{UC}_1,\mathsf{UC},\mathsf{D},\widetilde{\mathsf{deg}},λ\}$. We also show a slightly weaker positive result for randomized and quantum query complexity.

Arijit Ghosh, Chandrima Kayal, Soumi Nandi

Let $\mathbb{F}$ be a field, and consider the hypercube $\{ 0, 1 \}^{n}$ in $\mathbb{F}^{n}$. Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a polynomial $P ( X_{1}, \dots, X_{n} ) \in \mathbb{F}[ X_{1}, \dots, X_{n}]$ vanishes on every point of the hypercube $\{0,1\}^{n}$ except those with at most $r$ many ones then the degree of the polynomial will be at least $n-r$. This is a generalization of Alon and Füredi's fundamental result (European Journal of Combinatorics 1993) about polynomials vanishing on every point of the hypercube except at the origin (point with all zero coordinates). Sziklai and Weiner proved their interesting result using Möbius inversion formula and the Zeilberger method for proving binomial equalities. In this short note, we show that a stronger version of Sziklai and Weiner's result can be derived directly from Alon and Füredi's result.