StringologyTimes

Data Structures and Algorithms: 2020/4/22-28

1: Variable Decomposition for Prophet Inequalities and Optimal Ordering
2: Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
3: Faster and More Accurate Measurement through Additive-Error Counters
4: Optimal Online Algorithms for One-Way Trading and Online Knapsack Problems: A Unified Competitive Analysis
5: Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
6: Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
7: Some results on Vertex Separator Reconfiguration
8: Qd-tree: Learning Data Layouts for Big Data Analytics
9: Non-Adaptive Adaptive Sampling on Turnstile Streams
10: Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem
11: Coloring Problems on Bipartite Graphs of Small Diameter
12: Engineering Data Reduction for Nested Dissection
13: Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots
14: Conditionally optimal approximation algorithms for the girth of a directed graph
15: Efficient Algorithms for Approximating Quantum Partition Functions
16: Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
17: Robust testing of low-dimensional functions
18: Faster Parallel Multiterminal Cuts
19: A 12/7-approximation algorithm for the discrete Bamboo Garden Trimming problem
20: Incompressibility of H-free edge modification problems: Towards a dichotomy
21: Near optimal sparsity-constrained group testing: improved bounds and algorithms
22: A linear fixed parameter tractable algorithm for connected pathwidth
23: Finding Planted Cliques in Sublinear Time
24: Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
25: A general framework for enumerating equivalence classes of solutions
26: An algorithmic weakening of the Erd\H{o}s-Hajnal conjecture
27: Extending Partial 1-Planar Drawings
28: Online MinCut: Competitive and Regret Analysis
29: An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack
30: How to hide a clique?
31: An Efficient Index Method for the Optimal Route Query over Multi-Cost Networks
32: Succinct Filters for Sets of Unknown Sizes
33: Learning and Testing Junta Distributions with Subcube Conditioning
34: In-Place Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory
35: In-Place Bijective Burrows-Wheeler Transforms
36: On Perturbation Resilience of Non-Uniform $k$-Center
37: Input-Sparsity Low Rank Approximation in Schatten Norm
38: Robust Algorithms under Adversarial Injections
39: Approximate Turing Kernelization for Problems Parameterized by Treewidth
40: k-apices of minor-closed graph classes. II. Parameterized algorithms
41: An Extension of Pl"ucker Relations with Applications to Subdeterminant Maximization
42: Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
43: The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
44: New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
45: Testing Data Binnings
46: A verifiably secure and proportional committee election rule
47: Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation
48: Batched Predecessor and Sorting with Size-Priced Information in External Memory
49: Learning Lines with Ordinal Constraints
50: Certifying Certainty and Uncertainty in Approximate Membership Query Structures – Extended Version
51: Approximating longest common substring with $k$ mismatches: Theory and practice
52: Fast algorithms for general spin systems on bipartite expanders
53: As Time Goes By: Reflections on Treewidth for Temporal Graphs