Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and
investigate the relative power of the notion of ``concurrent knowledge-extraction'' ... more >>>

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

Quantified constraint satisfaction is the generalization of
constraint satisfaction that allows for both universal and existential
quantifiers over constrained variables, instead
of just existential quantifiers.
We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>