


401394020L
Student Seminar in Mathematics and Data:
Optimization of Random Functions
(Spring 2020, ETHZ)
Afonso S. Bandeira
Meets: Thu 1315 at HG G 3
Office Hours: Posted weekly
Piazza page available here.
Topic choice poll
here.
Contents: This seminar will be about quadratic
optimization over the hypercube, in particular the
problem:
Given A an n*n matrix, find
max_x x^TAx where x is constrained to be an
ndimensional vector taking values 1 or +1.
We will start with approximation algorithm for
deterministic, but structured, matrices A. Then move to
random instances corresponding to inverse problems in
graphs, and end with the state of the art in
understanding this optimization problem for a matrix A
with iid gaussian entries. Not all papers are written in
the context of this optimization problem, but you will
see that all of them are analyzing version of this
problem (with different structure, or distribution, of
A). I think this list of papers tells a story I like
very much, hope you also enjoy it!
Format: The first meeting
will be solely about logistics. In the remaining 12
meetings, each of the 12 students will lead the
discussion on one of the 12 topics described below. Many
of the papers below are not written in the context of
this optimization problem, but you will see that all of
them are analyzing a version of this problem (with
different structure or distribution). Each student
should prepare a presentation of around
4050 minutes, the rest of the time
will be spent with questions and discussion; or
presentations on related topics.
Please sign up for your topic here.
I tried to give a rough estimation of difficulty of
each topic, giving them * for the easier ones, and ***
for the hardest. This is of course a rough estimate (and
difficulty is not very well defined).
If you prefer, feel free to use a pseudonym on the
doodle poll and email me to let me know the pseudonym
belongs to you.
I am here to help: If you have any question, want to
discuss a problem, a question about one of the papers, or
brainstorm about any research idea, just stop by office
hours or email me and we'll schedule a time to meet.
Feedback: Also, if you have any comment or feedback
on the class please let me know, submit a comment to this
google form (or in person, or through email). Having
direct feedback from you is the best way for me to organize
the seminar you like! (keep in mind that I don't know who
sent me the comment or feedback and there is no way for me
to answer, for questions use piazza or email, piazza tends
to receive replies faster).
List of Papers/Topics:
 1 (27.02) * GoemansWilliamson Approximation
of MaxCut: Description of the Semidefinite
Programming Algorithm for Approximating MaxCut proposed
and analyzed here:
M. X. Goemans and D. P. Williamson. Improved
approximation algorithms for maximum cut and
satisfiability problems using semidefine programming.
Journal of the Association for Computing Machinery,
42:1115–1145, 1995. This is also describe in
Section 8.1. of my Lecture
Notes, and in many other places online. (Notice
that this corresponds to the case where A is the
Laplacian of a graph).
 2 (05.03) * Little Grothendieck Inequality:
The goal here is to give an approximation ratio (similar
to the one above) when A is positive semidefinite. A
good place to read this argument, and a discussion about
their connection to a celebrated inequality of
Grothendieck, is
N. Alon and A. Naor. Approximating the cutnorm via
Grothendieck’s inequality. In Proc. of the 36 th ACM
STOC, pages 72–80. ACM Press, 2004. see for
example Section 5.2. here,
or simply follow Problem 1.5 this this
homework set.
 3 (12.03) * NonPSD little Grothendieck
Inequality: In M. Charikar and A. Wirth.
Maximizing Quadratic Programs: Extending
Grothendieck's Inequality. FOCS '04: Proceedings of
the 45th Annual IEEE Symposium on Foundations of
Computer Science, 2004 a (nonconstrant)
approximation ratio is obtained for general A. See, for
example, Theorem 1 here.
 4 (19.03) ** Random Matrix, BBP, and Z2
