Frontiers of Algorithmics: International Joint Conference, IJTCS-FAW 2021, Beijing, China, August 16–19, 2021, Proceedings

Description

This book constitutes the proceedings of the 15th International Workshop on Frontiers in Algorithmics, FAW 2021, held in conjunction with second International Joint Conference on Theoretical Computer Science (IJTCS 2021), as IJTCS-FAW 2021, in Beijing, China, in August 2021.  The conference IJTCS-FAW 2021 was held in hybrid mode due to the COVID-19 pandemic. The 5 full papers presented in this volume were carefully reviewed and selected from 9 submissions. The joint conference provides a focused forum on Algorithmic Game Theory, Blockchain, Multi-agent Reinforcement Learning, Quantum Computation, Theory of Machine Learning, Machine Learning, Formal Method, Algorithm and Complexity, and EconCS. Preface Organization Keynote Speeches Insights from the Conscious Turing Machine (CTM) Speculative Smart Contracts Optimization from Structured Samples—An Effective Approach for Data-Driven Optimization Recent Developments in Property Testing of Boolean Functions AC0 Circuits, First-Order Logic, and Well-Structured Graphs Model-Based Digital Engineering and Verification of Intelligent Systems Tight Online Algorithms for Unrelated Machine Load Balancing with Predictions Fast Sampling Constraint Satisfaction Solutions via the Lovász Local Lemma Contents Papers and Talks Presented in IJTCS Tracks A-F and H-I, and the Forums Full Papers Pool Block Withholding Attack with Rational Miners 1 Introduction 1.1 Main Results 1.2 Related Work 2 Models and Preliminaries 2.1 Betray-and-Return Model 2.2 Betray-and-Not-Return Model 3 Betray-and-Return Model 3.1 A Single Miner's Best Reaction 3.2 Pool 1's Optimal Strategy 3.3 Simulations 4 Betray-and-Not-Return Model 4.1 Attacking a Single Pool 4.2 Attacking Multiple Pools and Simulations 5 Conclusion A Appendix A.1 Experiments in the BR Model A.2 Experiments in the BNR Model References Approximation Algorithms for the Directed Path Partition Problems 1 Introduction 2 Approximation Algorithms 2.1 The First k/2-Approximation for kPP 2.2 An Improved (k+2)/3-Approximation for kPP, When k 7 2.3 A 13/9-Approximation for 3PP 3 Final Remarks References Faster Algorithms for k-SubsetSum and Variations 1 Introduction 1.1 Related Work 1.2 Our Contribution 2 Preliminaries 2.1 Notation 2.2 Using FFT for SubsetSum 3 k-SubsetSum 3.1 Solving k-SubsetSum in Deterministic (nk/(k+1) tk) Time 3.2 Solving k-SubsetSum in Randomised (n + tk) Time 4 Faster Algorithms for Multiple Subset Problems 5 Future Work References Hardness and Algorithms for Electoral Manipulation Under Media Influence 1 Introduction 2 Problem Formalization 3 Strong Intractability for the EMMI Problem 4 Algorithms for a Special Setting of EMMI 4.1 A Dynamic Programming for EMMI-Laminar 5 Conclusion References Improved Approximation Algorithms for Multiprocessor Scheduling with Testing 1 Introduction 2 Preliminaries 3 The General Testing Case 4 The Uniform Testing Case 5 Conclusion References Author Index