StringologyTimes

Data Structures and Algorithms: 2021/7/08-14

1: Burrows Wheeler Transform on a Large Scale: Algorithms Implemented in Apache Spark
2: Space-Efficient Fault-Tolerant Diameter Oracles
3: Fast Online Algorithms for Linear Programming
4: On Submodular Prophet Inequalities and Correlation Gap
5: An Efficient Reduction of a Gammoid to a Partition Matroid
6: Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses
7: Keep That Card in Mind: Card Guessing with Limited Memory
8: Balanced Allocations with Incomplete Information: The Power of Two Queries
9: Perfect Sampling for (Atomic) Lov'asz Local Lemma
10: SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
11: A Tight Max-Flow Min-Cut Duality Theorem for Non-Linear Multicommodity Flows
12: The Three-Dimensional Stable Roommates Problem with Additively Separable Preferences
13: Multiaccurate Proxies for Downstream Fairness
14: Preventing Small $\mathbf{(s,t)}$-Cuts by Protecting Edges
15: Optimal Space and Time for Streaming Pattern Matching
16: Preserving Diversity when Partitioning: A Geometric Approach
17: Approximation algorithms for the directed path partition problems
18: Lower Bounds for Prior Independent Algorithms
19: Hitting Weighted Even Cycles in Planar Graphs
20: Connected $k$-partition of $k$-connected graphs and $c$-claw-free graphs
21: Analysis of Smooth Heaps and Slim Heaps
22: The Mixed Page Number of Graphs
23: Efficient and Effective Algorithms for Revenue Maximization in Social Advertising
24: CLAP: A New Algorithm for Promise CSPs
25: On Universal D-Semifaithful Coding for Memoryless Sources with Infinite Alphabets
26: Finding a Maximum Clique in a Grounded 1-Bend String Graph
27: Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
28: Inapproximability of counting hypergraph colourings
29: Strongly Hyperbolic Unit Disk Graphs
30: Strong recovery of geometric planted matchings
31: Forster Decomposition and Learning Halfspaces with Noise
32: In-Database Regression in Input Sparsity Time
33: Worst-Case Welfare of Item Pricing in the Tollbooth Problem
34: Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
35: Computational Hardness of the Hylland-Zeckhauser Scheme
36: Noisy searching: simple, fast and correct
37: A Parallel Approximation Algorithm for Maximizing Submodular $b$-Matching
38: Multi-token Markov Game with Switching Costs
39: Polynomial delay algorithm for minimal chordal completions
40: Towards exact structural thresholds for parameterized complexity
41: Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
42: Bag-of-Tasks Scheduling on Related Machines
43: Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
44: Robust Learning of Optimal Auctions
45: The Perfect Matching Cut Problem Revisited
46: A Theoretical Framework for Learning from Quantum Data
47: A QPTAS for stabbing rectangles
48: Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
49: Oblivious sketching for logistic regression
50: Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
51: ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
52: Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds