Search
w/in this Title
for Titles
All Reviews
Journal of the ACM
ACM Press
Options:
Date Reviewed
Title
Author
Publisher
Published Date
Descending Order
Ascending Order
110 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): 141, 2019. Type: Article
The resource allocation problem is an ageold problem with a rich history. This paper revisits the resource allocation problem, albeit in a different setting, finding “a middle ground between worstcase 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): 123, 2019. Type: Article
Many important problems are NPcomplete; this means that, unless P = NP, we cannot have a polynomialtime (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): 149, 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 placedependent Markov chains, unsynchronised AIMD, and optimisation
Wirth F., Stüdli S., Yu J., Corless M., Shorten R. Journal of the ACM 66(4): 137, 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): 116, 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): 166, 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): 130, 2019. Type: Article
A semialgebraic set is a subset of a finitedimensional 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): 159, 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 superpolynomial 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 threedimensional Euclidean space
Yamauchi Y., Uehara T., Kijima S., Yamashita M. Journal of the ACM 64(3): 143, 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 spacethat 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): 124, 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
5
10
15
25
50
100
per column
Reproduction in whole or in part without permission is prohibited. Copyright © 20002021 ThinkLoud, Inc.
Terms of Use

Privacy Policy