4 papers
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…
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…
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…
Exponential Separation Between Powers of Regular and General Resolution Over Parities
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvořák
Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot…