Loading Web-Font TeX/Math/Italic
| Register
\newcommand{\Cat}{{\rm Cat}} \newcommand{\A}{\mathcal A} \newcommand{\freestar}{ \framebox[7pt]{$\star$} }

1. Algorithmic Challenges

    1. Bounds on ground state enery in the Sherrington-Kirkpatrick model

          Given an n \times n symmetric matrix J whose entries are sampled iid from N(0,1/n), it is known that \max_{x \in \{-1,1\}^n} x^\top J x = 1.57 \pm o_n(1).


      In polynomial time, given J we can certify an upper bound of 2 via a spectral algorithm (refutation). The best known lower bound (search) is given by rounding a semi-definite program, and is also not tight.

      Add remark

      Problem 1.1.

      [Andrea Montanari] Give a polynomial time algorithm to certify better upper or lower bounds on this problem.

        • Random CSP phase transitions for refutation via semidefinite programs

              For some random CSPs, such as k-SAT and k-XOR with k > 2, it is known that semidefinite programs (SDPs) have value 1 (or believe that the instance is satisfiable) far above the satisfiability threshold, when \alpha \gg \alpha_s. However, for some CSPs, such as not-all-equal-3-SAT (NAE-3-SAT), this is not known to be the case.

          Add remark

          Problem 1.2.

          [Ryan O’Donnell] Show that there exists some constant \epsilon > 0 such that, for random NAE-3-SAT with \alpha > \alpha_s + \epsilon, the basic SDP relaxation still has value 1.

            • Algorithms for NAE-k-SAT below \alpha_d


              Add remark

              Problem 1.3.

              [Prasad Tetali] Are there polynomial-time algorithms for NAE-k-SAT for large k when \alpha \le \alpha_d?

                • Bridging the gap for planted NAE-k-SAT solutions

                      Suppose we generate an instance of NAE-k-SAT as follows: we begin with a random assignment x, then sample \alpha n random clauses and add them unless they are inconsistent with x. It is known at large and small densities, that is, if \alpha > \alpha_{u} or if \alpha < \alpha_{\ell}, that there is a polynomial-time algorithm for recovering x.

                  Add remark

                  Problem 1.4.

                  [Ryan O’Donnell] Bridge the gap, by demonstrating an algorithm for \alpha_{\ell} <\alpha < \alpha_u. Better yet, demonstrate a single algorithm which works at any density.

                    • Greedy algorithms for Planted Clique

                          In the planted clique model, we are given a sample from the Erdos Renyi distribution G(n,\frac{1}{2}) in which a clique has been planted on a random subset of k vertices.

                      Consider the following greedy algorithm:

                      While the graph is not a clique, remove the vertex of lowest degree.

                      We say that the algorithm has “succeeded” if at least one of the vertices in the terminal graph is in the planted clique. If k \gg \sqrt{n}, it is known that the algorithm succeeds with high probability.

                      Add remark

                      Problem 1.5.

                      [Uri Feige] Prove that, when k \le \sqrt{n}, the algorithm fails with high probability.

                        • Recovering planted solutions to Random CSPs


                          Add remark

                          Problem 1.6.

                          [Andrea Montanari] Is there any planted random CSP for which there is an algorithm that finds a solution in time n \log^{O(1)} n that is closer to the planted solution (as measured in expected Hamming distance) by at least \epsilon n for a constant \epsilon > 0 than the solution returned by Belief Propagation?

                            • Planted clique with bounded edge queries

                                  G(n,1/2) has a clique of size 2\log n with high probability.

                              There is a simple greedy algorithm which finds a clique of size \log n—choose an arbitrary vertex to include in the clique, throw away all of its non-neighbors, then repeat on the remaining graph.

                              This algorithm only looks at n\log n edges.

                              Add remark

                              Problem 1.7.

                              What is the largest clique we can find if we only look at O(n\log^{O(1)} n) edges, but can use an arbitrary amount of time? (By modifying the greedy algorithm, we can get a clique of size \frac{3}{2}\log n with high probability in time 2^{\sqrt{n}}, by running the greedy algorithm until \sqrt{n} unexamined vertices remain, then brute-forcing over them to find the larges clique).

                              Alternatively, consider the planted version: how large does the planted clique size k need to be in order to find it while looking at no more than m edges?

                                  Cite this as: AimPL: Phase transitions in randomized computational problems, available at http://aimpl.org/phaserandom.