StringologyTimes

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

1: Characterization of random walks on space of unordered trees using efficient metric simulation
2: Hierarchical Lowrank Arithmetic with Binary Compression
3: Finding Small Complete Subgraphs Efficiently
4: Minwise-Independent Permutations with Insertion and Deletion of Features
5: Simple and Faster Algorithms for Knapsack
6: Parameterized Complexity of Simultaneous Planarity
7: Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
8: Sequencing Stochastic Jobs with a Single Sample
9: Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
10: Dynamic Compact Data Structure for Temporal Reachability with Unsorted Contact Insertions
11: Linear Programming based Reductions for Multiple Visit TSP and Vehicle Routing Problems
12: Quantum Circuits for Fixed Substring Matching Problems
13: Adaptive Encoding Strategies for Erasing-Based Lossless Floating-Point Compression
14: Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
15: Recent Developments in Pandora’s Box Problem: Variants and Applications
16: Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
17: No Polynomial Kernels for Knapsack
18: An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
19: Sink Location Problems in Dynamic Flow Grid Networks
20: Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions
21: Counting Distinct Elements Under Person-Level Differential Privacy
22: Are there graphs whose shortest path structure requires large edge weights?
23: Approximation Algorithms to Enhance Social Sharing of Fresh Point-of-Interest Information
24: Optimizing Hierarchical Queries for the Attribution Reporting API
25: SAGE: A Storage-Based Approach for Scalable and Efficient Sparse Generalized Matrix-Matrix Multiplication
26: ChainedFilter: Combining Membership Filters by Chain Rule
27: On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity
28: Multipartite Entanglement Distribution in Quantum Networks using Subgraph Complementations
29: Dynamic Pricing for Reusable Resources: The Power of Two Prices
30: SoK: Authenticated Prefix Relations – A Unified Perspective On Relative Time-Stamping and Append-Only Logs
31: Spanning Adjacency Oracles in Sublinear Time
32: Testing Junta Truncation
33: An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
34: The APX-hardness of the Traveling Tournament Problem
35: Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
36: Locally Uniform Hashing
37: Sampling unknown large networks restricted by low sampling rates
38: Mutual visibility in hypercube-like graphs
39: Efficient Batch Dynamic Graphlet Counting