StringologyTimes

Data Structures and Algorithms: 2020/11/08-14

1: Fast Low-Space Algorithms for Subset Sum
2: Combinatorial Bernoulli Factories
3: Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
4: Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
5: Scout Algorithm For Fast Substring Matching
6: The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
7: Computing Lengths of Non-Crossing Shortest Paths in Planar Graphs
8: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
9: Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
10: Mitigating Bias in Set Selection with Noisy Protected Attributes
11: Hardness of Approximation of Euclidean $k$-Median
12: An APTAS for Bin Packing with Clique-graph Conflicts
13: Ordered $k$-Median with Outliers and Fault-Tolerance
14: Streaming Algorithms for Geometric Steiner Forest
15: A Theory of Universal Learning
16: Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
17: Balanced Crown Decomposition for Connectivity Constraints
18: Reduced-Rank Regression with Operator Norm Error
19: Solving the Steiner Tree Problem with few Terminals
20: Correlation Decay and the Absence of Zeros Property of Partition Functions
21: LinCbO: fast algorithm for computation of the Duquenne-Guigues basis
22: Distributed Distance Approximation
23: Higher-Order Spectral Clustering of Directed Graphs
24: On the cut dimension of a graph
25: Speed-Robust Scheduling – Sand, Bricks, and Rocks
26: Testability of relations between permutations
27: Improving the Approximation Ratio for Capacitated Vehicle Routing
28: Group testing and local search: is there a computational-statistical gap?
29: Adaptive Community Search in Dynamic Networks
30: A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
31: Sampling Matrices from Harish-Chandra-Itzykson-Zuber Densities with Applications to Quantum Inference and Differential Privacy
32: Improving the Quantum Approximate Optimization Algorithm with postselection
33: List Decoding of Direct Sum Codes
34: Unique Decoding of Explicit $\epsilon$-balanced Codes Near the Gilbert-Varshamov Bound
35: An Instance-Based Algorithm for Deciding the Bias of a Coin
36: The Strongish Planted Clique Hypothesis and Its Consequences
37: PHONI: Streamed Matching Statistics with Multi-Genome References
38: A $(2+\varepsilon)$-approximation algorithm for preemptive weighted flow time on a single machine
39: Mastermind with a Linear Number of Queries
40: Counting Homomorphic Cycles in Degenerate Graphs
41: An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
42: Tree Embeddings for Hop-Constrained Network Design
43: Hardness of Approximate Nearest Neighbor Search under L-infinity
44: On 3-Coloring of $(2P_4,C_5)$-Free Graphs
45: Optimal Private Median Estimation under Minimal Distributional Assumptions
46: Approximating the Weighted Minimum Label $s$-$t$ Cut Problem
47: Online Virtual Machine Allocation with Predictions
48: FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective
49: Quantum algorithms for spectral sums
50: Communication Efficient Coresets for Maximum Matching
51: Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality
52: Towards Tight Bounds for Spectral Sparsification of Hypergraphs
53: Towards Better Approximation of Graph Crossing Number
54: Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
55: Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
56: Secretaries with Advice
57: Matching through Embedding in Dense Graphs
58: Consistent k-Clustering for General Metrics
59: The Submodular Santa Claus Problem in the Restricted Assignment Case
60: A grammar compressor for collections of reads with applications to the construction of the BWT
61: Efficient Subspace Search in Data Streams
62: Kernel Density Estimation through Density Constrained Near Neighbor Search
63: Parametric Graph Templates: Properties and Algorithms
64: Some remarks on hypergraph matching and the F"{u}redi-Kahn-Seymour conjecture
65: Adaptive Learning of Compressible Strings
66: Data-driven Algorithm Design
67: Entropy conservation for comparison-based algorithms