StringologyTimes

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

1: A Tight Analysis of Bethe Approximation for Permanent
2: Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
3: Connecting Knowledge Compilation Classes and Width Parameters
4: Maximum Distance Sub-Lattice Problem
5: $O(\log^2k/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
6: Branch and bound algorithm for the traveling salesman problem is not a direct type algorithm
7: An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
8: Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
9: Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
10: Private Continual Release of Real-Valued Data Streams
11: An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
12: Stochastic Matching with Few Queries: New Algorithms and Tools
13: Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
14: Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)
15: Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
16: An O^(star)(2.619^k) algorithm for 4-path vertex cover
17: Density estimation for shift-invariant multidimensional distributions
18: Towards Instance-Optimal Private Query Release
19: Minimizing and Computing the Inverse Geodesic Length on Trees
20: Unique End of Potential Line
21: A Convergence Theory for Deep Learning via Over-Parameterization
22: A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
23: An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums
24: Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
25: Two Party Distribution Testing: Communication and Security
26: Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions
27: An efficient branch-and-bound algorithm for submodular function maximization
28: Efficiently Approximating Edit Distance Between Pseudorandom Strings
29: Coverage Centrality Maximization in Undirected Networks
30: Faster sublinear approximations of $k$-cliques for low arboricity graphs
31: Approximation Algorithms for Graph Burning
32: Computational Complexity Analysis of Genetic Programming
33: Tractability of Konig Edge Deletion Problems
34: MR-RePair: Grammar Compression based on Maximal Repeats
35: Streaming Hardness of Unique Games
36: A Review for Weighted MinHash Algorithms
37: Sliding Window Temporal Graph Coloring
38: Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
39: Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
40: Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
41: Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
42: Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
43: Approximating minimum representations of key Horn functions
44: Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
45: Submodular Optimization Over Streams with Inhomogeneous Decays
46: Robustness of spectral methods for community detection
47: Randomisation Algorithms for Large Sparse Matrices
48: Pareto Optimization for Subset Selection with Dynamic Cost Constraints
49: A Tutorial on Formulating and Using QUBO Models