StringologyTimes

Data Structures and Algorithms: 2023/10/15-21

1: A Combinatorial Approximation Algorithm for Correlation Clustering
2: Tree Containment Above Minimum Degree is FPT
3: Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
4: Efficiently matching random inhomogeneous graphs via degree profiles
5: Content Moderation and the Formation of Online Communities: A Theoretical Framework
6: Statistical Barriers to Affine-equivariant Estimation
7: Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time
8: Fast and Simple Spectral Clustering in Theory and Practice
9: Separator Theorem and Algorithms for Planar Hyperbolic Graphs
10: Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
11: Faster Algorithms for Generalized Mean Densest Subgraph Problem
12: Online Algorithms with Uncertainty-Quantified Predictions
13: Simpler Reductions from Exact Triangle
14: Open Problems in (Hyper)Graph Decomposition
15: SQ Lower Bounds for Learning Mixtures of Linear Classifiers
16: Sampling Algorithms for Butterfly Counting on Temporal Bipartite Graphs
17: Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem
18: The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
19: Guaranteed, Predictable, Polynomial AGV Time-Pathing
20: Simpler and Higher Lower Bounds for Shortcut Sets
21: Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
22: On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
23: Towards Simpler Sorting Networks and Monotone Circuits for Majority
24: Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
25: An $O(\log n)$-Competitive Posted-Price Algorithm for Online Matching on the Line
26: Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm
27: An Enumerative Perspective on Connectivity
28: Tight approximability of MAX 2-SAT and relatives, under UGC
29: Deterministic 3SUM-Hardness
30: Edge-disjoint paths in expanders: online with removals
31: Mean Estimation Under Heterogeneous Privacy Demands
32: Faster Algorithms for Text-to-Pattern Hamming Distances
33: One-Phase Batch Update on Sparse Merkle Trees for Rollups
34: An Analysis of $D^\alpha$ seeding for $k$-means
35: A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
36: Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
37: Fast Approximation of Similarity Graphs with Kernel Density Estimation