Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 56 Issue 6, September 2009

Introduction to PODS 2007 special section
Leonid Libkin, Victor Vianu
Article No.: 29
DOI: 10.1145/1568318.1568319

Generalized hypertree decompositions: NP-hardness and tractable variants
Georg Gottlob, Zoltán Miklós, Thomas Schwentick
Article No.: 30
DOI: 10.1145/1568318.1568320

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in...

The complexity of query containment in expressive fragments of XPath 2.0
Balder ten Cate, Carsten Lutz
Article No.: 31
DOI: 10.1145/1568318.1568321

XPath is a prominent W3C standard for navigating XML documents that has stimulated a lot of research into query answering and static analysis. In particular, query containment has been studied extensively for fragments of the 1.0 version of this...

Triangulation and embedding using small sets of beacons
Jon Kleinberg, Aleksandrs Slivkins, Tom Wexler
Article No.: 32
DOI: 10.1145/1568318.1568322

Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of...

A property of quantum relative entropy with an application to privacy in quantum communication
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
Article No.: 33
DOI: 10.1145/1568318.1568323

We prove the following information-theoretic property about quantum states.

Substate theorem: Let ρ and σ be quantum states in the same Hilbert space with relative entropy S(ρ ∥ σ) ≔ Tr ρ...

On lattices, learning with errors, random linear codes, and cryptography
Oded Regev
Article No.: 34
DOI: 10.1145/1568318.1568324

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It...