StringologyTimes

Data Structures and Algorithms: 2023/11/01-07

1: Tight bounds on adjacency labels for monotone graph classes
2: Dynamic Dictionary with Subconstant Wasted Bits per Key
3: Fast and Delay-Robust Multimodal Journey Planning
4: Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
5: Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment
6: Fully dynamic approximation schemes on planar and apex-minor-free graphs
7: Constrained Planarity in Practice – Engineering the Synchronized Planarity Algorithm
8: Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization
9: Local Max-Cut on Sparse Graphs
10: Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization
11: Accelerating Maximal Clique Enumeration via Graph Reduction
12: Adversarially Robust Distributed Count Tracking via Partial Differential Privacy
13: Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
14: Untangling Graphs on Surfaces
15: Maximum $k$- vs. $\ell$-colourings of graphs
16: Parameterized covering in semi-ladder-free hypergraphs
17: The Eclipse Layout Kernel
18: A new proof of Euclid’s algorithm
19: A Systematic Review of Approximability Results for Traveling Salesman Problems leveraging the TSP-T3CO Definition Scheme
20: Near-Optimal $k$-Clustering in the Sliding Window Model
21: Sorting with Predictions
22: Shortest paths on polymatroids and hypergraphic polytopes
23: Code Sparsification and its Applications
24: Finer-grained Reductions in Fine-grained Hardness of Approximation
25: A quantum-classical performance separation in nonconvex optimization
26: Sharp Noisy Binary Search with Monotonic Probabilities
27: $2$-Fault-Tolerant Strong Connectivity Oracles
28: Semidefinite programming and linear equations vs. homomorphism problems
29: Online Combinatorial Assignment in Independence Systems
30: A PTAS for $\ell_0$-Low Rank Approximation: Solving Dense CSPs over Reals
31: A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
32: On Conflict-Free Cuts: Algorithms and Complexity
33: Max $s,t$-Flow Oracles and Negative Cycle Detection in Planar Digraphs
34: A Survey on Coin Selection Algorithms in UTXO-based Blockchains
35: Dynamically Maintaining the Persistent Homology of Time Series
36: Constrained Submodular Maximization via New Bounds for DR-Submodular Functions
37: Simpler Distribution Testing with Little Memory
38: Instance-Specific Asymmetric Sensitivity in Differential Privacy
39: High-dimensional Linear Bandits with Knapsacks
40: Collective Tree Exploration via Potential Function Method
41: Fast Many-to-Many Routing for Dynamic Taxi Sharing with Meeting Points
42: Local Borsuk-Ulam, Stability, and Replicability
43: Generalizations of Matrix Multiplication can solve the Light Bulb Problem
44: Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
45: Parameterized algorithms for block-structured integer programs with large entries
46: GateLoop: Fully Data-Controlled Linear Recurrence for Sequence Modeling
47: A Lower Bound for the Max Entropy Algorithm for TSP
48: A First Order Method for Linear Programming Parameterized by Circuit Imbalance
49: Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products
50: Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
51: Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
52: Structural Properties of Search Trees with 2-way Comparisons
53: List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
54: Algorithms for Proportional Representation in Parliament in Divisor and Multiplicative Form
55: Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
56: Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(mn^{8/9})$ Time
57: Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection
58: Highly Connected Steiner Subgraph – Parameterized Algorithms and Applications to Hitting Set Problems
59: A stronger connection between the asymptotic rank conjecture and the set cover conjecture
60: Contour Algorithm for Connectivity
61: Cell-Probe Lower Bound for Accessible Interval Graphs
62: Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
63: Quantum speedups for linear programming via interior point methods
64: Dichotomies for Tree Minor Containment with Structural Parameters
65: Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
66: On Finding Optimal (Dynamic) Arborescences
67: Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
68: Exact Shortest Paths with Rational Weights on the Word RAM
69: Learning Hard-Constrained Models with One Sample
70: Sketching methods with small window guarantee using minimum decycling sets
71: Novel data structures for label based queries specifically efficient for billion+ property graph networks using Kinetica-Graph
72: Faster Algorithms for Cycle Hitting Problems on Disk Graphs
73: Dynamic Non-monotone Submodular Maximization
74: User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
75: On Matrices over a Polynomial Ring with Restricted Subdeterminants
76: Improved Deterministic Streaming Algorithms for Non-monotone Submodular Maximization
77: Structure of universal formulas
78: A quantum central path algorithm for linear optimization
79: On the density of primes of the form $X^2+c$