StringologyTimes

Data Structures and Algorithms: 2022/11/22-28

1: Lattice Problems Beyond Polynomial Time
2: Private Counting of Distinct and k-Occurring Items in Time Windows
3: The Berlekamp-Massey Algorithm revisited
4: A Cut-Matching Game for Constant-Hop Expanders
5: Algorithmic Applications of Hypergraph and Partition Containers
6: Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings
7: String Covering: A Survey
8: Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
9: Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality
10: On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
11: Online facility location with weights and congestion
12: Support Size Estimation: The Power of Conditioning
13: Generalized Private Selection and Testing with High Confidence
14: Efficient Sampling Algorithms for Approximate Motif Counting in Temporal Graph Streams
15: Minimum-Cost Temporal Walks under Waiting-Time Constraints in Linear Time
16: Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
17: Reversible Programming: A Case Study of Two String-Matching Algorithms
18: On Structural Parameterizations of Star Coloring
19: Scalable and Effective Conductance-based Graph Clustering
20: Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
21: The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
22: Finding Almost Tight Witness Trees
23: Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
24: An Algorithmic Bridge Between Hamming and Levenshtein Distances
25: SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search
26: Worst-Case to Expander-Case Reductions
27: Complexity Framework For Forbidden Subgraphs I: The Framework
28: The NISQ Complexity of Collision Finding
29: Space-efficient RLZ-to-LZ77 conversion
30: Learning and Testing Latent-Tree Ising Models Efficiently
31: A fast and simple $O (z \log n)$-space index for finding approximately longest common substrings
32: Differentially Private Heatmaps
33: Estimation of Similarity between DNA Sequences and Its Graphical Representation
34: Towards Better Bounds for Finding Quasi-Identifiers
35: Synthesis Cost-Optimal Targeted Mutant Protein Libraries
36: Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem
37: Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
38: A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions
39: Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
40: Better Trees for Santa Claus
41: Faster Algorithm for Structured John Ellipsoid Computation
42: Equity Promotion in Public Transportation
43: Identifying a 3-vertex strongly biconnected directed subgraph with minimum number of edges
44: Hardness Results for Minimizing the Covariance of Randomly Signed Sum of Vectors
45: Lower Bounds on Retroactive Data Structures
46: Dynamic Kernel Sparsifiers
47: Which $L_p$ norm is the fairest? Approximations for fair facility location across all “$p$”
48: LoNe Sampler: Graph node embeddings by coordinated local neighborhood sampling
49: A Faster $k$-means++ Algorithm
50: Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information