StringologyTimes

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

1: First-Order Model Checking on Structurally Sparse Graph Classes
2: Tight algorithms for connectivity problems parameterized by clique-width
3: Planted Bipartite Graph Detection
4: Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
5: Men Can’t Always be Transformed into Mice: Decision Algorithms and Complexity for Sorting by Symmetric Reversals
6: Approximately Optimal Core Shapes for Tensor Decompositions
7: Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees
8: Adaptive Massively Parallel Connectivity in Optimal Space
9: Weighted Edit Distance Computation: Strings, Trees and Dyck
10: Parallel Derandomization for Coloring
11: SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements
12: Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy
13: Locally consistent decomposition of strings with applications to edit distance sketching
14: Dual Algorithmic Reasoning
15: A Reduction from Chores Allocation to Job Scheduling
16: A new width parameter of graphs based on edge cuts: $\alpha$-edge-crossing width
17: An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs
18: $t$-sails and sparse hereditary classes of unbounded tree-width
19: Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal
20: Dynamic $(1+\epsilon)$-Approximate Matching Size in Truly Sublinear Update Time
21: Count-min sketch with variable number of hash functions: an experimental study
22: Online Algorithms with Randomly Infused Advice
23: Characterization of Simplicial Complexes by Counting Simplets Beyond Four Nodes
24: Synchrony/Asynchrony vs. Stationary/Mobile? The Latter is Superior…in Theory
25: A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-connected Induced Subgraphs
26: Algorithmically Effective Differentially Private Synthetic Data
27: Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
28: An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
29: Maintaining Discrete Probability Distributions in Practice
30: On Differential Privacy and Adaptive Data Analysis with Bounded Space
31: Fully Dynamic Exact Edge Connectivity in Sublinear Time
32: Computing Truncated Metric Dimension of Trees
33: Infinite Lewis Weights in Spectral Graph Theory
34: Computation with Large Advice
35: Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
36: Maximum Coverage in Sublinear Space, Faster
37: Sparse Dimensionality Reduction Revisited
38: On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)
39: Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
40: FREIGHT: Fast Streaming Hypergraph Partitioning
41: Computing finite index congruences of finitely presented semigroups and monoids
42: Engineering a Preprocessor for Symmetry Detection
43: Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
44: Efficient $1$-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences
45: Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
46: Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation
47: Detection-Recovery Gap for Planted Dense Cycles
48: Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes
49: Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
50: Scheduling Coflows for Minimizing the Makespan in Identical Parallel Networks
51: Distributed Symmetry Breaking on Power Graphs via Sparsification
52: Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
53: Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
54: Advances on Strictly $\Delta$-Modular IPs