Image de couverture de livre

Near-Optimal Trace Reconstruction for Mildly Separated Strings

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Aamand, Anders, Liu, Allen, Narayanan, Shyam
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the Structure of Replicable Hypothesis Testers
par: Aamand, Anders, et autres
Publié: (2025)

Statistical-Computational Trade-offs for Density Estimation
par: Aamand, Anders, et autres
Publié: (2024)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
par: Narayanan, Shyam, et autres
Publié: (2024)

Skirting Additive Error Barriers for Private Turnstile Streams
par: Aamand, Anders, et autres
Publié: (2026)

Online Sorting and Translational Packing of Convex Polygons
par: Aamand, Anders, et autres
Publié: (2021)

Hashing for Sampling-Based Estimation
par: Aamand, Anders, et autres
Publié: (2024)

Differentially Private Quantiles with Smaller Error
par: Imola, Jacob, et autres
Publié: (2025)

How fast can you find a good hypothesis?
par: Aamand, Anders, et autres
Publié: (2025)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
par: Aamand, Anders, et autres
Publié: (2025)

Improved algorithms for learning quantum Hamiltonians, via flat polynomials
par: Narayanan, Shyam
Publié: (2024)

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
par: Rivkin, Joey, et autres
Publié: (2024)

Near-real-time Solutions for Online String Problems
par: Köppl, Dominik, et autres
Publié: (2026)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
par: Blikstad, Joakim, et autres
Publié: (2025)

Improved Approximations for Hard Graph Problems using Predictions
par: Aamand, Anders, et autres
Publié: (2025)

Learning-Augmented Frequent Directions
par: Aamand, Anders, et autres
Publié: (2025)

Time-Optimal Construction of String Synchronizing Sets
par: Ellert, Jonas, et autres
Publié: (2026)

When is String Reconstruction using de Bruijn Graphs Hard?
par: Bals, Ben, et autres
Publié: (2025)

Simple and Optimal Sublinear Algorithms for Mean Estimation
par: Bertolotti, Beatrice, et autres
Publié: (2024)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
par: Hunkenschröder, Christoph, et autres
Publié: (2025)

New Bounds for Circular Trace Reconstruction
par: Burudgunte, Arnav, et autres
Publié: (2025)

Nearly Optimal List Labeling
par: Bender, Michael A., et autres
Publié: (2024)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
par: Dughmi, Shaddin, et autres
Publié: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
par: De, Rajat, et autres
Publié: (2025)

Nearly Optimal Internal Dictionary Matching
par: Chen, Jingbang, et autres
Publié: (2023)

Differentially Private Gomory-Hu Trees
par: Aamand, Anders, et autres
Publié: (2024)

Near-Optimal Dimension Reduction for Facility Location
par: Huang, Lingxiao, et autres
Publié: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
par: Sulser, Aurelio L., et autres
Publié: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Near-Optimal Property Testers for Pattern Matching
par: Jin, Ce, et autres
Publié: (2025)

Transposition is Nearly Optimal for IID List Update
par: Coester, Christian
Publié: (2026)

Near-Optimal Directed Low-Diameter Decompositions
par: Bringmann, Karl, et autres
Publié: (2025)

Near-Optimal Heaps and Dijkstra on Pointer Machines
par: van der Hoog, Ivor, et autres
Publié: (2026)

Nearly Optimal Bounds for Stochastic Online Sorting
par: Hu, Yang
Publié: (2025)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
par: Chhabra, Adil, et autres
Publié: (2025)

Optimal Rounding for Two-Stage Bipartite Matching
par: Pollner, Tristan, et autres
Publié: (2025)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
par: Duyster, Anouk, et autres
Publié: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

A Near-Optimal Kernel for a Coloring Problem
par: Haviv, Ishay, et autres
Publié: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
par: Costa, Martín, et autres
Publié: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
par: Dai, Jiangqi, et autres
Publié: (2025)