StringologyTimes

Data Structures and Algorithms: 2022/7/01-07

1: Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
2: Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities
3: Online TSP with Predictions
4: Verification and search algorithms for causal DAGs
5: Multivariate trace estimation in constant quantum depth
6: Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
7: Combining Predicted and Live Traffic with Time-Dependent A(star) Potentials
8: Search-Space Reduction via Essential Vertices
9: An Enumeration Algorithm for Binary Coprime Polynomials with Nonzero Constant Term
10: Packing cycles in planar and bounded-genus graphs
11: Proteus: A Self-Designing Range Filter
12: The Structure of Hypergraphs Arising in Cellular Mobile Communication Systems
13: Exponential Convergence of Sinkhorn Under Regularization Scheduling
14: Efficient and Effective Local Search for the Set-Union Knapsack Problem and Budgeted Maximum Coverage Problem
15: Sum-of-Max Partition under a Knapsack Constraint
16: Tableless Calculation of Circular Functions on Dyadic Rationals
17: Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
18: Decremental Matching in General Graphs
19: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
20: An Empirical Evaluation of $k$-Means Coresets
21: Suffix sorting via matching statistics
22: Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
23: On Streaming Algorithms for Geometric Independent Set and Clique
24: On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
25: Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel
26: Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
27: An Improved Algorithm for Finding the Shortest Synchronizing Words
28: On implementing SWMR registers from SWSR registers in systems with Byzantine failures
29: Correlated Stochastic Knapsack with a Submodular Objective
30: An almost linear time complexity algorithm for the Tool Loading Problem
31: Online 2-stage Stable Matching
32: Width Helps and Hinders Splitting Flows
33: Finding a Hidden Edge
34: Improving Order with Queues
35: Computing NP-hard Repetitiveness Measures via MAX-SAT
36: Learning Hierarchical Structure of Clusterable Graphs
37: Techniques for Generalized Colorful $k$-Center Problems
38: Reforming an Envy-Free Matching
39: Distributed domination on sparse graph classes
40: Private Matrix Approximation and Geometry of Unitary Orbits
41: Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
42: Comments on “Testing Conditional Independence of Discrete Distributions”
43: Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
44: From algorithms to connectivity and back: finding a giant component in random k-SAT
45: Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for all Orthogonal Convex Shapes
46: Fast Discrepancy Minimization with Hereditary Guarantees
47: On Geometric Shape Construction via Growth Operations
48: Barriers for Faster Dimensionality Reduction