In memory of Ker-I Ko

Preface......Page 7
Contents......Page 8
In Memoriam: Ker-I Ko (1950–2018)......Page 10
 References......Page 12
 1 Introduction: A Brief History of Time-Bounded Kolmogorov Complexity......Page 17
 2 Time-Bounded Kolmogorov Complexity and NP-Completeness......Page 20
 References......Page 23
The Power of Self-Reducibility: Selectivity, Information, and Approximation......Page 28
  1.1 A Note on the Two Audiences, and How to Read This Chapter......Page 29
 2 Definitions Used Throughout: SAT and Self-Reducibility......Page 33
  3.1 Needed Definitions......Page 35
  3.2 Can SAT Be P-Selective?......Page 36
  4.2 Can SAT Reduce to a Tally Set?......Page 37
  5.1 Needed Definitions......Page 38
  5.2 Can SAT Reduce to a Sparse Set?......Page 39
  6.1 Needed Definitions......Page 40
  6.3 Is #SAT as Hard to (Enumeratively) Approximate as It Is to Solve Exactly?......Page 41
 7 Going Big: Complexity-Class Implications......Page 42
 A  Solution to Challenge Problem 1......Page 44
 B  Solution to Challenge Problem 2......Page 47
 C  Solution to Challenge Problem 3......Page 50
  D.2  XYZ Idea/Statement......Page 52
  D.4  Proof Sketch of the Theorem......Page 53
 References......Page 54
 1 Introduction......Page 57
 2 Algorithmic Information and Algorithmic Dimensions......Page 58
 3 Point-to-Set Principles......Page 59
 5 Fractal Intersections......Page 61
 6 Kakeya Sets and Generalized Furstenberg Sets......Page 62
 References......Page 63
 1 Introduction......Page 66
 2 Preliminaries......Page 67
 3 On the Hardness of Probability Distributions......Page 68
 4 Approximating the Restart Time......Page 71
 References......Page 74
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets......Page 76
 1 Introduction......Page 77
 2 Reducing from the Worst-Case to the Average-Case: Limits of Black-Box Reductions......Page 78
 3 A Motivation for Investigating Non-black-box Reductions Further......Page 79
 4 Our Results......Page 81
 5 Why Are the Reductions of ch6Hirahara18spsfocsspsconf Non-black-box?......Page 82
 6 Our Techniques......Page 83
 7 Some Evidence for the Tightness of Our Upper Bounds......Page 85
 References......Page 86
 1 Introduction......Page 89
  1.1 Overview......Page 90
 2 Representing Divergence-Free L2 Functions on......Page 93
 3 Computability of Helmholtz Projection......Page 96
 4 Computability of the Linear Problem......Page 98
 5 Extension to the Nonlinear Problem......Page 103
  5.1 Representing and Operating on Space Hs2, 0()......Page 104
  5.2 Some Classical Properties of Fractional Powers of A......Page 106
  5.3 Proof of Proposition4......Page 107
  5.4 Proof of Proposition5......Page 115
  5.5 The Inhomogeneous Case and Pressure......Page 116
 A  Proof of Proposition1......Page 117
 B  Proof of Lemma1......Page 119
 References......Page 120
AutoOverview: A Framework for Generating Structured Overviews over Many Documents......Page 122
 1 Introduction......Page 123
  2.2 Hierarchical Topic Clustering......Page 125
  2.4 Statistics and Trends of Entities......Page 128
  2.7 Assembling......Page 129
  3.2 Information Coverage......Page 130
  3.4 Overall Quality......Page 131
  4.1 LDA Clustering......Page 132
  4.3 Affinity Propagation Clustering......Page 133
  5.1 Single-Document Summarization......Page 134
  5.2 SWR......Page 135
  5.3 Multi-Document Summarization......Page 137
 6 Title Generation......Page 139
  6.2 Dependency Trees and Trimming......Page 140
 7 NDORGS: The First Implementation of AutoOverview......Page 141
  7.1 Data Sets......Page 142
  7.3 Settings and Parameters......Page 143
  7.4 Text Clustering Evaluations for Deciding K......Page 144
  7.5 Evaluations of Overall Quality of SOVs......Page 146
 8 Statistics and Trends of Entities......Page 153
 9 Final Comments......Page 155
 References......Page 156
  1.1 Problem Description......Page 160
  1.2 Evaluation Functions......Page 161
  1.3 Our Results......Page 162
 2 Notations......Page 165
 3 An Algorithm Framework for Byzantine Robot Searching Problem......Page 167
  4.1 A Base Algorithm with Lg......Page 170
  4.2 A Base Algorithm with Lg......Page 174
 5 Competitive Ratio Lg for Small Lg and Lg......Page 177
 References......Page 179
 1 Introduction......Page 181
 2 Maximizing Non-monotone Submodular Set Functions......Page 182
 3 Maximizing Non-monotone Submodular Integer Lattice Functions......Page 187
 4 Maximizing Submodular Continuous Functions......Page 190
 References......Page 194
 1 Introduction......Page 196
 2 Model......Page 199
 3 Sequential Location on Directional Stars......Page 202
  4.1 Case 1: n08mu(mod6mus+t)......Page 205
  4.2 Case 2: n18mu(mod6mus+t) and t1......Page 206
  4.3 Case 3: Out-Stars......Page 211
 References......Page 212
 1 Introduction......Page 214
 2 Basic Definitions and a Problem Statement......Page 215
  3.1 A Linear-Time Algorithm......Page 216
  3.2 External-Memory Algorithms and I/O Efficient Algorithms......Page 217
  3.3 Distributed Algorithms......Page 218
  3.4 Core Decomposition on Uncertain Graphs......Page 219
  4.1 Streaming Algorithms......Page 220
  4.3 Parallel Algorithms......Page 222
  4.4 Order-Based Algorithms......Page 223
 5 Applications......Page 224
 References......Page 225
 1 Introduction......Page 228
 2 Preliminaries......Page 229
  3.1 Minimizing the Busy Time Length......Page 230
  3.2 Maximizing the Throughput......Page 233
  4.1 Minimizing the Active Time Length......Page 234
  4.2 Batch Scheduling......Page 235
 References......Page 236
 1 Introduction......Page 239
 2 Preliminaries......Page 240
 3 A Characterization of the Position Value......Page 241
 References......Page 245
 1 Introduction......Page 247
 2 Notation and Preliminaries......Page 248
 3 Two-Phase Algorithm......Page 249
 4 Approximation Ratio of the k-TPH......Page 250
 5 Performance of the k-TPH in General Graphs......Page 257
 References......Page 258
 1 Introduction......Page 261
 2 Preliminaries......Page 264
 3 Review of SCPT Problems Using so......Page 266
  4.2 Unreliable Jobs......Page 271
  4.3 Speed Scaling Machines......Page 272
 5 Conclusion......Page 273
 References......Page 274
 1 Introduction......Page 277
  2.1 The Key Technologies of Blockchain......Page 280
 3 The General Architecture of Edge Computing......Page 283
  4.1 Motivations......Page 285
  4.2 General Architecture......Page 286
  4.3 State of the Art......Page 288
  4.4 Challenges......Page 292
 5 Conclusion......Page 293
 References......Page 294
Author Index......Page 298