:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Burudgunte, Arnav, Valiant, Paul, Wang, Hongao
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2512.02412
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
by: Rivkin, Joey, et al.
Published: (2024)

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
by: Aliakbarpour, Maryam, et al.
Published: (2025)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
by: Pabbaraju, Chirag, et al.
Published: (2025)

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
by: Compton, Spencer, et al.
Published: (2025)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
by: Alon, Noga, et al.
Published: (2024)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
by: Aamand, Anders, et al.
Published: (2024)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
by: Jain, Sanjay, et al.
Published: (2026)

Improved Circular Dictionary Matching
by: Cotumaccio, Nicola
Published: (2025)

Approximate Circular Pattern Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2022)

Discovering Data Structures: Nearest Neighbor Search and Beyond
by: Salemohamed, Omar, et al.
Published: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
by: Ghosh, Prantar, et al.
Published: (2024)

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
by: Paschmanns, Paul, et al.
Published: (2026)

Distance Reconstruction of Sparse Random Graphs
by: Bastide, Paul
Published: (2024)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
by: Bhaskara, Aditya, et al.
Published: (2024)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Approximate Circular Pattern Matching under Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

Counting Unit Circular Arc Intersections
by: Wang, Haitao
Published: (2026)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
by: Jin, Mingming, et al.
Published: (2023)

C*: A New Bounding Approach for the Moving-Target Traveling Salesman Problem
by: Philip, Allen George, et al.
Published: (2023)

Efficient Trace Frequency Queries in Sparse Graphs
by: Awofeso, Christine, et al.
Published: (2025)

Trace reconstruction from local statistical queries
by: Chen, Xi, et al.
Published: (2024)

Dynamic Network Discovery via Infection Tracing
by: Bals, Ben, et al.
Published: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

On Rotation Distance of Rank Bounded Trees
by: M., Anoop S. K., et al.
Published: (2023)

A Subquadratic Bound for Online Bisection
by: Bienkowski, Marcin, et al.
Published: (2023)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)