StringologyTimes

Data Structures and Algorithms: 2023/5/08-14

1: A New Upper Bound on the Maximal Error Resilience of Interactive Error-Correcting Codes
2: Oblivious algorithms for the Max-$k$AND Problem
3: New metrics and search algorithms for weighted causal DAGs
4: Online Task Assignment with Controllable Processing Time
5: Block Crossings in One-Sided Tanglegrams
6: CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers
7: Autumn: A Scalable Read Optimized LSM-tree based Key-Value Stores with Fast Point and Range Read Speed
8: Memory-Efficient Solutions to Large-Graph MST Problems
9: Sorting Finite Automata via Partition Refinement
10: Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
11: A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
12: 4/3-Approximation of Graphic TSP
13: Fast Many-to-Many Routing for Ridesharing with Multiple Pickup and Dropoff Locations
14: Testing versus estimation of graph properties, revisited
15: Parallel External Sorting of ASCII Records Using Learned Models
16: Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem
17: On the Number of $t$-Lee-Error-Correcting Codes
18: Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
19: Constant Approximation for Network Revenue Management with Markovian-Correlated Customer Arrivals
20: Acceleration of FM-index Queries Through Prefix-free Parsing
21: Novel Quantum Information Processing Methods and Investigation
22: Coding for IBLTs with Listing Guarantees
23: Improving the performance of classical linear algebra iterative methods via hybrid parallelism
24: Pebble guided Treasure Hunt in Plane
25: Average Awake Complexity of MIS and Matching
26: Optimal mixing of the down-up walk on independent sets of a given size
27: A Near-Optimal Deterministic Distributed Synchronizer
28: Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser
29: Optimal Algorithms for Bounded Weighted Edit Distance
30: Characterizing the impact of last-level cache replacement policies on big-data workloads
31: Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
32: Fair Price Discrimination
33: Streaming Edge Coloring with Subquadratic Palette Size
34: Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
35: Learning-Augmented Online Packet Scheduling with Deadlines
36: A Wait-free Queue with Polylogarithmic Step Complexity
37: Minimum Consistent Subset for Trees Revisited
38: Reconfiguration of Time-Respecting Arborescences
39: Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
40: Matching Statistics speed up BWT construction
41: On the Fair Comparison of Optimization Algorithms in Different Machines
42: Reduced Label Complexity For Tight $\ell_2$ Regression
43: Temporal Network Creation Games
44: Isotropic Point Cloud Meshing using unit Spheres (IPCMS)
45: Linearizability Analysis of the Contention-Friendly Binary Search Tree
46: The $2$-$3$-Set Packing problem and a $\frac{4}{3}$-approximation for the Maximum Leaf Spanning Arborescence problem in rooted dags
47: Randomized Algorithm for the Maximum-Profit Routing Problem
48: Dynamic Convex Hulls under Window-Sliding Updates