StringologyTimes

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

1: Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs
2: Improved Algorithms for Population Recovery from the Deletion Channel
3: Differentially Private Assouad, Fano, and Le Cam
4: Learning sums of powers of low-degree polynomials in the non-degenerate case
5: Complete Edge-Colored Permutation Graphs
6: An algorithmic framework for colouring locally sparse graphs
7: Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
8: Slightly Improved Upper Bound on the Integrality Ratio for the $s-t$ Path TSP
9: Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
10: Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations
11: The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
12: Online Multiserver Convex Chasing and Optimization
13: On the computability of continuous maximum entropy distributions with applications
14: Fast exact computation of the $k$ most abundant isotope peaks with layer-ordered heaps
15: Resolving the Optimal Metric Distortion Conjecture
16: Faster Dynamic Matrix Inverse for Faster LPs
17: Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
18: Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
19: Approximating Independent Set and Dominating Set on VPG graphs
20: Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication
21: A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
22: Four Pages Are Indeed Necessary for Planar Graphs
23: Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
24: Algorithmic Foundations for the Diffraction Limit
25: Isomorphism Testing for Graphs Excluding Small Minors
26: Polynomial-delay Enumeration Algorithms in Set Systems
27: Novel Binary-Addition Tree Algorithm (BAT) for Binary-State Network Reliability Problem
28: On the computation of the M{"o}bius transform
29: Coresets for Clustering in Excluded-minor Graphs and Beyond
30: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
31: Entanglement is Necessary for Optimal Quantum Property Testing
32: Maximizing Determinants under Matroid Constraints
33: Beyond Tree Embeddings – a Deterministic Framework for Network Design with Deadlines or Delay
34: Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
35: Contention Resolution Without Collision Detection
36: A Survey of Approximate Quantile Computation on Large-scale Data (Technical Report)
37: Hitting forbidden induced subgraphs on bounded treewidth graphs
38: The two player shortest path network interdiction problem
39: Faster Approximate Pattern Matching: A Unified Approach
40: Low-stretch spanning trees of graphs with bounded width
41: Enumerating Chemical Graphs with Two Disjoint Cycles Satisfying Given Path Frequency Specifications
42: Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
43: Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
44: Counterexamples to the Low-Degree Conjecture
45: UDDSketch: Accurate Tracking of Quantiles in Data Streams
46: An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
47: Mapping Matchings to Minimum Vertex Covers: K\H{o}nig’s Theorem Revisited
48: The $(2,k)$-connectivity augmentation problem: Algorithmic aspects
49: Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
50: Stochastic Weighted Matching: $(1-\epsilon)$ Approximation
51: Faster Dynamic Range Mode
52: Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies
53: Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
54: Quantum algorithms for computational geometry problems
55: An Algorithm for the Exact Treedepth Problem
56: Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions
57: Black-White Array: A New Data Structure for Dynamic Data Sets
58: Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
59: Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
60: Dynamic Matching Algorithms in Practice
61: Distributed Weighted Min-Cut in Nearly-Optimal Time
62: Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas
63: A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions
64: Finding large $H$-colorable subgraphs in hereditary graph classes
65: Collaborative Top Distribution Identifications with Limited Interaction
66: Mechanism Design for Online Resource Allocation: A Unified Approach
67: Scheduling with Communication Delays via LP Hierarchies and Clustering
68: An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
69: Enumerating Maximal Induced Subgraphs
70: On the Parameterised Complexity of Induced Multipartite Graph Parameters
71: Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition