StringologyTimes

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

1: Efficient Correlation Clustering Methods for Large Consensus Clustering Instances
2: Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms
3: A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
4: Properly Learning Decision Trees with Queries Is NP-Hard
5: Efficient Approximation Algorithms for Scheduling Coflows with Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion Time
6: A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
7: Budgeted Matroid Maximization: a Parameterized Viewpoint
8: Private Data Stream Analysis for Universal Symmetric Norm Estimation
9: Improved Diversity Maximization Algorithms for Matching and Pseudoforest
10: On the Exponential Growth of Geometric Shapes
11: Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
12: A Linear Time Quantum Algorithm for Pairwise Sequence Alignment
13: Predicting Memory Demands of BDD Operations using Maximum Graph Cuts (Extended Paper)
14: Parameterised distance to local irregularity
15: Tight Algorithmic Applications of Clique-Width Generalizations
16: Temporal network compression via network hashing
17: Direct sampling of short paths for contiguous partitioning
18: Maximizing Social Welfare in Score-Based Social Distance Games
19: $\ell_p$-Regression in the Arbitrary Partition Model of Communication
20: Quantitative Comparison of Nearest Neighbor Search Algorithms
21: Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning
22: Parameterized Results on Acyclic Matchings with Implications for Related Problems
23: Computing Subset Vertex Covers in $H$-Free Graphs
24: Distance-Preserving Graph Compression Techniques
25: Ellipsoid Fitting Up to a Constant
26: Sublinear Time Shortest Path in Expander Graphs
27: Connectivity Labeling and Routing with Multiple Vertex Failures
28: Diagonally-Addressed Matrix Nicknack: How to improve SpMV performance
29: Cornerstone: Octree Construction Algorithms for Scalable Particle Simulations
30: Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective
31: Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication
32: Faster Rectangular Matrix Multiplication by Combination Loss Analysis
33: Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
34: Edge-Coloring Algorithms for Bounded Degree Multigraphs
35: The Algorithmic Phase Transition of Random Graph Alignment Problem
36: Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems
37: Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
38: Approximation algorithms for the square min-sum bin packing problem
39: Planar Disjoint Paths, Treewidth, and Kernels
40: The complexity of non-stationary reinforcement learning
41: Local elimination in the traveling salesman problem
42: A Noise Resilient Transformation for Streaming Algorithms
43: Parallelising Glauber dynamics
44: Approximating Edit Distance in the Fully Dynamic Model
45: A $(3/2 + \varepsilon)$-Approximation for Multiple TSP with a Variable Number of Depots
46: ~Optimal Fault-Tolerant Reachability Labeling in Planar Graphs
47: On Interpolating Experts and Multi-Armed Bandits
48: Random Wheeler Automata
49: Universal lower bound for community structure of sparse graphs
50: Graph Search Trees and Their Leaves
51: Delaying Decisions and Reservation Costs
52: Sparse induced subgraphs in P_6-free graphs
53: Beyond the worst case: Distortion in impartial culture electorates
54: Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
55: Efficient Strongly Polynomial Algorithms for Quantile Regression
56: The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
57: Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint
58: Fast Algorithms for a New Relaxation of Optimal Transport