Theory of Computing ------------------- Title : Special Issue: APPROX-RANDOM 2020: Guest Editor's Foreword Authors : Jaroslaw Byrka and Raghu Meka Volume : 19 Number : 5 Pages : 1-3 URL : https://theoryofcomputing.org/articles/v019a005 Abstract -------- Special Issue: APPROX-RANDOM 2020 Guest Editors' Foreword This collection contains the expanded and fully refereed versions of selected papers presented at the 24th International Conference on Randomization and Computation (RANDOM 2020), and the 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020). Due to COVID-related travel restrictions, the conferences were jointly organized in a virtual setup on August 17--19, 2020. The proceedings of the meetings was published in the Dagstuhl LIPIcs series. APPROX published 34 contributed papers and RANDOM published 30 contributed papers, selected by the program committees. The total number of submissions was 67 for each conference. In consultation with the RANDOM PC, PC chair and guest editor Raghu Meka invited three papers to this Special Issue and the authors of the following two papers accepted the invitation: * "Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov chains" by Sarah Miracle, Amanda Streib and Noah Streib * "Reaching a Consensus on Random Networks: The Power of Few" by Linh Tran and Van Vu. In consultation with the APPROX PC, PC chair and guest editor Jarosław Byrka invited the following three papers to this Special Issue. * "Pinning Down the Strong Wilber 1 Bound for Binary Search Trees" by Parinya Chalermsook, Julia Chuzhoy and Thatchaphol Saranurak * "Maximizing the Correlation: Extending Grothendieck's Inequality to Large Domains" by Dor Katzelnick and Roy Schwartz * "Parametrized Metrical Task Systems" by Sébastien Bubeck and Yuval Rabani. These five papers were refereed in accordance with the rigorous standards of Theory of Computing. We would like to thank the authors for their contributions and the anonymous referees for their hard work that helped improve this issue. We are especially indebted to the referees for their detailed and high quality reviews. It was a pleasure to edit this Special Issue for Theory of Computing. November 14, 2023 Jarosław Byrka Guest Editor for APPROX 2020 Raghu Meka Guest Editor for RANDOM 2020 ------------------------------------- APPROX 2020 Program Committee Nikhil Bansal, CWI & TU Eindhoven Jarosław Byrka, U. Wrocław, PC chair Andreas Emil Feldmann, Charles U., Prague Naveen Garg, IIT Delhi Anupam Gupta, Carnegie Mellon U. Pasin Manurangsi, Google Research Evangelos Markakis, AUEB, Athens Nicole Megow, U. Bremen Marcin Mucha, U. Warsaw Harald Räcke, TU Munich Laura Sanità, TU Eindhoven & U. Waterloo Chaitanya Swamy, U. Waterloo Jakub Tarnawski, Microsoft Research Anke van Zuylen, William and Mary David Williamson, Cornell RANDOM 2020 Program Committee Nima Anari, Stanford Eshan Chattopadhyay, Cornell Gil Cohen, Tel Aviv U. Parikshit Gopalan, VmWare Research Prahladh Harsha, Tata Institute of Fundamental Research Sam Hopkins, UC Berkeley Valentine Kabanets, Simon Fraser Un. Gautam Kamath, U. Waterloo Tali Kaufman, Bar-Ilan U. Yin-Tat Lee, U. Washington Sepideh Mahabadi, TTIC Chicago Raghu Meka, UCLA, PC chair Jelani Nelson, UC Berkeley Ryan O'Donnell, Carnegie Mellon Ilya Razenshteyn, Microsoft Research Barna Saha, UC Berkeley Tselil Schramm, Stanford Madhu Sudan, Harvard Avishay Tal, UC Berkeley Eric Vigoda, Georgia Tech Mary Wootters, Stanford ------------------------------------- Brief synopses of papers in the Special Issue * "Reaching a Consensus on Random Networks: The Power of Few" by Linh Tran and Van Vu. This paper studies a classical question in population dynamics: Imagine we have $n$ people connected by a graph, and each node starts with a red or blue color. Each subsequent day, every person revises their color based on some function of the colors of their neighbors. Let us say that a color wins if all people are of that color. How sensitive is the winning color to the initial configuration? The paper shows, surprisingly, that under the natural `majority rule' (a vertex adopts the color of the majority of its neighbors), if the graph is a random one, then flipping a constant number of vertices near the decision boundary will change the color with a high probability. That is, if there are $n/2+c$ nodes of one color at the beginning, then that color is very likely to win. The main point is that the advantage needed to make one color the overwhelming favorite does not depend on$ n$. For instance, if there are $n/2+5$ red nodes initially, red wins within four days with probability greater than .9. The key difficulty in analyzing the dynamics is that after one step, the colors of the nodes and the random graph are dependent. Hence, it is difficult to apply concentration inequalities. The authors find a clever way to overcome such dependency issues and obtain a tight analysis of the dynamics. * "Pinning Down the Strong Wilber 1 Bound for Binary Search Trees" by Parinya Chalermsook, Julia Chuzhoy and Thatchaphol Saranurak The Dynamic Optimality conjecture of Sleator and Tarjan is relatively easy to state, but remains one of the most intriguing open problems in the area of data structures. Here it is: we want to maintain a dynamic binary search tree (BST) as some set of elements is accessed via a request sequence. Since the access sequence may have some structure, we are allowed to change the BST in some local ways (via "rotations") to reduce the access cost. The Dynamic Optimality conjecture says: for each sequence of accesses, the total cost incurred by the Splay Tree data structure is within a constant factor of the optimal cost (the cost incurred by the best dynamic BST for \emph{that} sequence). We can also ask a weaker question: does there exist any algorithm that performs almost optimally on each access sequence? We do not yet know. In order to get such a universally optimal algorithm, these questions force us to understand the power and inherent trade-offs of basic data structures like BSTs. What is the optimal cost of a dynamic BST on some sequence? Previous attempts to reason about this optimal cost use one of two bounds proved by Wilbur in 1986. And until recently it seemed conceivable that either of these bounds was within a constant factor of the optimal cost. This paper shows that the first bound (WB-1) can be a factor of nearly $\Omega(\log \log n)$ away from the optimal cost on some instances. [Lecomte and Weinstein independently proved the same gap.] Moreover, the paper gives another bound, called the Guillotine bound, which may be useful in resolving the conjecture. Finally, they ask the algorithmic question: given a sequence, how to compute the optimal cost on it? The final result of this paper is an algorithm that smoothly translates between an $O(\log \log n)$-approximation in polynomial time, and an exact algorithm in exponential time. We do not know how to compute a constant-approximation in polynomial time. The Dynamic Optimality conjecture still remains tantalizingly open, but this paper deepens our understanding of this fascinating question.