Separation Between Computational Complexity Measures Using Projective Geometry

This poster was presented as a part of the Geometry Probability and Algorithm conference at International Center for Theoretical Sciences (ICTS), Bengaluru, India.

This project (Summer Project May–August 2024) was conducted under the guidance of Dr.Rajat Mittal, Department of Computer Science and Engineering, Indian Ins􀆟tute of Technology, Kanpur, and was funded by SURGE IIT Kanpur.

Abstract

In 2019, Hao Huang resolved a longstanding problem in theoretical computer science by proving that the sensitivity and degree of a Boolean function are polynomially related, thereby confirming the Sensitivity Conjecture of Nisan and Szegedy. Huang’s result established a tght upper bound: \(bs(f) \leq s(f)^4\). Is this power-four separaton tight? The largest known gap is observed in Rubinstein’s functon, where \(bs(f) = s(f)^2\), leaving open the intriguing question: Can the bound be improved to \(bs(f) \leq s(f)^2\)?

This work investigates this question by exploring two critical complexity measures in Boolean function analysis—sensitivity and block sensitivity—and examining the gap between them. We define a class of functions based on the projective plane, \(f_k\), and demonstrate that these func􀆟ons exhibit a substantial gap between sensitivity and block sensitivity. Specifically, we show that for the projective plane function \(f_k\), the 0-sensitivity satisfies \(s0(f_k) = 3\), while the 0-block sensitivity satisfies \(bs_0(f_k) \geq O(\sqrt{k})\). By composing this function with an OR operation, we establish a power-1.5 separa􀆟on between sensitivity and block sensitivity.

This result provides further insights into the intricate rela􀆟onship between these complexity measures and contributes to our understanding of Boolean function complexity through the lens of projective geometry.

The poster can be found here.

I also presented the same work at Indian Institute of Technology Kanpur, India and a part of SURGE program.