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

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

#### 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$

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

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

#### Problem 1.5.

[Uri Feige] Prove that, when $k \le \sqrt{n}$, the algorithm fails with high probability.
• ### Recovering planted solutions to Random CSPs

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

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