StringologyTimes

Data Structures and Algorithms: 2024/5/08-14

1: BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
2: Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)
3: Online List Labeling with Near-Logarithmic Writes
4: Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
5: Cryptanalysis of the SIMON Cypher Using Neo4j
6: Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
7: Testing the Fairness-Accuracy Improvability of Algorithms
8: Counting Cohesive Subgraphs with Hereditary Properties
9: Sorting multibay block stacking storage systems
10: Fast Computation of Leave-One-Out Cross-Validation for $k$-NN Regression
11: Dynamic Data Layout Optimization with Worst-case Guarantees
12: Low-Distortion Clustering in Bounded Growth Graphs
13: Is Transductive Learning Equivalent to PAC Learning?
14: Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
15: SPIDER: Improved Succinct Rank and Select Performance
16: Brooks-type colourings of digraphs in linear time
17: Distributed Least Squares in Small Space via Sketching and Bias Reduction
18: Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
19: Reconfiguration of Multisets with Applications to Bin Packing
20: Partially Ordered Sets Corresponding to the Partition Problem
21: Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
22: Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
23: Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
24: New Algorithms and Lower Bounds for Streaming Tournaments
25: A Lock-free Binary Trie
26: Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs
27: A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
28: Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
29: Fast Mixing in Sparse Random Ising Models
30: Tree Proof-of-Position Algorithms
31: A (Weakly) Polynomial Algorithm for AIVF Coding
32: Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes
33: Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
34: A Vector Representation for Phylogenetic Trees
35: PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
36: Stochastic Bandits with ReLU Neural Networks
37: Distributed Lov'{a}sz Local Lemma under Bandwidth Limitations
38: Concurrent aggregate queries
39: Practical Computation of Graph VC-Dimension
40: Decentralized Distributed Graph Coloring: Cluster Graphs
41: Optimal Matrix Sketching over Sliding Windows
42: Distribution Learning Meets Graph Structure Sampling
43: Active Learning with Simple Questions
44: Online Load and Graph Balancing for Random Order Inputs
45: Faster algorithms for the alignment of sparse correlated Erd"os-R'enyi random graphs
46: Anytime Sorting Algorithms (Extended Version)
47: Online busy time scheduling with flexible jobs