Cover Image

A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rivkin, Joey, Valiant, Gregory, Valiant, Paul
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

New Bounds for Circular Trace Reconstruction
by: Burudgunte, Arnav, et al.
Published: (2025)

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

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

On the Statistical Complexity of Sample Amplification
by: Axelrod, Brian, et al.
Published: (2022)

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

An Instance-Based Approach to the Trace Reconstruction Problem
by: Mazooji, Kayvon, et al.
Published: (2024)

Hardness and Approximability of Dimension Reduction on the Probability Simplex
by: Bruno, Roberto
Published: (2024)

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

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

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

Analyzing Collection Strategies: A Computational Perspective on the Coupon Collector Problem
by: Abraham, Hadas, et al.
Published: (2026)

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

A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
by: Wang, Xinzhao, et al.
Published: (2022)

The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings
by: Hou, Jiaxin, et al.
Published: (2023)

An Additive Approximation Scheme for Generating Dyadic Codings for the Outputs of an LLM
by: Bar-Lev, Daniella, et al.
Published: (2026)

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
by: Al-okaily, Anas
Published: (2024)

Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
by: Ahmadypour, Niloufar, et al.
Published: (2020)

A probabilistic analysis on general probabilistic scheduling problems
by: Suruga, Daiki
Published: (2024)

Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
by: Bruno, Roberto, et al.
Published: (2025)

A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data
by: Smart, Bridget, et al.
Published: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

Key Compression Limits for $k$-Minimum Value Sketches
by: Dickens, Charlie, et al.
Published: (2024)

Capacity-Achieving Gray Codes
by: Guruswami, Venkatesan, et al.
Published: (2024)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Investigations on Algorithm Selection for Interval-Based Coding Methods
by: Strutz, Tilo, et al.
Published: (2024)

More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
by: Ghentiyala, Surendra, et al.
Published: (2024)

Continuous Optimization for Decoding Errors
by: Srivastava, Shashank
Published: (2024)

Towards Optimal Grammars for RNA Structures
by: Onokpasa, Evarista, et al.
Published: (2024)

Scheduling Multi-Server Jobs is Not Easy
by: Vaze, Rahul
Published: (2024)

Tight bounds for stream decodable error-correcting codes
by: Gupta, Meghal, et al.
Published: (2024)

Improved Approximation Algorithms for Index Coding
by: Chawin, Dror, et al.
Published: (2024)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication
by: Ly, Hoang, et al.
Published: (2025)

Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
by: Löffler, Maarten, et al.
Published: (2026)

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
by: Pettie, Seth, et al.
Published: (2020)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

Pcodec: Better Compression for Numerical Sequences
by: Loncaric, Martin, et al.
Published: (2025)