StringologyTimes

Data Structures and Algorithms: 2022/8/15-21

1: Optimistic No-regret Algorithms for Discrete Caching
2: Towards Parallel Learned Sorting
3: On the Complexity of Distance-$d$ Independent Set Reconfiguration
4: Fair Assortment Planning
5: Private Query Release via the Johnson-Lindenstrauss Transform
6: Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
7: Mean estimation when you have the source code; or, quantum Monte Carlo methods
8: Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
9: Deletion Robust Non-Monotone Submodular Maximization over Matroids
10: Simple deterministic O(n log n) algorithm finding a solution of Erd\H{o}s-Ginzburg-Ziv theorem
11: Polynomial kernel for immersion hitting in tournaments
12: New Parallel Order Maintenance Data Structure
13: Optimal algorithms for learning quantum phase states
14: Fast Distributed Vertex Splitting with Applications
15: Minimum Cost Adaptive Submodular Cover
16: Simplicity in Eulerian Circuits: Uniqueness and Safety
17: Embeddable of one-vertex graph with rotations into torus
18: Improved Distributed Algorithms for the Lov'asz Local Lemma and Edge Coloring
19: Customizable Hub Labeling: Properties and Algorithms
20: Locally Restricted Proof Labeling Schemes (Full Version)
21: Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
22: Algorithm to derive shortest edit script using Levenshtein distance algorithm
23: Approximate Circular Pattern Matching
24: On the parameterized complexity of symmetric directed multicut
25: A Verified Implementation of B+-Trees in Isabelle/HOL
26: Secretary Problems: The Power of a Single Sample
27: Revisiting Maximum Satisfiability and Related Problems in Data Streams
28: Computing a Feedback Arc Set Using PageRank
29: A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems
30: Quancurrent: A Concurrent Quantiles Sketch
31: A Ptolemaic Partitioning Mechanism
32: Merging Sorted Lists of Similar Strings
33: A Simple Differentially Private Algorithm for Global Minimum Cut
34: An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
35: Learning in Stackelberg Games with Non-myopic Agents
36: Line Coverage with Multiple Robots: Algorithms and Experiments
37: Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006
38: Exponential Speedup Over Locality in MPC with Optimal Memory
39: Near-optimal fitting of ellipsoids to random points
40: Packet Forwarding with a Locally Bursty Adversary
41: On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
42: An $O(k\log n)$ Time Fourier Set Query Algorithm
43: The computational complexity of some explainable clustering problems
44: Solving systems of linear equations through zero forcing set and application to lights out
45: Parallel Longest Increasing Subsequence and van Emde Boas Trees
46: Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform
47: A Polynomial Decision for 3-SAT