StringologyTimes

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

1: Parallel Algorithms for Hierarchical Nucleus Decomposition
2: Simple Opinion Dynamics for No-Regret Learning
3: PLAN: Variance-Aware Private Mean Estimation
4: Deterministic and Work-Efficient Parallel Batch-Dynamic Trees in Low Span
5: Algorithmic Cluster Expansions for Quantum Problems
6: Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
7: On the $k$-Hamming and $k$-Edit Distances
8: Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
9: Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
10: A Smooth Binary Mechanism for Efficient Private Continual Observation
11: MementoHash: A Stateful, Minimal Memory, Best Performing Consistent Hash Algorithm
12: Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
13: An Efficient Algorithm for Power Dominating Set
14: Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
15: Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes
16: Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs
17: Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
18: Adversaries with Limited Information in the Friedkin–Johnsen Model
19: Algorithms for Multiple Drone-Delivery Scheduling Problem (MDSP)
20: On the Complexity of Co-secure Dominating Set Problem
21: Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation
22: Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems
23: A Smoothed FPTAS for Equilibria in Congestion Games
24: Agnostically Learning Single-Index Models using Omnipredictors
25: On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing
26: Efficient Parameterized Pattern Matching in Sublinear Space
27: A bounded partition approach to identifying one fake coin and its type
28: Scheduling with cardinality dependent unavailability periods
29: Minimax optimal testing by classification
30: Correcting Underrepresentation and Intersectional Bias for Classification
31: Quasipolynomiality of the Smallest Missing Induced Subgraph
32: Cuckoo Hashing in Cryptography: Optimal Parameters, Robustness and Applications
33: Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $\Omega(\log n)$ Lightness Barrier
34: Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections
35: Data Structures for Density Estimation
36: Composition of nested embeddings with an application to outlier removal
37: Fast quantum algorithm for differential equations
38: Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
39: A Parameterized Algorithm for Flat Folding
40: On the Optimal Bounds for Noisy Computing
41: Sampling Individually-Fair Rankings that are Always Group Fair
42: Block-Wise Index Modulation and Receiver Design for High-Mobility OTFS Communications
43: Optimal (degree+1)-Coloring in Congested Clique
44: Online Resource Allocation with Convex-set Machine-Learned Advice