Potechin, Aaron

1. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
   2016/04/11 by Barak, Boaz, Hopkins, Samuel B., Kelner, Jonathan +3 · 16 citations
   #Computational Complexity (cs.CC) #F.2.0 #FOS: Computer and information sciences
2. The power of sum-of-squares for detecting hidden structures
   2017/10/13 by Hopkins, Samuel B., Kothari, Pravesh K., Potechin, Aaron +3 · 10 citations
   #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
3. Exact tensor completion with sum-of-squares
   2017/02/21 by Aaron Potechin, David Steurer, Potechin, Aaron +1 · 3 citations
   Computer Science · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel Computing and Optimization Techniques #Polynomial and algebraic computation #Tensor decomposition and applications
4. Sum-of-squares lower bounds for planted clique
   2015/03/22 by Raghu Meka, Aaron Potechin, Meka, Raghu +3 · 2 citations
   Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
5. Proof of Han's Hook Expansion Conjecture
   2008/08/06 by Kevin Carde, Joe Loubert, Carde, Kevin +5 · 2 citations
   Mathematics · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Mathematics and Applications
6. Bounds on monotone switching networks for directed connectivity
   2009/11/03 by Potechin, Aaron · 1 citation
   #Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences
7. A Note on Amortized Branching Program Complexity
   2016/11/21 by Potechin, Aaron · 1 citation
   #Computational Complexity (cs.CC) #FOS: Computer and information sciences
8. Sum of squares lower bounds from symmetry and a good story
   2017/11/30 by Potechin, Aaron · 1 citation
   #Computational Complexity (cs.CC) #FOS: Computer and information sciences
9. On the Approximation Resistance of Balanced Linear Threshold Functions
   2018/07/12 by Potechin, Aaron · 1 citation
   #Computational Complexity (cs.CC) #FOS: Computer and information sciences
10. A Conjecture on Induced Subgraphs of Cayley Graphs
    2020/03/30 by Aaron Potechin, Hing Yin Tsang, Potechin, Aaron +1 · 2 citations
    Computer Science · Engineering · #Advanced Graph Theory Research #graph theory and CDMA systems #Graph Labeling and Dimension Problems
11. Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted\n Affine Planes
    2020/09/03 by Mrinalkanti Ghosh, Ghosh, Mrinalkanti, Fernando Granha Jeronimo +7 · 1 citation
    Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Reliability and Maintenance Optimization
12. Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
    2020/11/09 by Potechin, Aaron, Rajendran, Goutham · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
13. SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
    2021/07/08 by Kurpisz, Adam, Potechin, Aaron, Wirth, Elias Samuel · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
14. Sum-of-Squares Lower Bounds for Sparse Independent Set
    2021/11/17 by Jones, Chris, Potechin, Aaron, Rajendran, Goutham +2 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
15. Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
    2024/09/06 by Huang, Neng, Perkins, Will, Potechin, Aaron · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
16. Near-optimal fitting of ellipsoids to random points
    2022/08/19 by Paxton Turner, Potechin, Aaron, Prayaag Venkat +4 · 1 citation
    Computer Science · Engineering · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Geochemistry and Geologic Mapping #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
17. Separating MAX 2-AND, MAX DI-CUT and MAX CUT
    2022/12/21 by Brakensiek, Joshua, Huang, Neng, Potechin, Aaron +1 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA)
18. On induced subgraphs of H(n,3) with maximum degree 1
    2024/05/23 by Potechin, Aaron, Tsang, Hing Yin · 1 citation
    #Combinatorics (math.CO) #FOS: Mathematics
19. Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
    2024/06/26 by Kothari, Pravesh, Potechin, Aaron, Xu, Jeff · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
20. Sum-of-squares lower bounds for Non-Gaussian Component Analysis
    2024/10/28 by Ilias Diakonikolas, Diakonikolas, Ilias, Sushrut Karmalkar +5 · 1 citation
    Chemistry · Computer Science · Engineering · #03F20 #68Q17 #Blind Source Separation Techniques #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Spectroscopy and Chemometric Analyses