arXiv preprint ·
Efficient Recovery of Latent Coordinate Structure from Sparse Observations of the Hypercube
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=2^d$ vertices, each corresponding to a distinct "feature" vector in $\{\pm 1\}^d$. Between each pair whose feature vectors are at Hamming distance one, an edge is observed independently with probability $p$. As long as the expected degree $pd$ is $\gtrsim \log d = \log \log n$, we give a polynomial-time algorithm that, given only the graph of observed edges, correctly recovers the entire feature vector of all but a vanishing fraction of vertices. This matches the information-theoretic guarantee of Kapralov, Trevisan, and Wrzos-Kaminska in polynomial rather than exponential time, resolving the algorithmic question left open by their work. Our algorithm combines a degree-$4$ sum-of-squares certificate for the structure of balanced near-minimum cuts with a rounding scheme originally developed for tensor decomposition by Ma, Shi, and Steurer (2016). The analysis relies on two novel ingredients: a sum-of-squares version of the Friedgut-Kalai-Naor theorem in Boolean Fourier analysis and a spectral concentration result for the observed subgraph of the hypercube. Finally, we provide a justification for why higher-degree sum-of-squares might be needed by showing a limitation of the basic SDP relaxation of this problem.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
The chromatic number of the associahedron: simple and logarithmic
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.