Synchronization: From here one we will treat
random matrices A and show that the approximation ratios
above are pessimistic when considering certain random
matrices A. The idea is to consider A = vv^T + Gaussian
noise and understand this optimization through random
matrix theory. There are many good references, Sections
2 and 4.1. of this paper
are a good reference (you would have to consider +1/1
rather than unit norm complex numbers as in the paper,
but this only makes things easier. A. Singer.
Angular synchronization by eigenvectors and
semidefinite programming. Appl.
Comput. Harmon. Anal., 30(1):20 – 36, 2011.
For a 1/+1 discussion see Section 2.1. of this paper.
Messagepassing algorithms for synchronization
problems over compact groups. A. Perry, A. S. Wein, A.
S. Bandeira, A. Moitra. Communications on Pure and
Applied Mathematics, 2018.
 5 (26.03) ** Community Detection and the
Stochastic Block Model: Partial Recovery: The Goal
here is to describe the Stochastic Block Model and the
Statistical Physics Predictions for partial recovery. A.
Decelle, F. Krzakala, C. Moore, and L. Zdeborov´a.
Asymptotic analysis of the stochastic block model for
modular networks and its algorithmic applications. Phys.
Rev. E, 84, December 2011. When reading this,
focus on just two communities. See also Section 9.2. and
9.3. of these
Lecture Notes.
 6 (02.04) * Community Detection
and the Stochastic Block Model: Exact Recovery:
Main result of this paper.
Focus only in the threshold, not the algorithms. Exact
Recovery in the Stochastic Block Model. E. Abbe, A. S.
Bandeira, G. Hall. IEEE Transactions on
Information Theory, vol.62, no.1, pp.471487, 2016.
 SEMINARS AFTER
THIS DATE WERE MOVED FORWARD BY A WEEK
 7 (09.04 > 23.04) *
Community Detection and the Stochastic Block Model:
Semidefinite Program (SDP): Main result of this paper.
A. S. Bandeira, Foundations of Computational
Mathematics, Foundations of Computational Mathematics,
2018.
 8 (23.04 > 30.04) **
SherringtonKirkpatrick: Upper bound with Slepian:
From here one we remove the ``planted structure'' and
try to understand the problem with A simply being
gaussian, meaning that there is no ``planted correct
x''. This essentially follows a modified version of
Problem 1.1. in this Homework,
where x in the L2 sphere gets replaced by x taking
values in +1/1. The idea is to study problem (1) in this paper
(see also reference therein). The value is given in (2).
By following the proof outlined in the homework above
you will prove a good upper bound on this. A Tight
Degree 4 SumofSquares Lower Bound for the
SherringtonKirkpatrick Hamiltonian. D. Kunisky and A.
S. Bandeira
 9 (30.04 > 07.05) **
SherringtonKirkpatrick: True Value and Spectral
algorithm: The goal here is to give an algorithm
that produces a good answer. Start with a short
description of how the true value is obtained (the value
described in (2) of the paper
mentioned above). A simple spectral algorithm is
described in Example 1.1. namely (equations (5) and (6))
of this
paper (look also at references therein). Computational
Hardness of Certifying Bounds on Constrained PCA
Problems. A. S. Bandeira, D. Kunisky, A. S. Wein.
Innovations in Theoretical Computer Science (ITCS20),
2020.
 10 (07.05 > 14.05) *
SherringtonKirkpatrick: SDP bound: The idea here
is to give an upper bound based on semidefinite
programming, this is done in this paper.
Andrea Montanari and Subhabrata Sen. Semidefinite
programs on sparse random graphs and their application
to community detection. In Proceedings of the
fortyeighth annual ACM symposium on Theory of
Computing, pages 814–827. ACM, 2016. A description
is also available in Theorem 1.8. in this paper.
A Tight Degree 4 SumofSquares Lower Bound for the
SherringtonKirkpatrick Hamiltonian. D. Kunisky and A.
S. Bandeira
 11 (14.05 > 28.05) ** SherringtonKirkpatrick:
Computational Hardness of Upper Bound: Main result
of this
paper. Computational Hardness of Certifying
Bounds on Constrained PCA Problems. A. S. Bandeira, D.
Kunisky, A. S. Wein. Innovations in Theoretical
Computer Science (ITCS20), 2020.
 12 (28.05) *** SherringtonKirkpatrick:
``Optimal'' algorithm: Main result in this paper.
Optimization of the SherringtonKirkpatrick
Hamiltonian. Andrea Montanari.
