202 citations · 1.3k across the 61 of their papers we have counts for
6 papers · 1 filter
Experimental performance of graph neural networks on random instances of max-cut
Weichi Yao, Afonso S. Bandeira, Soledad Villar
This note explores the applicability of unsupervised machine learning techniques towards hard optimization problems on random inputs. In particular we consider Graph Neural Network…
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensio…
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
Dmitriy Kunisky, Afonso S. Bandeira
We show that, if is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares rela…
Subexponential-Time Algorithms for Sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1
We study the computational cost of recovering a unit-norm sparse principal component planted in a random matrix, in either the Wigner or Wishart spiked model (…
Computational Hardness of Certifying Bounds on Constrained PCA Problems
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Given a random symmetric matrix drawn from the Gaussian orthogonal ensemble (GOE), we consider the problem of certifying an upper bound on the maximum…
Sum-of-Squares Optimization and the Sparsity Structure of Equiangular Tight Frames
Afonso S. Bandeira, Dmitriy Kunisky
Equiangular tight frames (ETFs) may be used to construct examples of feasible points for semidefinite programs arising in sum-of-squares (SOS) optimization. We show how generalizin…