Cover Image

Graph Reconstruction from Noisy Random Subgraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	McGregor, Andrew, Sengupta, Rik
Format:	Preprint
Published:	2024
Subjects:	Information Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Random Subgraph Detection Using Queries
by: Huleihel, Wasim, et al.
Published: (2021)

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

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
by: Rao, Shravas
Published: (2023)

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
by: Wang, Ziao, et al.
Published: (2022)

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

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
by: Chakrabarti, Amit, et al.
Published: (2024)

Succinct Preferential Attachment Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme
by: Li, Xiaxin, et al.
Published: (2024)

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
by: Guo, Zeyu, et al.
Published: (2023)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

Compression with Privacy-Preserving Random Access
by: Chandar, Venkat, et al.
Published: (2025)

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

Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
by: Basu, Sabyasachi, et al.
Published: (2024)

Low-degree Security of the Planted Random Subgraph Problem
by: Bogdanov, Andrej, et al.
Published: (2024)

Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
by: Morgan, Alexander, et al.
Published: (2026)

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

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)

Hardness and Approximability of Dimension Reduction on the Probability Simplex
by: Bruno, Roberto
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)

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)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
by: Peikert, Chris, et al.
Published: (2025)

Old and New Results on Alphabetic Codes
by: Bruno, Roberto, et al.
Published: (2025)

Lower Bounds on Adaptive Sensing for Matrix Recovery
by: Kacham, Praneeth, et al.
Published: (2023)