StringologyTimes

Data Structures and Algorithms: 2022/8/08-14

1: Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem
2: Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms
3: MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
4: Exact Learning of Multitrees and Almost-Trees Using Path Queries
5: Combinatorial Optimization via the Sum of Squares Hierarchy
6: Almost optimal searching of maximal subrepetitions in a word
7: A note on independent sets in sparse-dense graphs
8: Multi Purpose Routing: New Perspectives and Approximation Algorithms
9: An Improved Trickle-Down Theorem for Partite Complexes
10: Training Overparametrized Neural Networks in Sublinear Time
11: Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy
12: Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams
13: Co-lexicographically Ordering Automata and Regular Languages – Part I
14: Computing Brascamp-Lieb Constants through the lens of Thompson Geometry
15: Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
16: Local Differentially Private Fuzzy Counting in Stream Data using Probabilistic Data Structure
17: Knapsack Secretary Through Boosting
18: Computing the theta function
19: Designing a 3D Parallel Memory-Aware Lattice Boltzmann Algorithm on Manycore Systems
20: Learning Computation Bounds for Branch-and-Bound Algorithms to k-plex Extraction
21: Smoothed Analysis of Information Spreading in Dynamic Networks
22: Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
23: Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
24: Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)
25: Avoider-Enforcer Game is NP-hard
26: Sharp Frequency Bounds for Sample-Based Queries
27: An Improved Greedy Algorithm for Stochastic Online Scheduling on Unrelated Machines
28: Exact Exponential Algorithms for Clustering Problems
29: An improved lower bound on the length of the longest cycle in random graphs