3 papers
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.CC2024
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…
cs.CC2024
Aaronson-Ambainis Conjecture Is True For Random Restrictions
Sreejata Kishor Bhattacharya
In an attempt to show that the acceptance probability of a quantum query algorithm making queries can be well-approximated almost everywhere by a classical decision tree of dep…