Alexander S. Wein

74 papers A* 19A 5Journal 49Unranked 1

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Computational Complexity of Statistics: New Insights from Low-Degree Polynomials. CoRR Alexander S. Wein
2025	J	`jnl`	Improving the Threshold for Finding Rank-1 Matrices in a Subspace. CoRR Jeshu Dastidar, Tait Weicht, Alexander S. Wein
2025	J	`jnl`	Information-Theoretic Thresholds for Planted Dense Cycles. IEEE Trans. Inf. Theory Cheng Mao, Alexander S. Wein, Shenduo Zhang
2025	A*	`conf`	Overcomplete Tensor Decomposition via Koszul-Young Flattenings. FOCS Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
2025	A*	`conf`	Sharp Phase Transitions in Estimation with Low-Degree Polynomials. STOC Youngtak Sohn, Alexander S. Wein
2025	J	`jnl`	Sharp Phase Transitions in Estimation with Low-Degree Polynomials. CoRR Youngtak Sohn, Alexander S. Wein
2025	A*	`conf`	Statistical Inference of a Ranked Community in a Directed Graph. STOC Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu
2025	A*	`conf`	Stochastic block models with many communities and the Kesten-Stigum bound - extended abstract. COLT Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein
2025	J	`jnl`	Stochastic block models with many communities and the Kesten-Stigum bound. CoRR Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein
2025	J	`jnl`	The Kikuchi Hierarchy and Tensor PCA. J. ACM Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
2025	A	`conf`	Time Lower Bounds for the Metropolis Process and Simulated Annealing. APPROX/RANDOM Zongchen Chen, Dan Mikulincer, Daniel Reichman, Alexander S. Wein
2024	J	`jnl`	Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics. SIAM J. Comput. David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2024	J	`jnl`	Information-Theoretic Thresholds for Planted Dense Cycles. CoRR Cheng Mao, Alexander S. Wein, Shenduo Zhang
2024	A*	`conf`	Low-degree phase transitions for detecting a planted clique in sublinear time. COLT Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
2024	J	`jnl`	Low-degree phase transitions for detecting a planted clique in sublinear time. CoRR Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
2024	J	`jnl`	Overcomplete Tensor Decomposition via Koszul-Young Flattenings. CoRR Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
2024	J	`jnl`	Statistical inference of a ranked community in a directed graph. CoRR Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu
2024	J	`jnl`	Subexponential-Time Algorithms for Sparse PCA. Found. Comput. Math. Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
2024	A*	`conf`	Tensor Cumulants for Statistical Inference on Invariant Distributions. FOCS Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
2024	J	`jnl`	Tensor cumulants for statistical inference on invariant distributions. CoRR Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
2023	A*	`conf`	Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials. STOC Alexander S. Wein
2023	J	`jnl`	Detection of Dense Subhypergraphs by Low-Degree Polynomials. CoRR Abhishek Dhawan, Cheng Mao, Alexander S. Wein
2023	A*	`conf`	Detection-Recovery Gap for Planted Dense Cycles. COLT Cheng Mao, Alexander S. Wein, Shenduo Zhang
2023	J	`jnl`	Detection-Recovery Gap for Planted Dense Cycles. CoRR Cheng Mao, Alexander S. Wein, Shenduo Zhang
2023	A	`conf`	Is It Easier to Count Communities Than Find Them? ITCS Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang
2023	A*	`conf`	Is Planted Coloring Easier than Planted Clique? COLT Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
2023	J	`jnl`	Is Planted Coloring Easier than Planted Clique? CoRR Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
2023	A*	`conf`	Near-optimal fitting of ellipsoids to random points. COLT Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein
2023	J	`jnl`	Time Lower Bounds for the Metropolis Process and Simulated Annealing. CoRR Zongchen Chen, Dan Mikulincer, Daniel Reichman, Alexander S. Wein
2022	J	`jnl`	Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials. CoRR Alexander S. Wein
2022	J	`jnl`	Is it easier to count communities than find them? CoRR Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang
2022	A*	`conf`	Lattice-Based Methods Surpass Sum-of-Squares in Clustering. COLT Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna
2022	A*	`conf`	Statistical and Computational Phase Transitions in Group Testing. COLT Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S. Wein, Ilias Zadik
2022	J	`jnl`	Statistical and Computational Phase Transitions in Group Testing. CoRR Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S. Wein, Ilias Zadik
2022	A*	`conf`	The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics. NeurIPS Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
2022	J	`jnl`	The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics. CoRR Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik
2021	—	`conf`	Average-Case Integrality Gap for Non-Negative Principal Component Analysis. MSML Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
2021	J	`jnl`	Circuit Lower Bounds for the p-Spin Optimization Problem. CoRR David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2021	A	`conf`	Counterexamples to the Low-Degree Conjecture. ITCS Justin Holmgren, Alexander S. Wein
2021	J	`jnl`	Lattice-Based Methods Surpass Sum-of-Squares in Clustering. CoRR Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna
2021	J	`jnl`	Optimal Spectral Recovery of a Planted Vector in a Subspace. CoRR Cheng Mao, Alexander S. Wein
2021	A*	`conf`	Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs. COLT Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
2021	J	`jnl`	The Average-Case Time Complexity of Certifying the Restricted Isometry Property. IEEE Trans. Inf. Theory Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
2020	J	`jnl`	Average-Case Integrality Gap for Non-Negative Principal Component Analysis. CoRR Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
2020	J	`jnl`	Computational Barriers to Estimation from Low-Degree Polynomials. CoRR Tselil Schramm, Alexander S. Wein
2020	A	`conf`	Computational Hardness of Certifying Bounds on Constrained PCA Problems. ITCS Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
2020	J	`jnl`	Computationally efficient sparse clustering. CoRR Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
2020	J	`jnl`	Counterexamples to the Low-Degree Conjecture. CoRR Justin Holmgren, Alexander S. Wein
2020	A*	`conf`	Free Energy Wells and Overlap Gap Property in Sparse PCA. COLT Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
2020	J	`jnl`	Free Energy Wells and Overlap Gap Property in Sparse PCA. CoRR Gérard Ben Arous, Alexander S. Wein, Ilias Zadik
2020	A*	`conf`	Low-Degree Hardness of Random Optimization Problems. FOCS David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2020	J	`jnl`	Low-Degree Hardness of Random Optimization Problems. CoRR David Gamarnik, Aukosh Jagannath, Alexander S. Wein
2020	J	`jnl`	Optimal Low-Degree Hardness of Maximum Independent Set. CoRR Alexander S. Wein
2020	J	`jnl`	Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs. CoRR Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein
2020	J	`jnl`	The Average-Case Time Complexity of Certifying the Restricted Isometry Property. CoRR Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
2019	J	`jnl`	Computational Hardness of Certifying Bounds on Constrained PCA Problems. CoRR Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
2019	J	`jnl`	Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio. CoRR Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
2019	A	`conf`	Overcomplete Independent Component Analysis via SDP. AISTATS Anastasia Podosinnikova, Amelia Perry, Alexander S. Wein, Francis R. Bach, Alexandre d'Aspremont, David A. Sontag
2019	J	`jnl`	Overcomplete Independent Component Analysis via SDP. CoRR Anastasia Podosinnikova, Amelia Perry, Alexander S. Wein, Francis R. Bach, Alexandre d'Aspremont, David A. Sontag
2019	J	`jnl`	Spectral Methods from Tensor Networks. SIAM J. Comput. Ankur Moitra, Alexander S. Wein
2019	A*	`conf`	Spectral methods from tensor networks. STOC Ankur Moitra, Alexander S. Wein
2019	J	`jnl`	Subexponential-Time Algorithms for Sparse PCA. CoRR Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
2019	A*	`conf`	The Kikuchi Hierarchy and Tensor PCA. FOCS Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
2019	J	`jnl`	The Kikuchi Hierarchy and Tensor PCA. CoRR Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
2018	J	`jnl`	Notes on computational-to-statistical gaps: predictions using statistical physics. CoRR Afonso S. Bandeira, Amelia Perry, Alexander S. Wein
2018	J	`jnl`	Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models. CoRR Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
2018	J	`jnl`	Spectral Methods from Tensor Networks. CoRR Ankur Moitra, Alexander S. Wein
2017	J	`jnl`	Estimation under group actions: recovering orbits from invariants. CoRR Afonso S. Bandeira, Ben Blum-Smith, Amelia Perry, Jonathan Weed, Alexander S. Wein
2016	A*	`conf`	How robust are reconstruction thresholds for community detection? STOC Ankur Moitra, William Perry, Alexander S. Wein
2016	J	`jnl`	Message-passing algorithms for synchronization problems over compact groups. CoRR Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
2016	J	`jnl`	Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization. CoRR Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
2016	J	`jnl`	Statistical limits of spiked tensor models. CoRR Amelia Perry, Alexander S. Wein, Afonso S. Bandeira
2015	J	`jnl`	A semidefinite program for unbalanced multisection in the stochastic block model. CoRR William Perry, Alexander S. Wein
2015	J	`jnl`	How Robust are Reconstruction Thresholds for Community Detection? CoRR Ankur Moitra, William Perry, Alexander S. Wein