We introduce symmetric Datalog, a syntactic restriction of linear
Datalog and show that its expressive power is exactly that of
restricted symmetric monotone Krom SNP. The deep result of
Reingold on the complexity of undirected
connectivity suffices to show that symmetric Datalog queries can be
evaluated in logarithmic space. We ... more >>>

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

In cryptography, there has been tremendous success in building
primitives out of homomorphic semantically-secure encryption
schemes, using homomorphic properties in a black-box way. A few
notable examples of such primitives include items like private
information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general
methodology for ... more >>>