Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 6, October 2010

The structure of inverses in schema mappings
Ronald Fagin, Alan Nash
Article No.: 31
DOI: 10.1145/1857914.1857915

A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). The notion of an inverse of a schema mapping is...

A random-sampling-based algorithm for learning intersections of halfspaces
Santosh S. Vempala
Article No.: 32
DOI: 10.1145/1857914.1857916

We give an algorithm to learn an intersection of k halfspaces in Rn whose normals span an l-dimensional subspace. For any input distribution with a logconcave density such that the bounding hyperplanes...

Newtonian program analysis
Javier Esparza, Stefan Kiefer, Michael Luttenberger
Article No.: 33
DOI: 10.1145/1857914.1857917

This article presents a novel generic technique for solving dataflow equations in interprocedural dataflow analysis. The technique is obtained by generalizing Newton's method for computing a zero of a differentiable function to ω-continuous...

Limitations of quantum coset states for graph isomorphism
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen
Article No.: 34
DOI: 10.1145/1857914.1857918

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting...