Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 1, March 2007

The complexity of homomorphism and constraint satisfaction problems seen from the other side
Martin Grohe
Article No.: 1
DOI: 10.1145/1206035.1206036

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let...

Polymorphic higher-order recursive path orderings
Jean-Pierre Jouannaud, Albert Rubio
Article No.: 2
DOI: 10.1145/1206035.1206037

This article extends the termination proof techniques based on reduction orderings to a higher-order setting, by defining a family of recursive path orderings for terms of a typed lambda-calculus generated by a signature of polymorphic...

Speed scaling to manage energy and temperature
Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs
Article No.: 3
DOI: 10.1145/1206035.1206038

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature...

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Sean Hallgren
Article No.: 4
DOI: 10.1145/1206035.1206039

We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer d, Pell's equation is x2...