Disjoint NP-pairs are a well studied complexity theoretic concept with
important applications in cryptography and propositional proof
complexity.

In this paper we introduce a natural generalization of the notion of
disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.
We define subclasses of ... more >>>

We shall prove a lower bound on the number of edges in some bounded
depth graphs. This theorem is stronger than lower bounds proved on
bounded depth superconcentrators and enables us to prove a lower bound
on certain bounded depth circuits for which we cannot use
superconcentrators: we prove that ... more >>>

We give a dichotomy theorem for the problem of counting homomorphisms to
directed acyclic graphs. $H$ is a fixed directed acyclic graph.
The problem is, given an input digraph $G$, how many homomorphisms are there
from $G$ to $H$. We give a graph-theoretic classification, showing that
for some digraphs $H$, ... more >>>