3 papers
quant-ph2022
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
Kamil Khadiev, Aliya Khadieva, Alexander Knop
In this paper, we study quantum Ordered Binary Decision Diagrams() model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexi…
cs.CC2020
Log-rank and lifting for AND-functions
Alexander Knop, Shachar Lovett, Sam McGuire +1
Let be a boolean function, and let denote the AND-function of , where denotes bit-wise AND. We study the…
cs.CC2019
Proof complexity of systems of (non-deterministic) decision trees and branching programs
Sam Buss, Anupam Das, Alexander Knop
This paper studies propositional proof systems in which lines are sequents of decision trees or branching programs - deterministic and nondeterministic. The systems LDT and LNDT ar…