StringologyTimes

Data Structures and Algorithms: 2016/7/15-21

1: Edit Distance: Sketching, Streaming and Document Exchange
2: Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
3: Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
4: Heuristics for Packing Semifluids
5: Edge-Orders
6: Online Grammar Compression for Frequent Pattern Discovery
7: Number representations and term rewriting
8: Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
9: On Distance-$d$ Independent Set and other problems in graphs with few minimal separators
10: Local Search for Max-Sum Diversification
11: Best-case Analysis of MergeSort with an Application to the Sum of Digits Problem, A manuscript (MS) v2
12: The complexity of tropical graph homomorphisms
13: Robust algorithms with polynomial loss for near-unanimity CSPs
14: Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)
15: Fully Dynamic de Bruijn Graphs
16: Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
17: An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
18: An optimization approach to locally-biased graph algorithms
19: Distributed Graph Clustering by Load Balancing
20: An Extended Note on the Comparison-optimal Dual Pivot Quickselect
21: Minimum cycle and homology bases of surface embedded graphs
22: Partitioning a Graph into Small Pieces with Applications to Path Transversal
23: Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
24: Fully dynamic all-pairs shortest paths with worst-case update-time revisited
25: Improved Hardness for Cut, Interdiction, and Firefighter Problems
26: Multi-view pattern matching
27: On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
28: Multidimensional Dynamic Pricing for Welfare Maximization
29: Distance Sensitive Bloom Filters Without False Negatives
30: Spanning Circuits in Regular Matroids
31: An Approximation Algorithm for the Art Gallery Problem
32: Distributed Construction of Purely Additive Spanners
33: Streaming k-mismatch with error correcting and applications
34: How to Discreetly Spread a Rumor in a Crowd
35: Erasure-Resilient Property Testing
36: Minimizing Uncertainty through Sensor Placement with Angle Constraints
37: On the Geodesic Centers of Polygonal Domains
38: Conditionally Optimal Algorithms for Generalized B"uchi Games
39: Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
40: Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
41: Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
42: Stochastic dominance and the bijective ratio of online algorithms
43: Strong Hardness of Privacy from Weak Traitor Tracing
44: Faster Graph Coloring in Polynomial Space
45: Greedy bi-criteria approximations for $k$-medians and $k$-means
46: Do branch lengths help to locate a tree in a phylogenetic network?