Theory and Applications of Models of Computation: 16th International Conference, TAMC 2020, Changsha, China, October 18–20, 2020, Proceedings (Theoretical ... Science and General Issues Book 12337)

This book constitutes the refereed proceedings of the 16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020, held in Changsha, China, in October 2020. The 37 full papers were carefully reviewed and selected from 83 submissions. The main themes of the selected papers are computability, complexity, algorithms, information theory and their extensions to machine learning theory and foundations of artificial intelligence. Front Matter ....Pages i-xi Semilattices of Punctual Numberings (Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev)....Pages 1-12 Partial Sums on the Ultra-Wide Word RAM (Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen)....Pages 13-24 Securely Computing the n-Variable Equality Function with 2n Cards (Suthee Ruangwises, Toshiya Itoh)....Pages 25-36 Polynomial Kernels for Paw-Free Edge Modification Problems (Yixin Cao, Yuping Ke, Hanchun Yuan)....Pages 37-49 Floorplans with Walls (Katsuhisa Yamanaka, Shin-ichi Nakano)....Pages 50-59 A Primal-Dual Randomized Algorithm for the Online Weighted Set Multi-cover Problem (Wenbin Chen, Fufang Li, Ke Qi, Miao Liu, Maobin Tang)....Pages 60-68 Sumcheck-Based Delegation of Quantum Computing to Rational Server (Yuki Takeuchi, Tomoyuki Morimae, Seiichiro Tani)....Pages 69-81 Online Removable Knapsack Problems for Integer-Sized Items (Kanaho Hanji, Hiroshi Fujiwara, Hiroaki Yamamoto)....Pages 82-93 An Improved Approximation Algorithm for the Prize-Collecting Red-Blue Median Problem (Zhen Zhang, Yutian Guo, Junyu Huang)....Pages 94-106 LP-Based Algorithms for Computing Maximum Vertex-Disjoint Paths with Different Colors (Yunyun Deng, Yi Chen, Kewen Liao, Longkun Guo)....Pages 107-118 A Constant Factor Approximation for Lower-Bounded k-Median (Yutian Guo, Junyu Huang, Zhen Zhang)....Pages 119-131 Reverse Mathematics, Projective Modules and Invertible Modules (Huishan Wu)....Pages 132-143 Two-Stage Submodular Maximization Problem Beyond Non-negative and Monotone (Zhicheng Liu, Hong Chang, Ran Ma, Donglei Du, Xiaoyan Zhang)....Pages 144-155 Optimal Matroid Bases with Intersection Constraints: Valuated Matroids, M-convex Functions, and Their Applications (Yuni Iwamasa, Kenjiro Takazawa)....Pages 156-167 On the Complexity of Acyclic Modules in Automata Networks (Kévin Perrot, Pacôme Perrotin, Sylvain Sené)....Pages 168-180 Eternal Connected Vertex Cover Problem (Toshihiro Fujito, Tomoya Nakamura)....Pages 181-192 Parametric Streaming Two-Stage Submodular Maximization (Ruiqi Yang, Dachuan Xu, Longkun Guo, Dongmei Zhang)....Pages 193-204 Approximation Guarantees for Deterministic Maximization of Submodular Function with a Matroid Constraint (Xin Sun, Dachuan Xu, Longkun Guo, Min Li)....Pages 205-214 A Novel Initialization Algorithm for Fuzzy C-means Problem (Qian Liu, Jianxin Liu, Min Li, Yang Zhou)....Pages 215-225 On the Parameterized Complexity of d-Restricted Boolean Net Synthesis (Ronny Tredup, Evgeny Erofeev)....Pages 226-238 Approximate #Knapsack Computations to Count Semi-fair Allocations (Theofilos Triommatis, Aris Pagourtzis)....Pages 239-250 Characterizations and Approximability of Hard Counting Classes Below \(\#\mathsf {P}\) (Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis)....Pages 251-262 On Existence of Equilibrium Under Social Coalition Structures (Bugra Caskurlu, Ozgun Ekici, Fatih Erdem Kizilkaya)....Pages 263-274 Space Complexity of Streaming Algorithms on Universal Quantum Computers (Yanglin Hu, Darya Melnyk, Yuyi Wang, Roger Wattenhofer)....Pages 275-286 On Coresets for Support Vector Machines (Murad Tukan, Cenk Baykal, Dan Feldman, Daniela Rus)....Pages 287-299 Tractabilities for Tree Assembly Problems (Feng Shi, Jie You, Zhen Zhang, Jingyi Liu)....Pages 300-312 On Characterization of Petrie Partitionable Plane Graphs (Xin He, Huaming Zhang)....Pages 313-326 Disjunctive Propositional Logic and Scott Domains (Longchun Wang, Qingguo Li)....Pages 327-339 Dispersing and Grouping Points on Segments in the Plane (Xiaozhou He, Wenfeng Lai, Binhai Zhu, Peng Zou)....Pages 340-351 Synchronizing Words and Monoid Factorization: A Parameterized Perspective (Jens Bruchertseifer, Henning Fernau)....Pages 352-364 Hidden Community Detection on Two-Layer Stochastic Models: A Theoretical Perspective (Jialu Bao, Kun He, Xiaodong Xin, Bart Selman, John E. Hopcroft)....Pages 365-376 A Primal-Dual Algorithm for Euclidean k-Means Problem with Penalties (Chunying Ren, Dachuan Xu, Donglei Du, Min Li)....Pages 377-389 The Complexity of the Partition Coloring Problem (Zhenyu Guo, Mingyu Xiao, Yi Zhou)....Pages 390-401 FPT Algorithms for Generalized Feedback Vertex Set Problems (Bin Sheng)....Pages 402-413 Fixed-Order Book Thickness with Respect to the Vertex-Cover Number: New Observations and Further Analysis (Yunlong Liu, Jie Chen, Jingui Huang)....Pages 414-425 Acyclic Edge Coloring Conjecture Is True on Planar Graphs Without Intersecting Triangles (Qiaojun Shu, Yong Chen, Shuguang Han, Guohui Lin, Eiji Miyano, An Zhang)....Pages 426-438 On Pure Space vs Catalytic Space (Sagar Bisoyi, Krishnamoorthy Dinesh, Jayalal Sarma)....Pages 439-451 Back Matter ....Pages 453-454