{"id":"d810b649-5665-45b1-bac1-50b6e51a0205","arxiv_id":"1908.01241","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A graph-based nearest-neighbor algorithm estimates sparse 3-tensors with small maximum entrywise error from p = n^{-3/2+κ} random observations per entry, nearly matching the conjectured efficient lower bound.","lead":"This paper introduces a similarity-based collaborative filtering algorithm that estimates a 3-way tensor from sparse random entries. The authors prove that it recovers low-rank tensors with small per-entry error using about n^{-3/2} observations per entry, nearly matching the conjectured computational limit for tensor completion.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Ideal-distance exponent mismatch: Eq. (5.2) uses Λ^{t+1}, while the proof of Lemma 5.2 (Lemmas 6.2/6.6/6.7) concentrates dist on Λ^{2t+1}; as written, Theorem 4.1 is not established.","rationale":"The reader's weakest assumption is the latent-variable restriction. I agree it is a genuine scope limitation, and the paper's own Section 2 note admits that the generative latent-variable model imposes smoothness beyond low rank. However, that restriction is an explicit assumption of Theorem 4.1, not a gap in its proof. The unproven robustness and approximate-low-rank claims in the abstract are a real overreach, but they extrapolate beyond the theorem rather than invalidate it. The most load-bearing issue for the central theorem itself is the exponent mismatch: the distance that the proof actually concentrates on differs from the distance used to define bias and meas. This is a concrete internal inconsistency, not a disagreement with consensus. It is fixable with constant-level changes, so it does not demand rejection; it does require a corrected exposition before the theorem can be considered proven. I also note the reader's concern about Lemma 6.7's conditional independence appears less serious: because rows a,b lie in B_{u,2t}∪B_{v,2t} while α,β lie in S, different columns use disjoint triplets, so the symmetric sampling model does not introduce dependence there. The exponent mismatch is the sharper concern, and it supports the reader's conditional verdict.","tokens_in":34086,"tokens_out":38364,"duration_ms":354955,"concrete_test":"Re-derive the limit of dist(u,v) from Eq. (3.3) using Lemma 6.2's approximation: substitute \\tilde N_{u,t} ≈ Λ^{2t} Q e_u and \\tilde N_{v,t} ≈ Λ^{2t} Q e_v into Z_uv = \\tilde N_u^T Q^T Λ^2 Q \\tilde N_v, obtaining Λ^{4t+2}. Then check whether Eq. (5.2) equals this; if not, replace (5.2) by d_actual = ||Λ^{2t+1}Q(eu−ev)||², adjust the Property 5.1 constant to 3B²√r |λ_r|^{−2t} and Property 5.3 constant to |λ_1|^{4t}L, and verify that the final MSE and MEE rates and probability exponents in Theorem 4.1 are unchanged. If the rates survive, Theorem 4.1 holds after a correction; if the constants propagate differently, the stated rates are unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 5.2 defines the ideal distance as d(θu,θv)=||Λ^{t+1}Q(eu−ev)||² (Eq. 5.2), and the bias and meas bounds in Theorem 4.1 are stated for that d. But the distance-concentration proof establishes a different target. Lemma 6.2 shows e_k^T Q \\tilde N_{u,t} ≈ e_k^T Λ^{2t} Q e_u. Lemma 6.6 then gives \\tilde N_u^T Q^T Λ^2 Q \\tilde N_v ≈ e_u^T Q^T Λ^{4t+2} Q e_v. Since dist(u,v) is built from Z_uv ≈ \\tilde N_u^T Q^T Λ^2 Q \\tilde N_v, the limiting quadratic form is Λ^{4t+2}, i.e. d_actual = ||Λ^{2t+1}Q(eu−ev)||². Section 6.5's Eq. (6.25) writes d = ||Λ^{2t}Q(eu−ev)||² = (eu−ev)^T Q^T Λ^{2t} Q(eu−ev), which is neither (5.2) nor d_actual and also mishandles the norm square. So the ideal distance used in the proof of Lemma 5.2 is inconsistent with the ideal distance used in the theorem. Because no assumption forces |λ_k|=1, the difference between the Λ^{4t+2} and Λ^{2t+2} cross terms is generally not O(n^{−(κ−ψ)}); Lemma 5.2 as stated is therefore not established. The gap is likely repairable by replacing (5.2) with d_actual and changing constants to |λ_r|^{−2t} (bias) and |λ_1|^{4t} (meas), since t=Θ(1), but it is a missing argument in the central theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies estimation of a symmetric 3-way tensor from independent noisy observations of entries with probability p, in the sparse regime p = n^{-3/2+κ}. It proposes a similarity-based collaborative filtering algorithm: flatten the tensor to an n-by-Θ(n^2) matrix, build BFS trees in the bipartite graph of observed entries, compute a distance between coordinates from bilinear forms of the BFS neighborhood vectors, and estimate each entry by averaging nearby observed entries. The main result, Theorem 4.1, claims MSE O(n^{-(κ-ψ)}) and maximum entrywise error O(n^{-(κ-ψ)/2}) with high probability, under a latent-variable model with bounded orthonormal eigenfunctions, constant rank, and an L-Lipschitz link function. The proof is via a chain of concentration lemmas: BFS growth (Lemma 6.1), quadratic-form concentration (Lemmas 6.2–6.6), and a column-average concentration (Lemma 6.7), culminating in Lemma 5.2 asserting that the estimated distance is within O(n^{-(κ-ψ)}) of an ideal distance.","tokens_in":34467,"tokens_out":31759,"duration_ms":287017,"significance":"If Theorem 4.1 were established, the contribution would be substantial: an elementary, parallelizable nearest-neighbor algorithm with provable consistency at p = n^{-3/2+κ}, matching the conjectured computational sample-complexity barrier without SOS or spectral methods, and with proof techniques for asymmetric flattened-matrix bilinear forms that could be of independent interest. The paper is also honest about the model restrictions (latent variables, Lipschitz f, bounded orthonormal eigenfunctions, r = Θ(1)) and about the practical limitations of the algorithm. However, the central proof currently contains several inconsistencies that prevent the main claim from being considered proved; the issues appear repairable, but they require substantive work rather than copyediting.","major_comments":[{"comment":"Lemma 6.2 shows Q\\tilde N_{u,t} ≈ Λ^{2t}Qe_u, and Lemma 6.6 then shows that the bilinear form \\tilde N_u^T Q^T Λ² Q \\tilde N_v concentrates on e_u^T Q^T Λ^{4t+2}Q e_v. Consequently the quantity Z_{uv} in (6.27) concentrates on e_u^T Q^T Λ^{4t+2}Q e_v, so the distance concentrates on ‖Λ^{2t+1}Q(e_u−e_v)‖². This is not the ideal distance d defined in (5.2) as ‖Λ^{t+1}Q(e_u−e_v)‖², and it is not the expression in (6.25), whose displayed equality is also algebraically wrong (the right-hand side equals ‖Λ^t Q(e_u−e_v)‖², not ‖Λ^{2t}Q(e_u−e_v)‖²). In addition, (3.3) and (6.26) put a leading 1/(|V_B|p²) or 1/(\\binom{|S|}{2}p²) in front of Z_{uu}+Z_{vv}−Z_{uv}−Z_{vu} although Z_{uv} already carries that normalization; with the printed definitions dist would be Θ(n^{−1+2κ}) too small. Because Lemma 5.2 is the bridge to Theorem 4.1 and no assumption forces |λ_k|=1, the proof of the main theorem is not established as written. The gap is plausibly repairable by defining the ideal distance as ‖Λ^{2t+1}Q(e_u−e_v)‖² and adjusting the constants in bias(η) and meas(η′) accordingly, but this needs to be done explicitly.","section":"§5.2, Eq. (5.2); §6.5, Eqs. (6.25)–(6.27); Lemmas 6.2 and 6.6"},{"comment":"The proof claims that, conditioned on F(u,v,t,x,δ) and {θ_i}_{i∈[n]}, the variables T(α,β) are independent across columns except for the case of the exact same pair, and that any shared-coordinate correlation is only through the latent variables. Under the symmetric observation model of Section 2, this is not correct: an observed triplet (a,α,β) is represented in the flattened matrix both as M_B(a,(α,β)) and as M_B(α,(a,β)), so e.g. T(α,β) and T(a,β) (or T(α,β) and T(α,γ) through the rows γ and β) contain the same random variable. The variance computation that follows sums Var[T(α,β)] over columns and omits these cross-column covariances, so the Bernstein bound on the sum of \\tilde T(α,β) is not justified. This is a load-bearing gap in Lemma 6.7 and hence in Lemma 5.2; it requires either a covariance calculation or a modification of the sampling/algorithm so that each observed triplet enters only one flattened entry.","section":"§6.4, proof of Lemma 6.7"},{"comment":"The proof bounds the bias introduced by the φ-threshold as O(n²(n^{−(1/2−κ)})^φ) and then concludes it is o(1). With φ = ⌈4/(1−2κ)⌉, at values of κ for which 4/(1−2κ) is an integer (e.g., κ = 1/4), this displayed bound is Θ(1), not o(1). The conclusion can be rescued by using the sharp growth bound from Lemma 6.1, |S_{u,t}∪S_{v,t}| = O(n^{2κt}) with t = ⌈1/(4κ)⌉, in place of the crude |S_{u,t}∪S_{v,t}| = O(n); but as written the argument does not prove the asserted o(1) uniformly in κ.","section":"§6.4, truncation bias in Lemma 6.7"}],"minor_comments":[{"comment":"The abstract and introduction state the result as recovery of low-rank or finite-rank tensors. Theorem 4.1 is proved only for the latent-variable model of Section 2 with iid Uniform[0,1] latent variables, bounded orthonormal eigenfunctions, constant rank, and an L-Lipschitz link function. The paper acknowledges this limitation on page 4, but the high-level claims should be phrased to match the theorem.","section":"Abstract and Introduction"},{"comment":"The set S≡S_{u,s,t} in (6.26) uses an undefined subscript s; it should be S_{u,v,t} = [n]\\(B_{u,2t}∪B_{v,2t}∪[n/2]) or similar.","section":"§6.5, Eq. (6.26)"},{"comment":"The explicit bound in Lemma 6.2 omits the dependence on the model constants B and on the eigenvalue factors that appear in the proof's variance summations; since these are constants this is cosmetic, but the statement should either include them or explicitly say constants are absorbed.","section":"Lemma 6.2 statement"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important question and the algorithmic idea is attractive, but the proof of the central Lemma 5.2 currently has multiple fixable inconsistencies: the target ideal distance is not the one attained by the concentration chain, the normalization of dist is inconsistent between the algorithm definition and the proof, and the conditional-independence assertion in Lemma 6.7 is false under symmetric sampling. I recommend major revision rather than rejection because the gaps appear repairable, but the authors should be asked to rewrite the proof of Lemma 5.2 and Lemma 6.7 carefully, including a corrected definition of the ideal distance and explicit covariance or independence arguments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this is a real result with a fixable hole in the proof. The authors extend the Borgs–Chayes–Lee–Shah iterative collaborative filtering idea to 3-tensors and show a nearest-neighbor scheme achieves max entrywise error and MSE going to zero at p = n^{-3/2+\\kappa}, matching the SOS and spectral sample complexity. That is genuinely new for a similarity-based method, and the proof machinery—BFS neighborhood growth, martingale concentration, U-statistic bounds—is substantial and mostly careful.\n\nThe good parts first. The algorithm is simple and parallelizable; the main theorem gives max-entrywise guarantees in a regime where previous efficient methods used SOS or spectral ideas. The paper is forthright about the latent-variable model: bounded orthonormal eigenfunctions, constant rank, i.i.d. latent positions, Lipschitz f. It also spells out what is used where and what could plausibly be relaxed.\n\nWhere it gets soft. There is an internal inconsistency in the distance-concentration part. Eq. (5.2) defines the ideal distance with an exponent \\Lambda^{t+1}; Section 6.5, Eq. (6.25), writes it with \\Lambda^{2t}; and the actual concentration lemmas (6.2 and 6.6) push \\tilde N_{u,t} toward \\Lambda^{2t} Q e_u, so the quadratic form in dist concentrates on \\Lambda^{4t+2}, i.e., d_actual = ||\\Lambda^{2t+1}Q(e_u-e_v)||^2. These are not the same object unless |\\lambda_k|=1, which is not assumed. So Lemma 5.2 as written is not established. I think it is repairable: redefine d to be d_actual and adjust bias to |\\lambda_r|^{-2t}\\sqrt{\\eta} and meas to |\\lambda_1|^{-2t}\\sqrt{\\eta'} times the existing constants. Since t = ceil(1/4\\kappa) is constant, all rates in Theorem 4.1 survive. But someone has to actually write out the corrected argument; right now the central proof has a gap.\n\nAlso, the metadata abstract advertises robustness to arbitrary bounded noise and approximate low-rank tensors. That is not proven in the body; the model assumes mean-zero noise with bounded entries and exactly finite spectrum. Either add the proof or tone down the abstract.\n\nOne reader concern I would push back on: the Lemma 6.7 conditional-independence point. Under the symmetric observation model, one observed triplet does create multiple edges, but the rows a in S_{u,t} or S_{v,t} are outside the set S used for the columns, so those extra edges land in columns (a,\\beta) that are not in the S\\times S summation. The independence claim across distinct columns looks defensible to me, though the authors should make that explicit.\n\nBottom line: worth a serious referee. The result is interesting and probably true in substance, but the distance concentration proof needs a corrected statement and constants. Send it to review with the expectation of heavy revision.","headline":"A real nearest-neighbor tensor estimator with near-optimal sample complexity, but the distance-concentration proof has an exponent mismatch that needs fixing before the main theorem can be taken as proven.","tokens_in":35023,"tokens_out":15231,"would_cite":true,"duration_ms":134851,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A similarity-based collaborative filtering rule estimates a 3-order tensor from sparse random entries once each entry is observed with probability $p=\\Omega(n^{-3/2+\\kappa})$, nearly matching the conjectured computational lower bound.","keywords":["tensor estimation","collaborative filtering","sparse observations","low-rank tensor","maximum entry-wise error","sample complexity","nearest neighbor estimator","latent variable model"],"falsifier":"Take a rank-$r$ tensor with random orthonormal factors and no smooth latent representation, run the algorithm at $p=n^{-3/2+\\kappa}$, and check whether the maximum entry-wise error still converges to $0$; the paper's assumptions predict the distance-concentration argument can fail. Concretely, one can measure the empirical distribution of the estimated distances against the ideal latent distances on synthetic data and look for a constant gap when $p=n^{-3/2}$.","tokens_in":33836,"feed_emoji":"🧮","tokens_out":8004,"duration_ms":80199,"temperature":0.7,"pith_summary":"This paper claims that a simple iterative collaborative-filtering rule can estimate a 3-way tensor from very sparse random observations, with every entry error tending to zero. Specifically, it establishes that if each of the $n^3$ possible entries is observed independently with probability $p=\\Omega(n^{-3/2+\\kappa})$ for any arbitrarily small $\\kappa>0$, then the proposed nearest-neighbor estimator achieves mean squared error and maximum entry-wise error decaying to $0$. That sample size nearly matches the conjectured computational lower bound of $\\Omega(n^{3/2})$ for low-rank tensor estimation, and is far below the $O(n^2)$ rate of flattening-based matrix methods. The algorithm works by flattening the tensor into a bipartite graph, expanding neighborhoods with breadth-first search, estimating distances between coordinate indices from thresholded quadratic forms, and finally averaging observed entries from nearby coordinates. The paper also proves a robustness property: bounded observation noise or a bounded-rank approximation error degrades the final error only by a polynomial in that tolerance.","feed_headline":"Neighbor averaging recovers sparse tensors near the n^{3/2} limit","feed_subtitle":"Each entry need be seen with probability only about n^{-3/2}; max per-entry error then shrinks to zero.","key_machinery":"The load-bearing object is a distance estimator built from breadth-first-search trees on a bipartite graph. The tensor is flattened into an $n\\times\\binom{n/2}{2}$ matrix; observed entries become weighted edges between coordinate vertices and pair vertices. For each coordinate $u$, the algorithm grows a BFS tree to depth $2t$ with $t=\\lceil 1/(4\\kappa)\\rceil$, forming neighborhood vectors $N_{u,s}$ over single coordinates and $W_{u,s}$ over coordinate pairs, whose entries are products of edge weights along tree paths. The estimated distance between coordinates $u$ and $v$ is a normalized combination of thresholded quadratic forms $Z_{uv}$ built from fresh observations over pair indices outside both BFS neighborhoods. This quantity concentrates around the ideal distance $d(\\theta_u,\\theta_v)=\\|\\Lambda^{t+1}Q(e_u-e_v)\\|_2^2$. The concentration proof is the heart of the paper: it bounds a martingale difference sequence built from the successive BFS layers, then a U-statistic over the remaining pair indices, obtaining $|d-\\mathrm{dist}|=O(n^{-\\kappa+\\psi})$ with high probability. Once distances are reliable, the final estimate averages fresh observations $(a,b,c)$ whose coordinates are all within threshold $\\eta=\\Theta(n^{-(\\kappa-\\psi)})$ of the target coordinates, a step whose bias-variance tradeoff controls the error rates.","core_discovery":"The central result, Theorem 4.1, assumes the true tensor has the form $F(u,v,w)=\\sum_{k=1}^r \\lambda_k q_k(\\theta_u)q_k(\\theta_v)q_k(\\theta_w)$ with i.i.d. latent variables $\\theta_u\\sim U[0,1]$, bounded orthonormal eigenfunctions $q_k$, constant rank $r=\\Theta(1)$, and an $L$-Lipschitz function $f$. Given independent Bernoulli observations with probability $p=n^{-3/2+\\kappa}$, $\\kappa\\in(0,1/2)$, and per-entry noise with bounded variance, the algorithm's estimate satisfies MSE $=O(n^{-(\\kappa-\\psi)})$ and $\\|F-\\hat F\\|_{\\max}=O(n^{-(\\kappa-\\psi)/2})$ with probability $1-O(n^4\\exp(-\\Theta(n^{2\\psi})))$, for any $\\psi<\\min(\\kappa,3/8)$. In words, both average and worst-case entry errors vanish whenever sampling density exceeds $n^{-3/2}$ by an arbitrarily small polynomial factor. The proof shows the same threshold is exactly the connectivity threshold of the bipartite graph used to compute coordinate similarities, which the authors identify as the algorithmic reason behind the conjectured $\\Omega(n^{3/2})$ computational lower bound. The robustness statement extends the conclusion to noisy tensors and to tensors that are only within $\\varepsilon$ of finite rank: the final error then converges to $\\mathrm{poly}(\\varepsilon)$.","pith_inferences":["If the connectivity explanation is the real barrier, the same BFS-neighborhood construction should generalize to $d$-order tensors with sample complexity near $n^{d/2}$; the paper only states this as a heuristic, not a theorem.","The theorem's constant rank $r=\\Theta(1)$ and orthonormal bounded eigenfunctions are likely the limiting conditions; testing the algorithm on overcomplete tensors with $r>n$ or on non-orthogonal factor dictionaries would show whether nearest-neighbor distances remain identifiable beyond the paper's model.","A practitioner would need to choose $\\kappa$ and the threshold $\\eta$ from data, but the theory assumes the sampling exponent is known; the paper gives no data-driven selection rule.","The robustness result could be turned into a model-selection tool: comparing estimation error across thresholds $\\eta$ may reveal the effective smoothness scale or rank of the latent function, an extension the authors do not explore."],"forward_implications":["Sample complexity nearly hits the conjectured efficient limit: $\\Omega(n^{3/2+\\kappa})$ observations suffice for consistent estimation, whereas flattening-based matrix methods need on the order of $n^2$ observations.","The guarantee is worst-case over entries, not just average-case: the maximum entry-wise error converges to $0$, so every coordinate of the estimate is reliable.","The estimator is robust: if observations carry noise bounded by $\\varepsilon$, or the tensor is only $\\varepsilon$-close to a finite-rank tensor, the final error degrades by only $\\mathrm{poly}(\\varepsilon)$.","The $n^{3/2}$ threshold has an algorithmic interpretation: it is the density at which the similarity graph becomes connected, giving a concrete reason why computationally efficient methods may not easily go below it.","The algorithm is parallelizable because similarity computations are pairwise, and the authors argue the construction extends to asymmetric tensors whose dimensions are proportional."],"supporting_citations":[{"why":"Supplies the matrix iterative collaborative-filtering method and BFS-neighborhood distance estimator that this paper generalizes to tensors.","marker":"[3]"},{"why":"Provides the latent-variable blind-regression analysis that underlies the nearest-neighbor averaging step and the local-measure argument.","marker":"[19]"},{"why":"Gives the martingale concentration inequality used to prove that the estimated distances concentrate around the ideal distances.","marker":"[29]"},{"why":"Provides the negative-dependence and Hoeffding bounds used in the U-statistic concentration for the quadratic forms over pair indices.","marker":"[14]"},{"why":"Establishes the sum-of-squares tensor completion algorithm and conjectures the $\\Omega(n^{3/2})$ computational sample complexity lower bound that motivates this paper's target.","marker":"[1]"},{"why":"Gives a spectral tensor completion algorithm with $\\Omega(n^{3/2})$ sample complexity, serving as the main computationally efficient baseline for comparison.","marker":"[22]"},{"why":"Shows information-theoretically near-optimal $O(n)$ sample complexity via nuclear norm minimization, defining the computational-statistical gap this paper addresses.","marker":"[30]"}],"fun_headline_variants":["Sparse tensor recovery at n^{3/2} sample limit","Collaborative filtering achieves near-optimal tensor estimation","Neighbor averaging recovers tensors at n^{-3/2} density","Robust tensor estimation hits conjectured lower bound","Max entry error vanishes near n^{3/2} sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee collapses if the tensor is not generated by a smooth latent-variable model of the specified form: the proof needs i.i.d. latent positions and a Lipschitz, finite-spectrum function to ensure that every coordinate has many near neighbors and that the ideal distance is well behaved, so the stated theorem does not cover an arbitrary low-rank tensor.","fun_headline_variants_meta":{"raw":{"variants":["Sparse tensor recovery at n^{3/2} sample limit","Collaborative filtering achieves near-optimal tensor estimation","Neighbor averaging recovers tensors at n^{-3/2} density","Robust tensor estimation hits conjectured lower bound","Max entry error vanishes near n^{3/2} sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000245,"raw_usage":{"total_tokens":1632,"prompt_tokens":1139,"completion_tokens":493,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":755,"completion_tokens_details":{"reasoning_tokens":409}},"tokens_in":755,"tokens_out":493,"duration_ms":4982,"temperature":1.0,"reasoning_tokens":409,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:23:27.967651+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a rank-$r$ tensor with random orthonormal factors and no smooth latent representation, run the algorithm at $p=n^{-3/2+\\kappa}$, and check whether the maximum entry-wise error still converges to $0$; the paper's assumptions predict the distance-concentration argument can fail. Concretely, one can measure the empirical distribution of the estimated distances against the ideal latent distances on synthetic data and look for a constant gap when $p=n^{-3/2}$.","supporting_citations":[{"cited_title":"Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation","cited_arxiv_id":null,"evidence_quote":"Supplies the matrix iterative collaborative-filtering method and BFS-neighborhood distance estimator that this paper generalizes to tensors."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the latent-variable blind-regression analysis that underlies the nearest-neighbor averaging step and the local-measure argument."},{"cited_title":"Hoeffding","cited_arxiv_id":null,"evidence_quote":"Provides the negative-dependence and Hoeffding bounds used in the U-statistic concentration for the quadratic forms over pair indices."},{"cited_title":"Noisy tensor completion via the sum-of-squares hierarchy","cited_arxiv_id":null,"evidence_quote":"Establishes the sum-of-squares tensor completion algorithm and conjectures the $\\Omega(n^{3/2})$ computational sample complexity lower bound that motivates this paper's target."},{"cited_title":"Spectral algorithms for tensor completion","cited_arxiv_id":null,"evidence_quote":"Gives a spectral tensor completion algorithm with $\\Omega(n^{3/2})$ sample complexity, serving as the main computationally efficient baseline for comparison."},{"cited_title":"On tensor completion via nuclear norm minimization","cited_arxiv_id":null,"evidence_quote":"Shows information-theoretically near-optimal $O(n)$ sample complexity via nuclear norm minimization, defining the computational-statistical gap this paper addresses."}],"review_version":1}