Fetching the paper…
Reading the bibliography…
Suppose we are given an $n$-dimensional order-3 symmetric tensor $T \in (\mathbb{R}^n)^{\otimes 3}$ that is the sum of $r$ random rank-1 terms.
Difference equations, isoperimetric inequality and transience of certain random walks
Jozef Dodziuk · 1984
Earlier work this paper cites.
λ 1 \lambda_{1} , isoperimetric inequalities for graphs, and superconcentrators
Noga Alon and Vitali D Milman · 1985
Earlier work this paper cites.
Tensor rank is NP-complete
Johan Håstad · 1989
Earlier work this paper cites.
Large cliques elude the metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
A decomposition for three-way arrays
Sue E Leurgans, Robert T Ross, and Rebecca B Abel · 1993
Earlier work this paper cites.
Random graphs
Béla Bollobás · 1998
Earlier work this paper cites.
Learning nonsingular phylogenies and hidden markov models
Elchanan Mossel and Sébastien Roch · 2005
Earlier work this paper cites.
Expander graphs and their applications
Shlomo Hoory, Nathan Linial, and Avi Wigderson · 2006
Earlier work this paper cites.
Fourth-order cumulant-based blind identification of underdetermined mixtures
Lieven De Lathauwer, Josphine Castaing, and Jean-Franois Cardoso · 2007
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
A proof of Alon’s second eigenvalue conjecture and related problems
Joel Friedman · 2008
Earlier work this paper cites.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 2011
Earlier work this paper cites.
A spectral algorithm for latent dirichlet allocation
Anima Anandkumar, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Yi-Kai Liu · 2012
Earlier work this paper cites.
A tensor spectral approach to learning mixed membership community models
Animashree Anandkumar, Rong Ge, Daniel Hsu, and Sham Kakade · 2013
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
Earlier work this paper cites.
Learning mixtures of spherical gaussians: moment methods and spectral decompositions
Daniel Hsu and Sham M Kakade · 2013
Earlier work this paper cites.
Most tensor problems are NP-hard
Christopher J Hillar and Lek-Heng Lim · 2013
Earlier work this paper cites.
The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures
Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James Voss · 2014
Earlier work this paper cites.
Analyzing tensor power method dynamics: Applications to learning overcomplete latent variable models
Anima Anandkumar, Rong Ge, and Majid Janzamin · 2014
Earlier work this paper cites.
Smoothed analysis of tensor decompositions
Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan · 2014
Earlier work this paper cites.
Refined methods for the identifiability of tensors
Cristiano Bocci, Luca Chiantini, and Giorgio Ottaviani · 2014
Earlier work this paper cites.
Fourier PCA and robust tensor decomposition
Navin Goyal, Santosh Vempala, and Ying Xiao · 2014
Earlier work this paper cites.
Algorithmic aspects of machine learning
Ankur Moitra · 2014
Earlier work this paper cites.
A statistical model for tensor PCA
Emile Richard and Andrea Montanari · 2014
Earlier work this paper cites.
Learning overcomplete latent variable models through tensor methods
Animashree Anandkumar, Rong Ge, and Majid Janzamin · 2015
Earlier work this paper cites.
Dictionary learning and tensor decomposition via the sum-of-squares method
Boaz Barak, Jonathan A Kelner, and David Steurer · 2015
Earlier work this paper cites.
Learning mixtures of gaussians in high dimensions
Rong Ge, Qingqing Huang, and Sham M Kakade · 2015
Earlier work this paper cites.
Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
Rong Ge and Tengyu Ma · 2015
Earlier work this paper cites.
Tensor principal component analysis via sum-of-square proofs
Samuel B Hopkins, Jonathan Shi, and David Steurer · 2015
Earlier work this paper cites.
Computational lower bounds for community detection on random graphs
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2015
Earlier work this paper cites.
MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová · 2015
Earlier work this paper cites.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer · 2016
Earlier work this paper cites.
Polynomial-time tensor decompositions with sum-of-squares
Tengyu Ma, Jonathan Shi, and David Steurer · 2016
Earlier work this paper cites.
A tensor based framework for community detection in dynamic networks
Esraa Al-Sharoa, Mahmood Al-Khassaweneh, and Selin Aviyente · 2017
Cited alongside, same era.
Estimation under group actions: recovering orbits from invariants
Afonso S Bandeira, Ben Blum-Smith, Joe Kileel, Amelia Perry, Jonathan Weed, and Alexander S Wein · 2017
Cited alongside, same era.
Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart · 2017
Cited alongside, same era.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao · 2017
Cited alongside, same era.
On the optimization landscape of tensor decompositions
Rong Ge and Tengyu Ma · 2017
Cited alongside, same era.
Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
Zhou Fan, Yi Sun, Tianhao Wang, and Yihong Wu · 2020
Later among the works it cites.
Low-degree hardness of random optimization problems
David Gamarnik, Aukosh Jagannath, and Alexander S Wein · 2020
Later among the works it cites.
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
Bohdan Kivva and Aaron Potechin · 2020
Later among the works it cites.
Machinery for proving sum-of-squares lower bounds on certification problems
Aaron Potechin and Goutham Rajendran · 2020
Later among the works it cites.
Statistical query algorithms and low degree tests are almost equivalent
Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, and Tselil Schramm · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2017
Cited alongside, same era.
Sparse high-dimensional linear regression. algorithmic barriers and a local search algorithm
David Gamarnik and Ilias Zadik · 2017
Cited alongside, same era.
The power of sum-of-squares for detecting hidden structures
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer · 2017
Cited alongside, same era.
Efficient bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Cited alongside, same era.
Sum of squares lower bounds for refuting any CSP
Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Cited alongside, same era.
Introduction to tensor decompositions and their applications in machine learning
Stephan Rabanser, Oleksandr Shchur, and Stephan Günnemann · 2017
Cited alongside, same era.
Tensor decomposition for signal processing and machine learning
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E Papalexakis, and Christos Faloutsos · 2017
Cited alongside, same era.
Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs
Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alexander S Wein · 2021
Later among the works it cites.
Local statistics, semidefinite programming, and community detection
Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra · 2021
Later among the works it cites.
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik · 2021
Later among the works it cites.
The overlap gap property in principal submatrix recovery
David Gamarnik, Aukosh Jagannath, and Subhabrata Sen · 2021
Later among the works it cites.
Counterexamples to the low-degree conjecture
Justin Holmgren and Alexander S Wein · 2021
Later among the works it cites.
Community detection on mixture multilayer networks via regularized tensor decomposition
Bing-Yi Jing, Ting Li, Zhongyuan Lyu, and Dong Xia · 2021
Later among the works it cites.
Reconstruction on trees and low-degree polynomials
Frederic Koehler and Elchanan Mossel · 2021
Later among the works it cites.
A stress-free sum-of-squares lower bound for coloring
Pravesh K Kothari and Peter Manohar · 2021
Later among the works it cites.
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Dmitriy Kunisky · 2021
Later among the works it cites.
Algorithms from invariants: Smoothed analysis of orbit recovery over S O ( 3 ) SO(3)
Allen Liu and Ankur Moitra · 2021
Later among the works it cites.
Statistical problems with planted structures: Information-theoretical and computational limits
Yihong Wu and Jiaming Xu · 2021
Later among the works it cites.
The Franz-Parisi criterion and computational trade-offs in high dimensional statistics
Afonso S Bandeira, Ahmed El Alaoui, Samuel B Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik · 2022
Closest in time.
The algorithmic phase transition of random k-SAT for low degree polynomials
Guy Bresler and Brice Huang · 2022
Closest in time.
Statistical and computational phase transitions in group testing
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik · 2022
Closest in time.
Almost-linear planted cliques elude the metropolis process
Zongchen Chen, Elchanan Mossel, and Ilias Zadik · 2022
Closest in time.
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d’Orsi, Chih-Hung Liu, David Steurer, and Stefan Tiegel · 2022
Closest in time.
Non-gaussian component analysis via lattice basis reduction
Ilias Diakonikolas and Daniel Kane · 2022
Closest in time.
Disordered systems insights on computational hardness
David Gamarnik, Cristopher Moore, and Lenka Zdeborová · 2022
Closest in time.
Will the real Jennrich’s algorithm please stand up?
Tamara G. Kolda · 2022
Closest in time.
Lecture notes on sum-of-squares optimization
Dmitriy Kunisky · 2022
Closest in time.
Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2022
Closest in time.
Tensor clustering with planted structures: Statistical optimality and computational limits
Yuetian Luo and Anru R Zhang · 2022
Closest in time.
Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation
Andrea Montanari and Alexander S Wein · 2022
Closest in time.
Random tensor theory for tensor decomposition
Mohamed Ouerfelli, Mohamed Tamaazousti, and Vincent Rivasseau · 2022
Closest in time.
Computational barriers to estimation from low-degree polynomials
Tselil Schramm and Alexander S Wein · 2022
Closest in time.
Optimal low-degree hardness of maximum independent set
Alexander S Wein · 2022
Closest in time.
Lattice-based methods surpass sum-of-squares in clustering
Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna · 2022
Closest in time.