StringologyTimes

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

1: Fine-grained reductions from approximate counting to decision
2: Lower Bounds for Electrical Reduction on Surfaces
3: Clustering Algorithms for the Centralized and Local Models
4: On Approximating the Number of $k$-cliques in Sublinear Time
5: Testing bounded arboricity
6: Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path
7: Coding sets with asymmetric information
8: Polylogarithmic Approximation Algorithms for Weighted-$\mathcal{F}$-Deletion Problems
9: Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
10: Projected Power Iteration for Network Alignment
11: Automatic Backward Differentiation for American Monte-Carlo Algorithms (Conditional Expectation)
12: Practical Locally Private Heavy Hitters
13: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
14: Geometric Rescaling Algorithms for Submodular Function Minimization
15: Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
16: Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees
17: Tight Analysis of Randomized Greedy MIS
18: Differentially Private Testing of Identity and Closeness of Discrete Distributions
19: A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
20: Capacitated Covering Problems in Geometric Spaces
21: Weak Modular Product of Bipartite Graphs, Bicliques and Isomorphism
22: Coloring Down: $3/2$-approximation for special cases of the weighted tree augmentation problem
23: Shorter tours and longer detours: Uniform covers and a bit beyond
24: On Treewidth and Stable Marriage
25: Polynomial-time algorithm for Maximum Weight Independent Set on $P_6$-free graphs
26: Differentially Private Identity and Closeness Testing of Discrete Distributions
27: Nested Convex Bodies are Chaseable
28: The Compressed Overlap Index
29: Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs
30: Learning Powers of Poisson Binomial Distributions
31: Reconciling Graphs and Sets of Sets
32: First-Order Query Evaluation with Cardinality Conditions
33: Computing Tutte Paths
34: Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
35: Online Bipartite Matching with Amortized $O(\log^2 n)$ Replacements
36: On Finding Maximum Cardinality Subset of Vectors with a Constraint on Normalized Squared Length of Vectors Sum
37: Boolean dimension and tree-width
38: A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
39: Submodular Minimization Under Congruency Constraints
40: Dynamic Bridge-Finding in $\tilde{O}(\log ^2 n)$ Amortized Time
41: Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
42: An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
43: Document Listing on Repetitive Collections with Guaranteed Performance
44: Deterministic Dispersion of Mobile Robots in Dynamic Rings
45: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
46: The Euler and Chinese Postman Problems on 2-Arc-Colored Digraphs
47: Congestion Barcodes: Exploring the Topology of Urban Congestion Using Persistent Homology
48: Improved bounds for testing Dyck languages
49: Two Results on Slime Mold Computations
50: Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner
51: Constant Time Updates in Hierarchical Heavy Hitters
52: Improved Kernels and Algorithms for Claw and Diamond Free Edge Deletion Based on Refined Observations
53: The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
54: Scalable and robust set similarity join
55: Hierarchical Partial Planarity
56: Load Thresholds for Cuckoo Hashing with Overlapping Blocks
57: Fast Nearest Neighbor Preserving Embeddings