| 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.