StringologyTimes

Data Structures and Algorithms: 2021/11/22-28

1: On Fairness and Stability in Two-Sided Matchings
2: Multiscale entropic regularization for MTS on general metric spaces
3: Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
4: A Dynamic Programming Algorithm to Compute Joint Distribution of Order Statistics on Graphs
5: Theoretically and Practically Efficient Parallel Nucleus Decomposition
6: Private and polynomial time algorithms for learning Gaussians and beyond
7: On the Local Communication Complexity of Counting and Modular Arithmetic
8: On Fair Division with Binary Valuations Respecting Social Networks
9: Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets
10: Harmless Sets in Sparse Classes
11: Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
12: CQS: A Formally-Verified Framework for Fair and Abortable Synchronization
13: A note on Matching-Cut in $P_t$-free Graphs
14: A Review on Analysis and Visualization Methods for Biclustering
15: Scale-Invariant Strength Assortativity of Streaming Butterflies
16: dCSR: A Memory-Efficient Sparse Matrix Representation for Parallel Neural Network Inference
17: Matroid Partition Property and the Secretary Problem
18: Combinatorial Optimization Problems with Balanced Regret
19: Time and Memory Efficient Parallel Algorithm for Structural Graph Summaries and two Extensions to Incremental Summarization and $k$-Bisimulation for Long $k$-Chaining
20: A Classical Algorithm Which Also Beats $\frac{1}{2}+\frac{2}{\pi}\frac{1}{\sqrt{D}}$ For High Girth MAX-CUT
21: Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
22: Tiny Pointers
23: Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
24: The Implicit Graph Conjecture is False
25: Online Sampling and Decision Making with Low Entropy
26: Quantum Motif Clustering
27: Quasi-Isometric Graph Simplifications
28: New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $\sqrt{n}$ Barrier
29: Simple and Optimal Greedy Online Contention Resolution Schemes
30: How heavy independent sets help to find arborescences with many leaves in DAGs
31: Reconfiguration of Regular Induced Subgraphs
32: An Optimal Algorithm for Finding Champions in Tournament Graphs
33: A Unified Framework of Light Spanners II: Fine-Grained Optimality
34: A Note on Sanitizing Streams with Differential Privacy
35: Scheduling Appointments Online:\ The Power of Deferred Decision-Making
36: A polynomial kernel for vertex deletion into bipartite permutation graphs
37: Reconfiguration Problems on Submodular Functions
38: Distributionally robust possibilistic optimization problems
39: Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes