StringologyTimes

Data Structures and Algorithms: 2021/2/15-21

1: Byzantine Dispersion on Graphs
2: Testing properties of signed graphs
3: Fair and Optimal Cohort Selection for Linear Utilities
4: Polynomial time algorithms in invariant theory for torus actions
5: Dynamic Membership for Regular Languages
6: Local Access to Random Walks
7: On Interim Envy-Free Allocation Lotteries
8: Empirical Characterization of Graph Sampling Algorithms
9: Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs
10: About Weighted Random Sampling in Preferential Attachment Models
11: On Greedily Packing Anchored Rectangles
12: Online matching in lossless expanders
13: Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
14: Faster Kernel Matrix Algebra via Density Estimation
15: On the sampling Lov'asz Local Lemma for atomic constraint satisfaction problems
16: Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
17: Smoothed Analysis with Adaptive Adversaries
18: Lexicographically Fair Learning: Algorithms and Generalization
19: Maximum Coverage in the Data Stream Model: Parameterized and Generalized
20: Efficient Maintenance of Distance Labelling for Incremental Updates in Large Dynamic Graphs
21: Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time
22: Leveraging Public Data for Practical Private Query Release
23: Linear Time Runs over General Ordered Alphabets
24: Local Mending
25: Deterministic Algorithms for Compiling Quantum Circuits with Recurrent Patterns
26: Fast Graphical Population Protocols
27: Differentially Private Correlation Clustering
28: The Complexity of Gerrymandering Over Graphs: Paths and Trees
29: Impartial selection with prior information
30: Consistent Lock-free Parallel Stochastic Gradient Descent for Fast and Stable Convergence
31: Online $k$-means Clustering on Arbitrary Data Streams
32: Efficient Online ML API Selection for Multi-Label Classification Tasks
33: Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms
34: Buffered Streaming Graph Partitioning
35: Temporal Locality in Online Algorithms
36: A Stronger Impossibility for Fully Online Matching
37: Range Minimum Queries in Minimal Space
38: How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
39: Combinatorial optimization and reasoning with graph neural networks
40: Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
41: Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
42: Hardness of Metric Dimension in Graphs of Constant Treewidth
43: Training Neural Networks is $\exists\mathbb R$-complete
44: Strong-Diameter Network Decomposition
45: Gerrymandering on graphs: Computational complexity and parameterized algorithms
46: Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
47: Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
48: Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning
49: Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
50: Quantifying Variational Approximation for the Log-Partition Function
51: ALTO: Adaptive Linearized Storage of Sparse Tensors
52: Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
53: Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle