StringologyTimes

Data Structures and Algorithms: 2018/11/01-07

1: A Two Query Adaptive Bitprobe Scheme Storing Five Elements
2: Stochastic Submodular Cover with Limited Adaptivity
3: Testing Halfspaces over Rotation-Invariant Distributions
4: Recovery Guarantees for Quadratic Tensors with Sparse Observations
5: Tropical Modeling of Weighted Transducer Algorithms on Graphs
6: An $O(n \log n)$ time Algorithm for computing the Path-length Distance between Trees
7: On subexponential running times for approximating directed Steiner tree and related problems
8: Drawing Clustered Graphs on Disk Arrangements
9: Planar Graphs of Bounded Degree have Constant Queue Number
10: Worst-Case Efficient Sorting with QuickMergesort
11: Competitively Chasing Convex Bodies
12: Spectral Methods from Tensor Networks
13: Near-Linear Time Algorithm for n-fold ILPs via Color Coding
14: Local search breaks 1.75 for Graph Balancing
15: Chasing Nested Convex Bodies Nearly Optimally
16: Dynamic Pricing (and Assortment) under a Static Calendar
17: Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
18: Efficient Projection onto the Perfect Phylogeny Model
19: Improved approximation algorithms for path vertex covers in regular graphs
20: Smoothed Analysis of the Art Gallery Problem
21: Optimal Rank and Select Queries on Dictionary-Compressed Text
22: Learning sparse mixtures of rankings from noisy information
23: Multidimensional segment trees can do range updates in poly-logarithmic time
24: Compressed Multiple Pattern Matching
25: QuickXsort - A Fast Sorting Scheme in Theory and Practice
26: Tight complexity lower bounds for integer linear programming with few constraints
27: Lower Bounds for External Memory Integer Sorting via Network Coding
28: Towards a Zero-One Law for Column Subset Selection
29: RePair in Compressed Space and Time
30: How to aggregate Top-lists: Approximation algorithms via scores and average ranks
31: Almost Optimal Distance Oracles for Planar Graphs
32: On a generalization of iterated and randomized rounding
33: Exact multiplicative updates for convolutional $\beta$-NMF in 2D
34: The distributed complexity of locally checkable problems on paths is decidable
35: Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
36: Learning Two Layer Rectified Neural Networks in Polynomial Time
37: Lower Bounds for Parallel and Randomized Convex Optimization
38: The Sparsest Additive Spanner via Multiple Weighted BFS Trees
39: Towards a Unified Theory of Sparsification for Matching Problems
40: Ordered Graph Limits and Their Applications
41: An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning
42: Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
43: Motif and Hypergraph Correlation Clustering
44: The entropy of lies: playing twenty questions with a liar
45: Characterizations and Directed Path-Width of Sequence Digraphs
46: An estimation of the greedy algorithm’s accuracy for a set cover problem instance
47: Tunneling on Wheeler Graphs
48: Interactive coding resilient to an unknown number of erasures
49: Weighted Upper Edge Cover: Complexity and Approximability
50: Oblivious Set-maxima for Intersection of Convex Polygons
51: Flow-Cut Gaps and Face Covers in Planar Graphs
52: Static Data Structure Lower Bounds Imply Rigidity
53: Weighted Matchings via Unweighted Augmentations
54: A new exact approach for the Bilevel Knapsack with Interdiction Constraints