ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


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...