StringologyTimes

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

1: Refined bounds for algorithm configuration: The knife-edge of dual class approximability
2: Personalized PageRank to a Target Node, Revisited
3: How to Count Triangles, without Seeing the Whole Graph
4: Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
5: Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
6: Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization
7: Adaptive Discretization for Adversarial Lipschitz Bandits
8: A Convergent and Dimension-Independent Min-Max Optimization Algorithm
9: Improved Bounds for Metric Capacitated Covering Problems
10: Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
11: Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
12: Distributional Individual Fairness in Clustering
13: Similarity Search with Tensor Core Units
14: An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
15: Approximation Algorithms for Sparse Principal Component Analysis
16: Combinatorial Pure Exploration of Dueling Bandit
17: BETULA: Numerically Stable CF-Trees for BIRCH Clustering
18: Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
19: Approximation algorithms for general cluster routing problem
20: Learning Based Distributed Tracking
21: The Bike Sharing Problem
22: Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
23: Lower Bounds on Rate of Convergence of Matrix Products in All Pairs Shortest Path of Social Network
24: Approximation algorithms for the MAXSPACE advertisement problem
25: Provably and Efficiently Approximating Near-cliques using the Tur'an Shadow: PEANUTS
26: Online Dense Subgraph Discovery via Blurred-Graph Feedback
27: Improved Circular $k$-Mismatch Sketches
28: Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
29: Kernelization of Whitney Switches
30: The Power of Connection: Leveraging Network Analysis to Advance Receivable Financing
31: A Parameterized Family of Meta-Submodular Functions
32: Acyclic coloring of special digraphs
33: Discrepancy Minimization via a Self-Balancing Walk
34: Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
35: Small Longest Tandem Scattered Subsequences
36: A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
37: Reconfiguration of Spanning Trees with Many or Few Leaves
38: New Approximations and Hardness Results for Submodular Partitioning Problems
39: Approximation Algorithms for Clustering with Dynamic Points
40: Augmenting the Algebraic Connectivity of Graphs
41: Practical Trade-Offs for the Prefix-Sum Problem
42: Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
43: Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
44: APX-Hardness and Approximation for the k-Burning Number Problem
45: Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
46: On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
47: Computing all $s$-$t$ bridges and articulation points simplified
48: Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
49: Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship
50: Optimizing Cuckoo Filter for high burst tolerance,low latency, and high throughput
51: Reconstructing Biological and Digital Phylogenetic Trees in Parallel
52: The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
53: Submodular Combinatorial Information Measures with Applications in Machine Learning
54: Queues with Small Advice
55: Parallel Weighted Model Counting with Tensor Networks
56: Random Access in Persistent Strings and Segment Selection
57: A Polynomial Kernel for Line Graph Deletion
58: JAMPI: efficient matrix multiplication in Spark using Barrier Execution Mode