ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 55 Issue 3, July 2008

Beyond separation of duty: An algebra for specifying high-level security policies
Ninghui Li, Qihua Wang
Article No.: 12
DOI: 10.1145/1379759.1379760

The process of introducing security controls into a sensitive task, which we call secure task design in this article, consists of two steps: high-level security policy design and low-level enforcement scheme design. A high-level security...

Matching algorithmic bounds for finding a Brouwer fixed point
Xi Chen, Xiaotie Deng
Article No.: 13
DOI: 10.1145/1379759.1379761

We prove a new discrete fixed point theorem for direction-preserving functions defined on integer points, based on a novel characterization of boundary conditions for the existence of fixed points. The theorem allows us to derive an improved...

Computing correlated equilibria in multi-player games
Christos H. Papadimitriou, Tim Roughgarden
Article No.: 14
DOI: 10.1145/1379759.1379762

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical...

Homomorphism preservation theorems
Benjamin Rossman
Article No.: 15
DOI: 10.1145/1379759.1379763

The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an...