StringologyTimes

Data Structures and Algorithms: 2023/2/22-28

1: Repeated Bilateral Trade Against a Smoothed Adversary
2: ITERATED INSIDE OUT: a new exact algorithm for the transportation problem
3: Robust Mean Estimation Without Moments for Symmetric Distributions
4: The Target-Charging Technique for Privacy Accounting across Interactive Computations
5: Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
6: Differentially Private $L_2$-Heavy Hitters in the Sliding Window Model
7: Improved Coresets for Clustering with Capacity and Fairness Constraints
8: The Complexity of Debt Swapping
9: Approximation Ineffectiveness of a Tour-Untangling Heuristic
10: Fair Correlation Clustering in Forests
11: Approximability of the Four-Vertex Model
12: The Power of Uniform Sampling for $k$-Median
13: Differentially Private Data Structures under Continual Observation for Histograms and Related Queries
14: Easy testability for posets
15: Engineering a Distributed-Memory Triangle Counting Algorithm
16: Degrees and Network Design: New Problems and Approximations
17: Pattern detection in ordered graphs
18: Finding a Small Vertex Cut on Distributed Networks
19: Storage in Computational Geometry
20: Learning to Manipulate a Commitment Optimizer
21: Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier
22: On price-induced minmax matchings
23: Simultaneous Drawing of Layered Trees
24: Efficiently handling constraints with Metropolis-adjusted Langevin algorithm
25: Online Minimum Spanning Trees with Weight Predictions
26: A simple division-free algorithm for computing Pfaffians
27: Warehouse Problem with Bounds, Fixed Costs and Complementarity Constraints
28: Dynamic Averaging Load Balancing on Arbitrary Graphs
29: Using Colors and Sketches to Count Subgraphs in a Streaming Graph
30: Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
31: Optimal Bounds for Noisy Sorting
32: The number of descendants in a random directed acyclic graph
33: $k$-Center Clustering with Outliers in the MPC and Streaming Model
34: Generative Models of Huge Objects
35: Limited Query Graph Connectivity Test
36: On the Cost of Demographic Parity in Influence Maximization
37: Improving Fairness in Information Exposure by Adding Links
38: Toward Self-Adjusting k-ary Search Tree Networks
39: The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests
40: Fast Attention Requires Bounded Entries
41: MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results
42: Large-Block Modular Addition Checksum Algorithms
43: Random-Order Enumeration for Self-Reducible NP-Problems
44: Dispatching Point Selection for a Drone-Based Delivery System Operating in a Mixed Euclidean-Manhattan Grid
45: Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
46: Contracting edges to destroy a pattern: A complexity study
47: 3-Coloring in Time O(1.3217^n)
48: Online Interval Scheduling with Predictions
49: On Coresets for Clustering in Small Dimensional Euclidean Spaces
50: A Formal Analysis of RANKING
51: An algorithm for geo-distributed and redundant storage in Garage
52: Polynomial-delay generation of functional digraphs up to isomorphism
53: Host Community Respecting Refugee Housing
54: Query-optimal estimation of unitary channels in diamond distance
55: On Differentially Private Online Predictions
56: Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
57: Signal Propagation in Double Edged Relays
58: A CS guide to the quantum singular value transformation
59: Practical Algorithms for Orientations of Partially Directed Graphical Models
60: Publicly verifiable delegative democracy with secret voting power