StringologyTimes

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

1: An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem
2: Polynomial Logical Zonotopes: A Set Representation for Reachability Analysis of Logical Systems
3: Memory-Query Tradeoffs for Randomized Convex Optimization
4: On Differentially Private Sampling from Gaussian and Product Distributions
5: Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters
6: The Power of Menus in Contract Design
7: Counting occurrences of patterns in permutations
8: Fast Compression of Deterministic Finite Automata
9: On boundedness of zeros of the independence polynomial of tori
10: SQ Lower Bounds for Learning Bounded Covariance GMMs
11: Adversarial Resilience in Sequential Prediction via Abstention
12: Breaking the cubic barrier in the Solovay-Kitaev algorithm
13: Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps
14: On minimum $t$-claw deletion in split graphs
15: Fair integer programming under dichotomous and cardinal preferences
16: Improved Competitive Ratios for Online Bipartite Matching on Degree Bounded Graphs
17: Adaptive Privacy Composition for Accuracy-first Mechanisms
18: A Dynamic Data Structure for Representing Timed Transitive Closures on Disk
19: On Scalable Testing of Samplers
20: Approximation Algorithm for Unrooted Prize-Collecting Forest with Multiple Components and Its Application on Prize-Collecting Sweep Coverage
21: On finding 2-cuts and 3-edge-connected components in parallel
22: An FPT Algorithm for Splitting a Necklace Among Two Thieves
23: Approximation algorithms for $k$-submodular maximization subject to a knapsack constraint
24: Prefix-free graphs and suffix array construction in sublinear space
25: Towards Optimal Effective Resistance Estimation
26: Approximate Counting for Spin Systems in Sub-Quadratic Time
27: Robust and Space-Efficient Dual Adversary Quantum Query Algorithms
28: Synthesis of Quantum Vector Databases Based on Grovers Algorithm
29: Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations
30: On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs
31: On Detecting Some Defective Items in Group Testing
32: Scheduling with a Limited Testing Budget
33: Asynchronous Algorithmic Alignment with Cocycles
34: Ticketed Learning-Unlearning Schemes
35: Planar graphs are acyclically edge $(\Delta + 5)$-colorable
36: Increasing the Measured Effective Quantum Volume with Zero Noise Extrapolation
37: Pb-Hash: Partitioned b-bit Hashing
38: Erasing-based lossless compression method for streaming floating-point time series
39: Approximate Cartesian Tree Matching: an Approach Using Swaps
40: Refining the Adaptivity Notion in the Huge Object Model
41: New Menger-like dualities in digraphs and applications to half-integral linkages