StringologyTimes

Data Structures and Algorithms: 2023/4/08-14

1: On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
2: Improving Identity-Robustness for Face Models
3: On Rotation Distance of Rank Bounded Trees
4: Prophet Inequalities: Separating Random Order from Order Selection
5: A simple and efficient preprocessing step for convex hull problem
6: On Extend-Only Directed Posets and Derived Byzantine-Tolerant Replicated Data Types (Extended Version)
7: Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension
8: Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size
9: Alon-Tarsi Number of Some Regular Graphs
10: Interior Point Methods with a Gradient Oracle
11: Ranking and Unranking k-subsequence universal words
12: Extension of Dictionary-Based Compression Algorithms for the Quantitative Visualization of Patterns from Log Files
13: (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
14: Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
15: Achieving Long-term Fairness in Submodular Maximization through Randomization
16: The Kraft–Barmpalias–Lewis-Pye lemma revisited
17: Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
18: An Associativity Threshold Phenomenon in Set-Associative Caches
19: Longest Common Subsequence with Gap Constraints
20: Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
21: Foundations for an Abstract Proof Theory in the Context of Horn Rules
22: When Should You Wait Before Updating? Toward a Robustness Refinement
23: A Hall-type theorem with algorithmic consequences in planar graphs
24: On Parallel k-Center Clustering
25: Node-Differentially Private Estimation of the Number of Connected Components
26: Locality via Global Ties: Stability of the 2-Core Against Misspecification
27: Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model
28: Load Balanced Demand Distribution under Overload Penalties
29: Beyond the Quadratic Time Barrier for Network Unreliability
30: List Update with Delays or Time Windows
31: Near-Optimal Degree Testing for Bayes Nets
32: Recognizing and generating unswitchable graphs
33: Solving Tensor Low Cycle Rank Approximation
34: Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints
35: Improved Approximations for Relative Survivable Network Design
36: On streaming approximation algorithms for constraint satisfaction problems
37: A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
38: Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
39: The Longest Subsequence-Repeated Subsequence Problem
40: Near Tight Shortest Paths in the Hybrid Model
41: Optimal Uncoordinated Unique IDs
42: Finding A Path Of Length k: An Expository