StringologyTimes

Data Structures and Algorithms: 2022/12/08-14

1: An improved approximation guarantee for Prize-Collecting TSP
2: Why the equivalence problem for unambiguous grammars has not been solved back in 1966?
3: Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
4: Cocke–Younger–Kasami–Schwartz–Zippel algorithm and relatives
5: Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions
6: Fast and Practical DAG Decomposition with Reachability Applications
7: DeMEtRIS: Counting (near)-Cliques by Crawling
8: A refinement on the structure of vertex-critical ($P_5$, gem)-free graphs
9: Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
10: A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
11: Robustness Implies Privacy in Statistical Estimation
12: Transcoding Unicode Characters with AVX-512 Instructions
13: Efficient and Generic Algorithms for Quantitative Attack Tree Analysis
14: Beyond circular-arc graphs – recognizing lollipop graphs and medusa graphs
15: Algorithms approaching the threshold for semi-random planted clique
16: Binary Error-Correcting Codes with Minimal Noiseless Feedback
17: Minimum-weight partitioning of a set with associated subsets
18: Scalable Recovery-based Adaptation on Quadtree Meshes for Advection-Diffusion-Reaction Problems
19: A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
20: Dynamic Maxflow via Dynamic Interior Point Methods
21: How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions
22: Streaming Euclidean MST to a Constant Factor
23: Dimensionality reduction on complex vector spaces for Euclidean distance with dynamic weights
24: Fast Number Parsing Without Fallback
25: Profit Maximization in Social Networks and Non-monotone DR-submodular Maximization
26: On computing the vertex connectivity of 1-plane graphs
27: Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput
28: Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs
29: Data Structures for Approximate Discrete Fr'echet Distance