Samuel Hopkins

PhD Candidate, Cornell University

algorithms, theoretical machine learning, semidefinite programming, sum of squares optimization, convex hierarchies, hardness of approximation

CV (pdf)
Google Scholar

Supported by a Microsoft PhD Fellowship, an NSF Graduate Research Fellowship, and a Cornell University Fellowship.

News:

• In Fall 2018 I will join UC Berkeley as a Miller Postdoctoral Fellow!
• Andrea Montanari, David Steurer, and I are running a workshop on computational thresholds in average-case computation at STOC 2018.

Recent and Upcoming Events

• June 2018: Workshop on computational thresholds in average-case problems
• May 2018: Discrete math seminar, UMass Amherst
• May 2018: Theory seminar at Columbia
• May 2018: Theory seminar at NYU
• April 2018: Limits to Inference in Networks and Noisy Data at Santa Fe Institute
• March 2018: UC Berkeley Theory Lunch
• November 2017: Theory seminar, University of Washington
• November 2017: Banff workshop on approximation algorithms

Publications

2018+

Mixture Models, Robustness, and Sum of Squares Proofs. Samuel B. Hopkins, Jerry Li. STOC 2018. arxiv talk (video)

2017

The power of SoS for detecting hidden structures. Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer. FOCS 2017. arxiv

Efficient Bayesian estimation from few samples: community detection and related problems. Samuel B. Hopkins, David Steurer. FOCS 2017. arxiv video

2016

A nearly tight sum-of-squares lower bound for the planted clique problem. Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin. FOCS 2016, inivted to special issue. arxiv video slides (pdf)

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer. STOC 2016. arxiv slides (pptx)

On the integrality gap of degree-4 sum of squares for planted clique Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Tselil Schramm, Prasad Raghavendra. SODA 2016, invited to special issue. arxiv 1 (Hopkins-Kothari-Potechin version) and arxiv 2 (Raghavendra-Schramm version)

2015

Tensor principal component analysis via sum-of-squares proofs. Samuel B. Hopkins, Jonathan Shi, David Steurer. COLT 2015, 20 minute presentation. arxiv

2013

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret. Chicago Journal of Theoretical Computer Science. eccc

Other Writing and Talks

Clustering and Sum of Squares Proofs. A series of blog posts on the sum of squares method in unsupervised learning, and in particular on clustering in mixture models. December 2017.
pdf with all the posts
part 1 part 2 part 3 part 4 part 5 part 6

Introduction to Pseudocalibration. Joint talk with Aaron Potechin. Fall 2017. youtube

Lecture Notes on SoS Tensor Decomposition Algorithms. From a guest lecture given in Moses Charikar’s special topics course at Stanford. Spring 2017. pdf

Contact

324 Gates Hall
samhop at cs dot cornell dot edu