Journal of the ACM
ISSN / EISSN : 0004-5411 / 1557-735X
Published by: Institute of Electrical and Electronics Engineers (IEEE) (10.1145)
Total articles ≅ 3,030
Latest articles in this journal
Journal of the ACM, Volume 68, pp 1-1; https://doi.org/10.1145/3464772
Journal of the ACM, Volume 68, pp 1-26; https://doi.org/10.1145/3450704
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.
Journal of the ACM, Volume 68, pp 1-66; https://doi.org/10.1145/3457606
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms—high-dimensional symmetries of solution spaces—to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a “measure of symmetry” that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any k ≥ 3, it is NP-hard to find a (2 k -1)-colouring of a given k -colourable graph.
Journal of the ACM, Volume 68, pp 1-25; https://doi.org/10.1145/3447579
Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution, as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error. In this work, we develop a framework for augmenting online algorithms with a machine learned predictor to achieve competitive ratios that provably improve upon unconditional worst-case lower bounds when the predictor has low error. Our approach treats the predictor as a complete black box and is not dependent on its inner workings or the exact distribution of its errors. We apply this framework to the traditional caching problem—creating an eviction strategy for a cache of size k . We demonstrate that naively following the oracle’s recommendations may lead to very poor performance, even when the average error is quite low. Instead, we show how to modify the Marker algorithm to take into account the predictions and prove that this combined approach achieves a competitive ratio that both (i) decreases as the predictor’s error decreases and (ii) is always capped by O (log k ), which can be achieved without any assistance from the predictor. We complement our results with an empirical evaluation of our algorithm on real-world datasets and show that it performs well empirically even when using simple off-the-shelf predictions.
Journal of the ACM, Volume 68, pp 1-26; https://doi.org/10.1145/3449352
We prove that for k ≪ 4√ n regular resolution requires length n Ω( k ) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k -clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional n Ω( k ) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
Journal of the ACM, Volume 68, pp 1-35; https://doi.org/10.1145/3453721
We consider the adversarial convex bandit problem and we build the first poly( T )-time algorithm with poly( n ) √ T -regret for this problem. To do so, we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves Õ( n 9.5 √ T )-regret, and we show that a simple variant of this algorithm can be run in poly( n log ( T ))-time per step (for polytopes with polynomially many constraints) at the cost of an additional poly( n ) T o(1) factor in the regret. These results improve upon the Õ( n 11 √ T -regret and exp (poly( T ))-time result of the first two authors and the log ( T ) poly( n ) √ T -regret and log( T ) poly( n ) -time result of Hazan and Li. Furthermore, we conjecture that another variant of the algorithm could achieve Õ( n 1.5 √ T )-regret, and moreover that this regret is unimprovable (the current best lower bound being Ω ( n √ T ) and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order n 3 / ɛ 2 .
Journal of the ACM, Volume 68, pp 1-40; https://doi.org/10.1145/3457389
We show that a context-free grammar of size that produces a single string of length (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for of size , whose unique derivation tree has depth . This solves an open problem in the area of grammar-based compression, improves many results in this area, and greatly simplifies many existing constructions. Similar results are shown for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be all deduced from a single meta-theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to with the cost of a constant multiplicative size increase. Here, refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (noncommutative) semirings.
Journal of the ACM, Volume 68, pp 1-41; https://doi.org/10.1145/3448973
Response time density is obtained in a tandem pair of Markovian queues with both batch arrivals and batch departures. The method uses conditional forward and reversed node sojourn times and derives the Laplace transform of the response time probability density function in the case that batch sizes are finite. The result is derived by a generating function method that takes into account that the path is not overtake-free in the sense that the tagged task being tracked is affected by later arrivals at the second queue. A novel aspect of the method is that a vector of generating functions is solved for, rather than a single scalar-valued function, which requires investigation of the singularities of a certain matrix. A recurrence formula is derived to obtain arbitrary moments of response time by differentiation of the Laplace transform at the origin, and these can be computed rapidly by iteration. Numerical results for the first four moments of response time are displayed for some sample networks that have product-form solutions for their equilibrium queue length probabilities, along with the densities themselves by numerical inversion of the Laplace transform. Corresponding approximations are also obtained for (non-product-form) pairs of “raw” batch-queues—with no special arrivals—and validated against regenerative simulation, which indicates good accuracy. The methods are appropriate for modeling bursty internet and cloud traffic and a possible role in energy-saving is considered.
Journal of the ACM, Volume 68, pp 1-30; https://doi.org/10.1145/3448213
Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with blocking (FJQN/B). While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize their throughput performance at scale theoretically. What further complicates the study is the presence of heavy-tailed delays that have been widely documented therein. In this article, we utilize an infinite sequence of FJQN/Bs to study the throughput limit and focus on an important class of heavy-tailed service times that are regularly varying with index . The throughput is said to be scalable if the throughput limit infimum of the sequence is strictly positive as the network size grows to infinity. We introduce two novel geometric concepts—scaling dimension and extended metric dimension—and show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension and only if the scaling dimension . We also show that for the cases where buffer sizes are scaling in an order of , the scalability conditions are relaxed by a factor of . The results provide new insights on the scalability of a rich class of FJQN/Bs with various structures, including tandem, lattice, hexagon, pyramid, tree, and fractals.
Journal of the ACM, Volume 68, pp 1-36; https://doi.org/10.1145/3446330
We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.