Journal of the ACM (JACM)

Latest Articles

The Power of Localization for Efficiently Learning Linear Separators with Noise

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and we demonstrate its... (more)


Important Note on P/NP: Some submissions purport to solve a long-standing open problem in complexity theory, such as the P/NP problem. Many of these turn out to be mistaken, and such submissions tax JACM volunteer editors and reviewers. JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions due to incremental corrections of errors identified during editorial review, no author may submit more than one such paper to JACM, ACM Trans. on Algorithms, or ACM Trans. on Computation in any 24-month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts. Please consider this policy before submitting a such a paper.

About JACM

The Journal of the ACM (JACM) provides coverage of the most significant work on principles of computer science, broadly construed. The scope of research we cover encompasses contributions of lasting value to any area of computer science. To be accepted, a paper must be judged to be truly outstanding in its field.  JACM is interested  in work in core computer science and at the boundaries, both the boundaries of subdisciplines of computer science and the boundaries between computer science and other fields.

read more
Forthcoming Articles
Analysis of a Classical Matrix Preconditioning Algorithm

We study a classical iterative algorithm for balancing matrices in the L norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for any irreducible n×n (real or complex) input matrix A, a natural variant of the algorithm converges in O(n3 log(nÁ/µ)) elementary balancing operations, where Á measures the initial imbalance of A and µ is the target imbalance of the output matrix. (The imbalance of A is maxi |log(aiout/aiin)|, where aiout, aiin are the maximum entries in magnitude in the i'th row and column respectively.) This bound is tight up to the log n factor. A balancing operation scales the i'th row and column so that their maximum entries are equal, and requires O(m/n) arithmetic operations on average, where m is the number of non-zero elements in A. Thus the running time of the iterative algorithm is O~(n2m). This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed.

A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets

A roadmap for a semi-algebraic set $S$ is a curve which has a non-empty and connected intersection with all connected components of $S$. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in many higher-level algorithms. For a long time, the best known complexity result for computing roadmaps, due to Basu, Pollack and Roy, was $s^{d+1} D^{O(n^2)}$, where the input is given by $s$ polynomials of degree $D$ in $n$ variables, with $d \le n$ the dimension of an associated geometric object. In 2011, we introduced new proof techniques for establishing connectivity results in real algebraic sets. This gave us more freedom for the design of algorithms computing roadmaps and led us to a first probabilistic roadmap algorithm for smooth and bounded real hypersurfaces running in time $(nD)^{O(n^{1.5})}$. With Basu and Roy, we then obtained a deterministic algorithm for general real algebraic sets running in time $D^{O(n^{1.5})}$. Recently, Basu and Roy improved this result to obtain an algorithm computing a roadmap of degree polynomial in $n^{n\log^2(n)} D^{n\log(n)}$, in time polynomial in $n^{n\log^3(n)} D^{n\log^2(n)}$; this is close to the expected optimal $D^n$. In this paper, we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets such that the output size and the running time are polynomial in $(nD)^{n\log(n)}$. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under these extra assumptions, it is the first roadmap algorithm with output size and running time polynomial in $(nD)^{n\log(n)}$.

The freezing threshold for k-colourings of a random graph

We determine the exact value of the freezing threshold, r_k, for k-colourings of a random graph when k g 14. We prove that for random graphs with density above r_k, almost every colouring is such that a linear number of vertices are frozen, meaning that their colours cannot be changed by a sequence of alterations whereby we change the colours of o(n) vertices at a time, always obtaining another proper colouring. When the density is below r_k, then almost every colouring is such that every vertex can be changed by a sequence of alterations where we change O(log n) vertices at a time. Frozen vertices are a key part of the clustering phenomena discovered using methods from statistical physics. The value of the freezing threshold was previously determined by the non-rigorous cavity method.

Amplifiers for the Moran Process

The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r>1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r>1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the paper. Strong amplification is a rather surprising property - it means that in such graphs, the fixation probability of a uniformly-placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r>1 (independently of n). The name "strongly amplifying'' comes from the fact that this selective advantage is "amplified''. Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this paper, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars''. When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly $n^{-1/2}$ (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counter-example which clarifies the literature concerning the isothermal theorem of Lieberman et al.

Monadic Decomposition

Monadic predicates play a prominent role in many decidable cases, including decision procedures for symbolic automata. We are here interested in discovering whether a formula can be rewritten into a Boolean combination of monadic predicates. Our setting is quantifier-free formulas whose satisfiability is decidable, such as linear arithmetic and we here develop a semi-decision procedure for extracting a monadic decomposition of a formula when it exists.

Coloring 3-colorable graphs with less than n^{1/5} colors

We consider the problem of coloring a 3-colorable graphs in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using $\widetilde O(n^{4/11})$ colors. This is the first combinatorial improvement since Blum's $\widetilde O(n^{3/8})$ bound from FOCS'90. Like Blum's algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for polynomial time algorithm for coloring of 3-colorable graphs from $O(n^{0.2072})$ colors by Chlamtac from FOCS'07 to $O(n^{0.2049})$ colors. Next we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to $O(n^{0.19996})$ colors.

Upward Max Min Fairness

Often one would like to allocate shared resources in a fair way. A common and well studied notion of fairness is {\em Max-Min Fairness}, where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting each commodity has multiple possible paths to route its demand (for example, a network using MPLS tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths. More importantly, a network operator has limited control and understanding of the inner working of the algorithm. Finally, this approach is inherently centralized and cannot be implemented via a distributed protocol. In this paper we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation. This algorithm is a natural extension of the well known Water Filling Algorithm for a multiple path setting. We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization.

Homotopy-initial algebras in type theory

We investigate inductive types in type theory, using the insights provided by ho- motopy type theory and univalent foundations of mathematics. We do so by introducing the new notion of a homotopy-initial algebra. This notion is defined by a purely type-theoretic contractibility condition which replaces the standard, category-theoretic universal property in- volving the existence and uniqueness of appropriate morphisms. Our main result characterises the types that are equivalent to W-types as homotopy-initial algebras.

Invited Articles Foreword for 63:6

A Temporal-Logic Approach to Binding-Time Analysis

This paper demonstrates that there is a fundamental relationship between temporal logic and languages that involve multiple stages, such as those used to analyze binding times in the context of partial evaluation. This relationship is based on an extension of the Curry-Howard isomorphism, which identifies proofs with programs, and propositions with types. Our extension involves the ``next time'' (Ë) operator from linear-time temporal logic, and yields a »-calculus that we call »Ë with types of the form ËA for expressions in the subsequent stage, including appropriate introduction and elimination forms. We demonstrate that »Ë is equivalent to the core of a previously studied multi-level binding-time analysis. This is similar to work by Davies and Pfenning on staged computation based on the necessity (¡) operator of modal logic, but ¡ only allows closed code, and naturally supports a code evaluation construct, while Ë captures open code, thus is more flexible, but is incompatible with such a construct. Instead code evaluation is an external global operation that is validated by the proof theory regarding closed proofs of Ë formulas. We demonstrate the relevance of »Ë to staged computation directly by showing that that normalization can be done in an order strictly following the times of the logic. We also extend »Ë to a small functional language, and show that it would serve as a suitable basis for directly programming with multiple stages by presenting some example programs.

Faster polynomial multiplication over finite fields

Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log* n) log p), where log* n=min {k:log ...k times... log n <= 1} stands for the iterated logarithm. This improves on the previously best known bound M_p(n) = O(n log n log log n log p), which essentially goes back to the seventies.

Coin Flipping of Any Constant Bias Implies One-Way Functions

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias (2 - 1)/2 - o(1) H .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.

Property-Directed Inference of Universal Invariants or Proving Their Absence

We present Universal Property Directed Reachability (PDR), a property-directed semi-algorithm for automatic inference of invariants in a universal fragment of first-order logic. PDR is an extension of Bradley's PDR/IC3 algorithm for inference of propositional invariants. PDR terminates when it either discovers a concrete counterexample, infers an inductive universal invariant strong enough to establish the desired safety property, or finds a proof that such an invariant does not exist. PDR is not guaranteed to terminate. However, we prove that under certain conditions, e.g., when reasoning about programs manipulating singly-linked lists, it does. We implemented an analyzer based on PDR, and applied it to a collection of list-manipulating programs. Our analyzer was able to automatically infer universal invariants strong enough to establish memory safety and certain functional correctness properties, show the absence of such invariants for certain natural programs and specifications, and detect bugs. All this, without the need for user-supplied abstraction predicates.

All ACM Journals | See Full Journal Index

Search JACM
enter search term and/or author name