Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
Journal of the ACM
ACM Press
  1-10 of 406 reviews Date Reviewed 
  Near optimal online algorithms and fast approximation algorithms for resource allocation problems
Devanur N., Jain K., Sivan B., Wilkens C.  Journal of the ACM 66(1): 1-41, 2019. Type: Article

The resource allocation problem is an age-old problem with a rich history. This paper revisits the resource allocation problem, albeit in a different setting, finding “a middle ground between worst-case and stochastic [analyses]”: the ...

Sep 21 2021
   Exact algorithms via monotone local search
Fomin F., Gaspers S., Lokshtanov D., Saurabh S.  Journal of the ACM 66(2): 1-23, 2019. Type: Article

Many important problems are NP-complete; this means that, unless P = NP, we cannot have a polynomial-time (feasible) algorithm for solving all instances of this problem. For each such problem, there is an exhaustive search algorithm that requires ...

Apr 26 2021
  Computing the geometric intersection number of curves
Despré V., Lazarus F.  Journal of the ACM 66(6): 1-49, 2019. Type: Article

More than a century ago, Poincaré asked for a procedure to determine if a closed curve γ on a compact surface S could be contracted to a point, and suggested a computationally expensive method. Dehn proposed a simpler ...

Jan 1 2021
  Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation
Wirth F., Stüdli S., Yu J., Corless M., Shorten R.  Journal of the ACM 66(4): 1-37, 2019. Type: Article

The transmission control protocol (TCP) that underpins most Internet traffic has a simple yet intuitively beautiful algorithm for congestion control. Every connection will gradually ramp up the bandwidth it uses until congestion occurs, at which p...

Oct 19 2020
  The salesman’s improved paths through forests
Seb A., Zuylen A.  Journal of the ACM 66(4): 1-16, 2019. Type: Article

Given a set of cities and a function that gives the cost of traveling from one city to another, the traveling salesman problem (TSP) determines a circuit of minimal cost that 1) starts and ends in the same city and 2) passes through each city only...

Sep 19 2019
  The PCL theorem: transactions cannot be parallel, consistent, and live
Bushkov V., Dziuma D., Fatourou P., Guerraoui R.  Journal of the ACM 66(1): 1-66, 2019. Type: Article

Transactional memory is one approach to making highly parallel programming manageable. In such approaches, parallel memory accesses are treated somewhat similarly to transactions in a database system, ideally guaranteeing properties similar to the...

Apr 15 2019
  Computing the homology of basic semialgebraic sets in weak exponential time
Bürgisser P., Cucker F., Lairez P.  Journal of the ACM 66(1): 1-30, 2019. Type: Article

A semialgebraic set is a subset of a finite-dimensional Euclidean space defined by a finite list of polynomial equalities and inequalities. These sets can be weird, so it desirable to be able to describe their topological shape, in particular, to ...

Mar 26 2019
  Circuit complexity, proof complexity, and polynomial identity testing: the ideal proof system
Grochow J., Pitassi T.  Journal of the ACM 65(6): 1-59, 2018. Type: Article

Cook and Reckhow [1] proved that NP ≠ coNP if and only if in every propositional proof system there is a tautology whose proof size has a super-polynomial lower bound (in terms of the size of the proved formula). Currently, it is not known w...

Feb 13 2019
  Plane formation by synchronous mobile robots in the three-dimensional Euclidean space
Yamauchi Y., Uehara T., Kijima S., Yamashita M.  Journal of the ACM 64(3): 1-43, 2017. Type: Article

This is an interesting and thorough investigation of the plane formation problem. This problem addresses how a large group of robots moving in 3D Euclidean space--that can see but have no identification, no access to a common coordinate syste...

Feb 16 2018
  Improved algorithms for constructing consensus trees
Jansson J., Shen C., Sung W.  Journal of the ACM 63(3): 1-24, 2016. Type: Article

A phylogenetic tree is a popular structure used by both biologists and computer scientists to infer evolutionary relationships among various species. In spite of its popularity, different methods, datasets, heuristics and so on used to generate th...

Feb 8 2017
Display per column
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy