Alexander Knop

activity

20192023

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2020

Log-rank and lifting for AND-functions

Alexander Knop, Shachar Lovett, Sam McGuire +1

Let $f : {0, 1}^{n} \to {0, 1}$ be a boolean function, and let $f_{\land} (x, y) = f (x \land y)$ denote the AND-function of $f$ , where $x \land y$ 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…