Copertina

New Bounds for Circular Trace Reconstruction

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Burudgunte, Arnav, Valiant, Paul, Wang, Hongao
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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

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

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

Improved Circular Dictionary Matching
di: Cotumaccio, Nicola
Pubblicazione: (2025)

Approximate Circular Pattern Matching
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2022)

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

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

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

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

Distance Reconstruction of Sparse Random Graphs
di: Bastide, Paul
Pubblicazione: (2024)

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

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

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

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

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

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

Counting Unit Circular Arc Intersections
di: Wang, Haitao
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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