3 papers
cs.CC2026
Quantum-Classical Equivalence for AND-Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean funct…
cs.CC2025
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay
Itsykson and Sokolov [IS14] identified resolution over parities, denoted by , as a natural and simple fragment of -Frege for which no super-poly…
cs.CC2025
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree o…