StringologyTimes

Data Structures and Algorithms: 2023/3/29-31

1: Faster Deterministic Distributed MIS and Approximate Matching
2: Universal Coating by 3D Hybrid Programmable Matter
3: Lower Bounds for Pseudo-Deterministic Counting in a Stream
4: Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
5: Certified Hardness vs. Randomness for Log-Space
6: Training Neural Networks is NP-Hard in Fixed Dimension
7: A Subquadratic Time Algorithm for the Weighted $k$-Center Problem on Cactus Graphs
8: Capacity-Preserving Subgraphs of Directed Flow Networks
9: Advice Complexity bounds for Online Delayed F-Node-, H-Node- and H-Edge-Deletion Problems
10: Sum-of-Squares Lower Bounds for Densest $k$-Subgraph
11: The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
12: Pseudorandom Linear Codes are List Decodable to Capacity
13: The Many Qualities of a New Directly Accessible Compression Scheme