2 citations · 3 across the 3 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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…
cs.CC2012★ 2 cited
Unshuffling a Square is NP-Hard
Sam Buss, Michael Soltys
A shuffle of two strings is formed by interleaving the characters into a new string, keeping the characters of each string in order. A string is a square if it is a shuffle of two…