StringologyTimes

Data Structures and Algorithms: 2017/4/15-21

1: Maximal Unbordered Factors of Random Strings
2: Additive Spanners and Distance Oracles in Quadratic Time
3: The Entropy of Backwards Analysis
4: A Simple Randomized Algorithm to Compute Harmonic Numbers and Logarithms
5: SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
6: On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
7: Pseudo-Separation for Assessment of Structural Vulnerability of a Network
8: FMtree: A fast locating algorithm of FM-indexes for genomic data
9: Negative Cycle Separation in Wireless Network Design
10: Generic LSH Families for the Angular Distance Based on Johnson-Lindenstrauss Projections and Feature Hashing LSH
11: Outward Influence and Cascade Size Estimation in Billion-scale Networks
12: Nearly Tight Bounds for Sandpile Transience on the Grid
13: Certificate Transparency with Enhancements and Short Proofs
14: Space-Optimal Majority in Population Protocols
15: On the k-Means/Median Cost Function
16: A Faster Implementation of Online Run-Length Burrows-Wheeler Transform
17: Grammar-Based Graph Compression
18: Positive-instance driven dynamic programming for treewidth
19: The Robot Routing Problem for Collecting Aggregate Stochastic Rewards
20: Online Weighted Matching: Breaking the $\frac{1}{2}$ Barrier
21: Online Degree-Bounded Steiner Network Design
22: 1D Modeling of Sensor Selection Problem for Weak Barrier Coverage and Gap Mending in Wireless Sensor Networks
23: Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching
24: m-Bonsai: a Practical Compact Dynamic Trie
25: Sorting sums of binary decision summands
26: Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
27: Beating 1-1/e for Ordered Prophets
28: On fast bounded locality sensitive hashing
29: Temporal Clustering
30: Optimal Query Time for Encoding Range Majority
31: Cell-Probe Lower Bounds from Online Communication Complexity
32: A Time Hierarchy Theorem for the LOCAL Model
33: Shared processor scheduling
34: The Ising Partition Function: Zeros and Deterministic Approximation
35: Fairness in Resource Allocation and Slowed-down Dependent Rounding
36: Minimal Controllability of Conjunctive Boolean Networks is NP-Complete