enter search term and/or author name
Generalized hypertree decompositions: NP-hardness and tractable variants
Georg Gottlob, Zoltán Miklós, Thomas Schwentick
Article No.: 30
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
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
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
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
Article No.: 34
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...