Cover Image

The Fundamental Limits of Recovering Planted Subgraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lee, Daniel, Pernice, Francisco, Rajaraman, Amit, Zadik, Ilias
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Discrete Mathematics Information Theory Combinatorics Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
by: Bangachev, Kiril, et al.
Published: (2024)

The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models
by: Gunderson, Lee M, et al.
Published: (2024)

The maximal hard-core model as a recoverable system: Gibbs measures and phase coexistence
by: Wang, Geyang, et al.
Published: (2025)

Smoothed Analysis of the Komlós Conjecture: Rademacher Noise
by: Aigner-Horev, Elad, et al.
Published: (2023)

Recoverable systems and the maximal hard-core model on the triangular lattice
by: Wang, Geyang, et al.
Published: (2026)

Group Testing: An Information Theory Perspective
by: Aldridge, Matthew, et al.
Published: (2019)

Exact Thresholds for Noisy Non-Adaptive Group Testing
by: Chen, Junren, et al.
Published: (2024)

Enumeration of Row-Column Designs
by: Jäger, Gerold, et al.
Published: (2024)

Detecting Arbitrary Planted Subgraphs in Random Graphs
by: Elimelech, Dor, et al.
Published: (2025)

A Method for Generating Connected Erdos-Renyi Random Graphs
by: Chinyaev, Boris
Published: (2025)

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
by: Bangachev, Kiril, et al.
Published: (2024)

Six Permutation Patterns Force Quasirandomness
by: Crudele, Gabriel, et al.
Published: (2023)

On the clique number of random Cayley graphs and related topics
by: Conlon, David, et al.
Published: (2024)

Graph-theoretical estimates of the diameters of the Rubik's Cube groups
by: Hirata, So
Published: (2024)

Constructing $k$-ary Orientable Sequences with Asymptotically Optimal Length
by: Gabrić, Daniel, et al.
Published: (2024)

Causal Models for Growing Networks
by: Bravo-Hermsdorff, Gecia, et al.
Published: (2025)

Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences
by: Gabric, Daniel, et al.
Published: (2026)

Geometric planted matchings beyond the Gaussian model
by: Schwengber, Lucas da Rocha, et al.
Published: (2024)

Optimal Erasure Codes and Codes on Graphs
by: Chen, Yeyuan, et al.
Published: (2025)

The Labeled Coupon Collector Problem
by: Tan, Andrew, et al.
Published: (2025)

Reconstructing graphs with subgraph compositions
by: Dailly, Antoine, et al.
Published: (2025)

On Average Distance, Level-1 Fourier Weight, and Chang's Lemma
by: Yu, Lei
Published: (2025)

On the Codebook Design for NOMA Schemes from Bent Functions
by: Li, Chunlei, et al.
Published: (2025)

Universal cycle constructions for k-subsets and k-multisets
by: Campbell, Colin, et al.
Published: (2026)

Generalized Three and Four Person Hat Game
by: van Uem, Theo
Published: (2017)

Permutation and Multi-permutation Codes Correcting Multiple Deletions
by: Wang, Shuche, et al.
Published: (2024)

Threshold rates for properties of random codes
by: Guruswami, Venkatesan, et al.
Published: (2020)

Asymptotic Rate Bounds and Constructions for the Inclusive Variant of Disjunct Matrices
by: Mizunuma, Yuto, et al.
Published: (2026)

Evaluating the Gilbert-Varshamov Bound for Constrained Systems
by: Goyal, Keshav, et al.
Published: (2024)

Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics
by: Goyal, Keshav, et al.
Published: (2024)

Improved Upper Bound for the Size of a Trifferent Code
by: Bhandari, Siddharth, et al.
Published: (2024)

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Optimal Repair Bandwidth and Repair I/O of $(n,n-2,2)$ MDS Array Codes
by: Wu, Huawei
Published: (2026)

A Bayesian Proof and Interpretation of Talagrand's Majorizing Measure Theorem
by: Zadik, Ilias
Published: (2026)

The q-ary Gilbert-Varshamov bound can be improved for all but finitely many positive integers q
by: Liang, Xue-Bin
Published: (2024)

Decoupling of clusters in independent sets in a percolated hypercube
by: Chowdhury, Mriganka Basu Roy, et al.
Published: (2025)

Gaussian to log-normal transition for independent sets in a percolated hypercube
by: Chowdhury, Mriganka Basu Roy, et al.
Published: (2024)

Thinned Quantile Shares are Universally Feasible
by: Jain, Vishesh, et al.
Published: (2026)

Limit Laws for Critical Dispersion on Complete Graphs
by: De Ambroggio, Umberto, et al.
Published: (2024)

A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
by: Ta, Hoang, et al.
Published: (2025)