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

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