Structural Information and Communication Complexity: 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27–29, 2022, Proceedings (Lecture Notes in Computer Science, 13298)

This book constitutes the refereed conference proceedings of the 29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022, held in Paderborn, Germany, in June 2022. The 16 full papers presented in this book were carefully reviewed and selected from 30 submissions. SIROCCO is devoted to the study of the interplay between structural knowledge, communication, and computing in decentralized systems of multiple communicating entities. Special emphasis is given to innovative approaches leading to better understanding of the relationship between computing and communication. Preface Organization Contents Local Mending 1 Introduction 2 Contributions and Key Ideas 3 Related Work 4 Defining Mendability 4.1 Additional Definitions 5 From Local Mendability to Local Solvability 6 From Local Solvability to Local Mendability 6.1 Cycles 7 Landscape of Mendability References Proof Labeling Schemes for Reachability-Related Problems in Directed Graphs 1 Introduction 2 Related Work 3 Preliminaries 4 Building Blocks 4.1 DFS-Based Schemes 4.2 Canonical Proof Labeling Scheme 4.3 The Charge-Distribution Protocol 5 Decidability of Reachability-Related Problems 5.1 Global Source 5.2 Global Sink 5.3 Strong Connectivity 6 Sufficient and Necessary Conditions for Universal Decidability 7 Conclusion References On the Computational Power of Energy-Constrained Mobile Robots: Algorithms and Cross-Model Analysis 1 Introduction 2 Models and Preliminaries 3 Computational Relationship Between Rsynch and Ssynch 3.1 Power of Rsynch in FC,FS and OB 3.2 Power of Rsynch in 4 Computational Relationship Between Fsynch and Rsynch 4.1 Dominance of Fsynch over Rsynch 4.2 Orthogonality of Fsynch with Rsynch 5 Analysis Within Rsynch 6 Concluding Remarks References Randomized Strategies for Non-additive 3-Slope Ski Rental 1 Introduction 2 Preliminaries: Profiles and Transition Functions 3 Optimal Profile for Three Slopes 3.1 Progressive and Tight Pairs of Profile and Transition Function 3.2 Reconstruction: Profile and Transition Function 4 Computing a Near-Optimal Strategy 4.1 Monotonicity of the Competitive Ratio and Interval 4.2 Outline of Our Algorithm 5 Future Directions References Accelerated Information Dissemination on Networks with Local and Global Edges 1 Introduction 2 Preliminaries 2.1 Percolation Processes 2.2 Graph Classes 3 Extreme Thresholds 4 Polynomial-to-Rapid Activation Rate 4.1 Polynomial Rate 4.2 Rapid Rate on the Global Graph 5 Experimental Results 5.1 Erdős–Rényi Graphs 5.2 Other Global-Graph Models 6 Outlook References Phase Transition of the 3-Majority Dynamics with Uniform Communication Noise 1 Introduction 1.1 Our Results and Their Consequences 1.2 Related Works 1.3 Structure of the Paper 2 Preliminaries 3 Results 4 Analysis 4.1 Victory of the Majority 4.2 Symmetry Breaking 4.3 Victory of Noise References A Meta-Theorem for Distributed Certification 1 Introduction 2 Preliminaries 3 A Protocol Certifying a 3-Approximation of the Treewidth 4 Certifying Regular Properties 5 Conclusion References The Red-Blue Pebble Game on Trees and DAGs with Large Input 1 Introduction 1.1 Related Work 1.2 The Red-Blue Pebble Game 1.3 Notations and Definitions 2 Bounds for Trees 3 Bounds for General DAGs 4 I/O-Bounds in a Parallel Setting 5 Experiments 5.1 Regular Tree, Varying Memory Size 5.2 Random DAGs with Large Inputs 5.3 General Random DAGs with Varying Numbers of Vertices 6 Conclusions References Local Planar Domination Revisited 1 Introduction 2 Preliminaries 3 Phase 1: Preprocessing 4 Phase 2: Analyzing the Local Dominators 5 Phase 3: LP-Based Approximation 5.1 LP-Based Approximation 5.2 Solving LPs Locally 5.3 From Bounded Residual Degree to Bounded Degree 5.4 Conclusion of the Algorithm 6 Alternative Phase 3: Greedy Domination in Planar Graphs of Maximum Residual Degree 7 Restricted Classes of Planar Graphs 7.1 LP-Based Approximation 7.2 Greedy Approximation References Election in Fully Anonymous Shared Memory Systems: Tight Space Bounds and Algorithms 1 Introduction 1.1 Leader Election 1.2 System Models 1.3 Related Works on Anonymous Memories 1.4 Motivation and Content 2 d-Election in the RMW Model Where Participation is Not Required 2.1 A Necessary Condition for d-election 2.2 A d-election algorithm in RMW fully anonymous systems 2.3 Proof of Algorithm 1 3 Exact d-election in the RMW Model Where Participation is Required 3.1 A Necessary Condition for Exact d-election 3.2 An Exact d-election algorithm 3.3 Proof of Algorithm 2 4 d-Election in the RMW Model Where Participation is Required 4.1 A Necessary Condition for d-election 4.2 A Necessary and Sufficient Condition for d-election 5 Impossibility in the RW Communication Model 6 Conclusion A The Case Where m=1 References Dispersion of Mobile Robots on Directed Anonymous Graphs 1 Introduction 2 Model and Preliminaries 3 Impossibility and Lower Bounds 4 DFS Dispersion Algorithm 4.1 Analysis of the Algorithm 5 BFS Dispersion Algorithm 6 Extensions to Crash Faults References Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes 1 Introduction 1.1 Proof-Labeling Schemes and Distributed Interactive Proofs 1.2 Geometric Intersection Graph Classes 1.3 Our Results 1.4 Related Work 2 Preliminaries 3 Toolbox 3.1 Spanning Tree and Related Problems 3.2 Problems Equality and Permutation 4 Permutation and Trapezoid Graphs 5 Circle and Polygon Circle Graphs 6 Lower Bounds References Exactly Optimal Deterministic Radio Broadcasting with Collision Detection 1 Introduction 2 Model 3 Related Work 4 Algorithm 5 Lower Bound 6 Future Work References Lower Bounds on Message Passing Implementations of Multiplicity-Relaxed Queues and Stacks 1 Introduction and Related Work 2 Model and Definitions 2.1 System Model 2.2 Multiplicity 2.3 Shifting Arguments 3 Worst-Case Lower Bounds 3.1 Dequeue and Pop 3.2 Amortized Cost Lower Bounds 3.3 Bound on Sum of Operations 4 Tightness 5 Conclusion References Fixed Points and 2-Cycles of Synchronous Dynamic Coloring Processes on Trees 1 Introduction 2 State of the Art 3 Synchronous Discrete-Time Dynamical Systems 3.1 Notation 4 Fixed Points 4.1 The Bijection Bfix 4.2 Counting Fixed Points 4.3 Generating Fixed Points 5 General 2-Cycles 5.1 General Results 5.2 Pure 2-Cycles 5.3 Counting Pure 2-Cycles 5.4 Block Trees of 2-Cycles 5.5 Counting Block Trees 6 Conclusion and Open Problems References Foremost Non-stop Journey Arrival in Linear Time 1 Introduction 2 Journey in a Temporal (di)graph 3 From Journey to Time Set 4 Foremost Non-stop Journey Arrival in Linear Time 5 Conclusion and Perspectives References Author Index