StringologyTimes

Data Structures and Algorithms: 2019/7/08-14

1: Fair Byzantine Agreements for Blockchains
2: Inapproximability Results for Scheduling with Interval and Resource Restrictions
3: More Hierarchy in Route Planning Using Edge Hierarchies
4: Contraction Clustering (RASTER): A Very Fast Big Data Algorithm for Sequential and Parallel Density-Based Clustering in Linear Time, Constant Memory, and a Single Pass
5: A spectral bound on hypergraph discrepancy
6: Faster Deterministic Distributed Coloring Through Recursive List Coloring
7: Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
8: The Densest k Subgraph Problem in b-Outerplanar Graphs
9: Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
10: Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience
11: Trustworthy Graph Algorithms
12: Stochastic Monotone Submodular Maximization with Queries
13: PTAS and Exact Algorithms for $r$-Gathering Problems on Tree
14: $r$-Gather Clustering and $r$-Gathering on Spider: FPT Algorithms and Hardness
15: Linear MIM-Width of Trees
16: Reconstruction under outliers for Fourier-sparse functions
17: Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice — Continuous Greedy Algorithm on Median Complex —
18: Better Sample – Random Subset Sum in $2^{0.255n}$ and its Impact on Decoding Random Linear Codes
19: Nearly optimal edge estimation with independent set queries
20: The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
21: Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension
22: New Competitiveness Bounds for the Shared Memory Switch
23: $L_p$ Pattern Matching in a Stream
24: Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in $\ell_p$ norm
25: On Approximating Partial Set Cover and Generalizations
26: Hitting minors on bounded treewidth graphs. IV. An optimal algorithm
27: Speed Scaling with Tandem Servers
28: Computing Valuations of the Dieudonn'e Determinants
29: Progressive Wasserstein Barycenters of Persistence Diagrams
30: Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
31: Polytopes, lattices, and spherical codes for the nearest neighbor problem
32: Evolutionary techniques in lattice sieving algorithms
33: Approximate Voronoi cells for lattices, revisited
34: Smoothed Analysis of Order Types
35: String Attractors and Combinatorics on Words
36: Coresets for Clustering in Graphs of Bounded Treewidth
37: Matroid Bases with Cardinality Constraints on the Intersection
38: Constant-Time Dynamic $(\Delta+1)$-Coloring and Weight Approximation for Minimum Spanning Forest: Dynamic Algorithms Meet Property Testing
39: Dense Peelable Random Uniform Hypergraphs
40: Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications
41: Sparse Regular Expression Matching
42: Scheduling With Inexact Job Sizes: The Merits of Shortest Processing Time First
43: Approximately counting and sampling small witnesses using a colourful decision oracle
44: Minimum k-critical bipartite graphs
45: A Resource-Aware Approach to Collaborative Loop Closure Detection with Provable Performance Guarantees
46: ADDMC: Weighted Model Counting with Algebraic Decision Diagrams
47: Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
48: Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
49: Analysis of Ward’s Method
50: Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
51: Towards a Better Understanding of Randomized Greedy Matching
52: State-of-The-Art Sparse Direct Solvers
53: Competitive Analysis with a Sample and the Secretary Problem
54: Quantum and Classical Algorithms for Approximate Submodular Function Minimization
55: Walking Randomly, Massively, and Efficiently
56: Computational Concentration of Measure: Optimal Bounds, Reductions, and More
57: Eccentricity function in distance-hereditary graphs
58: Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension
59: Non-uniform Geometric Set Cover and Scheduling on Multiple Machines
60: A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization
61: Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
62: Towards Optimal Moment Estimation in Streaming and Distributed Models
63: On a Generalization of the Marriage Problem
64: Finding irrelevant vertices in linear time on bounded-genus graphs
65: Online learning for min-max discrete problems
66: Efficient average-case population recovery in the presence of insertions and deletions
67: The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
68: Perfect sampling from spatial mixing
69: Zeros of ferromagnetic 2-spin systems
70: On Happy Colorings, Cuts, and Structural Parameterizations
71: The FAST Algorithm for Submodular Maximization