StringologyTimes

Data Structures and Algorithms: 2018/10/15-21

1: Super Strong ETH is False for Random $k$-SAT
2: No Place to Hide: Catching Fraudulent Entities in Tensors
3: Small Space Stream Summary for Matroid Center
4: CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata
5: An Illuminating Algorithm for the Light Bulb Problem
6: On Finding Dense Subgraphs in Bipartite Graphs: Linear Algorithms
7: Multi-budgeted directed cuts
8: Randomized contractions meet lean decompositions
9: Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
10: Enumerative and Structural Aspects Of Anagrams Without Fixed Letters
11: Nearly Optimal Space Efficient Algorithm for Depth First Search
12: Fast and Longest Rollercoasters
13: $k$-Servers with a Smile: Online Algorithms via Projections
14: An EPTAS for machine scheduling with bag-constraints
15: Payment Network Design with Fees
16: Algorithmic Blockchain Channel Design
17: Towards Optimal Running Times for Optimal Transport
18: The Matching Augmentation Problem: A $\frac74$-Approximation Algorithm
19: Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
20: Distributed $k$-Clustering for Data with Heavy Noise
21: Solving Linear Programs in the Current Matrix Multiplication Time
22: Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
23: Complexity of Computing the Anti-Ramsey Numbers for Paths
24: Locally Private Mean Estimation: Z-test and Tight Confidence Intervals
25: Towards a compact representation of temporal rasters
26: Best-of-two-worlds analysis of online search
27: Testing Matrix Rank, Optimally
28: FPT algorithms to recognize well covered graphs
29: A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
30: Bilu-Linial stability, certified algorithms and the Independent Set problem
31: New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
32: Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
33: Direct and Binary Direct Bases for One-set Updates of a Closure System
34: The Frontiers of Fairness in Machine Learning
35: MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
36: A Polynomial Time MCMC Method for Sampling from Continuous DPPs