1. Algorithmic Challenges

Bounds on ground state enery in the SherringtonKirkpatrick 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 semidefinite 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 notallequal3SAT (NAE3SAT), 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 NAE3SAT 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 polynomialtime 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 polynomialtime 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 nonneighbors, 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 bruteforcing 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.