
We consider the $(\ell_p,\ell_r)$Grothendieck problem, which seeks to
maximize the bilinear form $y^T A x$ for an input matrix $A$ over vectors $x,y$
with $\x\_p=\y\_r=1$. The problem is equivalent to computing the $p \to
r^*$ operator norm of $A$. The case $p=r=\infty$ corresponds to the classical
Grothendieck problem. Our main result is an algorithm for arbitrary $p,r \ge 2$
with approximation ratio $(1+\epsilon_0)/(\sinh^{1}(1)\cdot \gamma_{p^*}
\,\gamma_{r^*})$ for some fixed $\epsilon_0 \le 0.00863$. Comparing this with
Krivine's approximation ratio of $(\pi/2)/\sinh^{1}(1)$ for the original
Grothendieck problem, our guarantee is off from the best known hardness factor
of $(\gamma_{p^*} \gamma_{r^*})^{1}$ for the problem by a factor similar to
Krivine's defect.
Our approximation follows by bounding the value of the natural vector
relaxation for the problem which is convex when $p,r \ge 2$. We give a
generalization of random hyperplane rounding and relate the performance of this
rounding to certain hypergeometric functions, which prescribe necessary
transformations to the vector solution before the rounding is applied. Unlike
Krivine's Rounding where the relevant hypergeometric function was $\arcsin$, we
have to study a family of hypergeometric functions. The bulk of our technical
work then involves methods from complex analysis to gain detailed information
about the Taylor series coefficients of the inverses of these hypergeometric
functions, which then dictate our approximation factor.
Our result also implies improved bounds for "factorization through
$\ell_{2}^{\,n}$" of operators from $\ell_{p}^{\,n}$ to $\ell_{q}^{\,m}$ (when
$p\geq 2 \geq q$) such bounds are of significant interest in functional
analysis and our work provides modest supplementary evidence for an intriguing
parallel between factorizability, and constantfactor approximability.

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A
\in R^{m \times n}$, defined as \[ \A\_{p\rightarrow q} ~:=~ \max_{x \,\in\,
R^n \setminus \{0\}} \frac{\Ax\_q}{\x\_p} \] This problem generalizes the
spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$,
$q=1$), and has been widely studied in various regimes. When $p \geq q$, the
problem exhibits a dichotomy: constant factor approximation algorithms are
known if $2 \in [q,p]$, and the problem is hard to approximate within almost
polynomial factors when $2 \notin [q,p]$.
The regime when $p < q$, known as \emph{hypercontractive norms}, is
particularly significant for various applications but much less well
understood. The case with $p = 2$ and $q > 2$ was studied by [Barak et al,
STOC'12] who gave subexponential algorithms for a promise version of the
problem (which captures smallset expansion) and also proved hardness of
approximation results based on the Exponential Time Hypothesis. However, no
NPhardness of approximation is known for these problems for any $p < q$.
We study the hardness of approximating matrix norms in both the above cases
and prove the following results:
 We show that for any $1< p < q < \infty$ with $2 \notin [p,q]$,
$\A\_{p\rightarrow q}$ is hard to approximate within
$2^{O(\log^{1\epsilon}\!n)}$ assuming $NP \not\subseteq
BPTIME(2^{\log^{O(1)}\!n})$. This suggests that, similar to the case of $p \geq
q$, the hypercontractive setting may be qualitatively different when $2$ does
not lie between $p$ and $q$.
 For all $p \geq q$ with $2 \in [q,p]$, we show $\A\_{p\rightarrow q}$ is
hard to approximate within any factor than $1/(\gamma_{p^*} \cdot \gamma_q)$,
where for any $r$, $\gamma_r$ denotes the $r^{th}$ norm of a gaussian, and
$p^*$ is the dual norm of $p$.

We consider the following basic problem: given an $n$variate degree$d$
homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in
\mathbb{R}^n$ that maximizes $f(x)$. Besides its fundamental nature, this
problem arises in diverse contexts ranging from tensor and operator norms to
graph expansion to quantum information theory. The homogeneous degree $2$ case
is efficiently solvable as it corresponds to computing the spectral norm of an
associated matrix, but the higher degree case is NPhard.
We give approximation algorithms for this problem that offer a tradeoff
between the approximation ratio and running time: in $n^{O(q)}$ time, we get an
approximation within factor $O_d((n/q)^{d/21})$ for arbitrary polynomials,
$O_d((n/q)^{d/41/2})$ for polynomials with nonnegative coefficients, and
$O_d(\sqrt{m/q})$ for sparse polynomials with $m$ monomials. The approximation
guarantees are with respect to the optimum of the level$q$ sumofsquares
(SoS) SDP relaxation of the problem. Known polynomial time algorithms for this
problem rely on "decoupling lemmas." Such tools are not capable of offering a
tradeoff like our results as they blow up the number of variables by a factor
equal to the degree. We develop new decoupling tools that are more efficient in
the number of variables at the expense of less structure in the output
polynomials. This enables us to harness the benefits of higher level SoS
relaxations.
We complement our algorithmic results with some polynomially large
integrality gaps, albeit for a slightly weaker (but still very natural)
relaxation. Toward this, we give a method to lift a level$4$ solution matrix
$M$ to a higher level solution, under a mild technical condition on $M$.

We study the approximability of constraint satisfaction problems (CSPs) by
linear programming (LP) relaxations. We show that for every CSP, the
approximation obtained by a basic LP relaxation, is no weaker than the
approximation obtained using relaxations given by $\Omega\left(\frac{\log
n}{\log \log n}\right)$ levels of the SheraliAdams hierarchy on instances of
size $n$.
It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extended
formulation is no stronger than relaxations obtained by a superconstant levels
of the SheraliAdams hierarchy.. Combining this with our result also implies
that any polynomial size LP extended formulation is no stronger than the basic
LP.
Using our techniques, we also simplify and strengthen the result by Khot et
al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a
necessary and sufficient condition under which $\Omega(\log \log n)$ levels of
the SheraliAdams hierarchy cannot achieve an approximation better than a
random assignment. We simplify their proof and strengthen the bound to
$\Omega\left(\frac{\log n}{\log \log n}\right)$ levels.

We give an arithmetic version of the recent proof of the triangle removal
lemma by Fox [Fox11], for the group $\mathbb{F}_2^n$.
A triangle in $\mathbb{F}_2^n$ is a triple $(x,y,z)$ such that $x+y+z = 0$.
The triangle removal lemma for $\mathbb{F}_2^n$ states that for every $\epsilon
> 0$ there is a $\delta > 0$, such that if a subset $A$ of $\mathbb{F}_2^n$
requires the removal of at least $\epsilon \cdot 2^n$ elements to make it
trianglefree, then it must contain at least $\delta \cdot 2^{2n}$ triangles.
This problem was first studied by Green [Gre05] who proved a lower bound on
$\delta$ using an arithmetic regularity lemma. Regularity based lower bounds
for triangle removal in graphs were recently improved by Fox and we give a
direct proof of an analogous improvement for triangle removal in
$\mathbb{F}_2^n$.
The improved lower bound was already known to follow (for triangleremoval in
all groups), using Fox's removal lemma for directed cycles and a reduction by
Kr\'{a}l, Serra and Vena [KSV09] (see [Fox11,CF13]). The purpose of this note
is to provide a direct Fourieranalytic proof for the group $\mathbb{F}_2^n.$

In analogy with the regularity lemma of Szemer\'edi, regularity lemmas for
polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by
Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials \calF =
{P_1,...,P_m} to a new collection \calF' so that the polynomials in \calF' are
"pseudorandom". These lemmas have various applications, such as (special cases)
of ReedMuller testing and worstcase to averagecase reductions for
polynomials. However, the transformation from \calF to \calF' is not
algorithmic for either regularity lemma. We define new notions of regularity
for polynomials, which are analogous to the above, but which allow for an
efficient algorithm to compute the pseudorandom collection \calF'. In
particular, when the field is of high characteristic, in polynomial time, we
can refine \calF into \calF' where every nonzero linear combination of
polynomials in \calF' has desirably small Gowers norm.
Using the algorithmic regularity lemmas, we show that if a polynomial P of
degree d is within (normalized) Hamming distance 11/F \eps of some unknown
polynomial of degree k over a prime field F (for k < d < F), then there is an
efficient algorithm for finding a degreek polynomial Q, which is within
distance 11/F \eta of P, for some \eta depending on \eps. This can be
thought of as decoding the ReedMuller code of order k beyond the list decoding
radius (finding one close codeword), when the received word P itself is a
polynomial of degree d (with k < d < F).
We also obtain an algorithmic version of the worstcase to averagecase
reductions by Kaufman and Lovett. They show that if a polynomial of degree d
can be weakly approximated by a polynomial of lower degree, then it can be
computed exactly using a collection of polynomials of degree at most d1. We
give an efficient (randomized) algorithm to find this collection.

A predicate f:{1,1}^k > {0,1} with \rho(f) = \frac{f^{1}(1)}{2^k} is
called {\it approximation resistant} if given a nearsatisfiable instance of
CSP(f), it is computationally hard to find an assignment that satisfies at
least \rho(f)+\Omega(1) fraction of the constraints.
We present a complete characterization of approximation resistant predicates
under the Unique Games Conjecture. We also present characterizations in the
{\it mixed} linear and semidefinite programming hierarchy and the
SheraliAdams linear programming hierarchy. In the former case, the
characterization coincides with the one based on UGC. Each of the two
characterizations is in terms of existence of a probability measure with
certain symmetry properties on a natural convex polytope associated with the
predicate.

The kfold Cartesian product of a graph G is defined as a graph on ktuples
of vertices, where two tuples are connected if they form an edge in one of the
positions and are equal in the rest. Starting with G as a single edge gives G^k
as a kdimensional hypercube. We study the distributions of edges crossed by a
cut in G^k across the copies of G in different positions. This is a
generalization of the notion of influences for cuts on the hypercube.
We show the analogues of results of Kahn, Kalai, and Linial (KKL Theorem
[KahnKL88]) and that of Friedgut (Friedgut's Junta theorem [Friedgut98]), for
the setting of Cartesian products of arbitrary graphs. Our proofs extend the
arguments of Rossignol [Rossignol06] and of Falik and Samorodnitsky [FalikS07],
to the case of arbitrary Cartesian products. We also extend the work on
studying isoperimetric constants for these graphs [HoudreT96, ChungT98] to the
value of semidefinite relaxations for edgeexpansion. We connect the optimal
values of the relaxations for computing expansion, given by various
semidefinite hierarchies, for G and G^k.

We give new combinatorial proofs of known almostperiodicity results for
sumsets of sets with small doubling in the spirit of Croot and Sisask, whose
almostperiodicity lemma has had farreaching implications in additive
combinatorics. We provide an alternative (and L^pnorm free) point of view,
which allows for proofs to easily be converted to probabilistic algorithms that
decide membership in almostperiodic sumsets of dense subsets of F_2^n.
As an application, we give a new algorithmic version of the quasipolynomial
BogolyubovRuzsa lemma recently proved by Sanders. Together with the results by
the last two authors, this implies an algorithmic version of the quadratic
GoldreichLevin theorem in which the number of terms in the quadratic Fourier
decomposition of a given function is quasipolynomial in the error parameter,
compared with an exponential dependence previously proved by the authors. It
also improves the running time of the algorithm to have quasipolynomial
dependence instead of an exponential one.
We also give an application to the problem of finding large subspaces in
sumsets of dense sets. Green showed that the sumset of a dense subset of F_2^n
contains a large subspace. Using Fourier analytic methods, Sanders proved that
such a subspace must have dimension bounded below by a constant times the
density times n. We provide an alternative (and L^p normfree) proof of a
comparable bound, which is analogous to a recent result of Croot, Laba and
Sisask in the integers.

Decomposition theorems in classical Fourier analysis enable us to express a
bounded function in terms of few linear phases with large Fourier coefficients
plus a part that is pseudorandom with respect to linear phases. The
GoldreichLevin algorithm can be viewed as an algorithmic analogue of such a
decomposition as it gives a way to efficiently find the linear phases
associated with large Fourier coefficients.
In the study of "quadratic Fourier analysis", higherdegree analogues of such
decompositions have been developed in which the pseudorandomness property is
stronger but the structured part correspondingly weaker. For example, it has
previously been shown that it is possible to express a bounded function as a
sum of a few quadratic phases plus a part that is small in the $U^3$ norm,
defined by Gowers for the purpose of counting arithmetic progressions of length
4. We give a polynomial time algorithm for computing such a decomposition.
A key part of the algorithm is a local selfcorrection procedure for
ReedMuller codes of order 2 (over $\F_2^n$) for a function at distance
$1/2\epsilon$ from a codeword. Given a function $f:\F_2^n \to \{1,1\}$ at
fractional Hamming distance $1/2\epsilon$ from a quadratic phase (which is a
codeword of ReedMuller code of order 2), we give an algorithm that runs in
time polynomial in $n$ and finds a codeword at distance at most $1/2\eta$ for
$\eta = \eta(\epsilon)$. This is an algorithmic analogue of Samorodnitsky's
result, which gave a tester for the above problem. To our knowledge, it
represents the first instance of a correction procedure for any class of codes,
beyond the listdecoding radius.
In the process, we give algorithmic versions of results from additive
combinatorics used in Samorodnitsky's proof and a refined version of the
inverse theorem for the Gowers $U^3$ norm over $\F_2^n$.

The subspace approximation problem Subspace($k$,$p$) asks for a
$k$dimensional linear subspace that fits a given set of points optimally,
where the error for fitting is a generalization of the least squares fit and
uses the $\ell_{p}$ norm instead. Most of the previous work on subspace
approximation has focused on small or constant $k$ and $p$, using coresets and
sampling techniques from computational geometry.
In this paper, extending another line of work based on convex relaxation and
rounding, we give a polynomial time algorithm, \emph{for any $k$ and any $p
\geq 2$}, with the approximation guarantee roughly $\gamma_{p} \sqrt{2 
\frac{1}{nk}}$, where $\gamma_{p}$ is the $p$th moment of a standard normal
random variable N(0,1). We show that the convex relaxation we use has an
integrality gap (or "rank gap") of $\gamma_{p} (1  \epsilon)$, for any
constant $\epsilon > 0$. Finally, we show that assuming the Unique Games
Conjecture, the subspace approximation problem is hard to approximate within a
factor better than $\gamma_{p} (1  \epsilon)$, for any constant $\epsilon >
0$.

The SmallSet Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a
natural hardness assumption concerning the problem of approximating the edge
expansion of small sets in graphs. This hardness assumption is closely
connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the
SmallSet Expansion Hypothesis implies the Unique Games Conjecture
(Raghavendra, Steurer, STOC 2010).
Our main result is that the SmallSet Expansion Hypothesis is in fact
equivalent to a variant of the Unique Games Conjecture. More precisely, the
hypothesis is equivalent to the Unique Games Conjecture restricted to instance
with a fairly mild condition on the expansion of small sets. Alongside, we
obtain the first strong hardness of approximation results for the Balanced
Separator and Minimum Linear Arrangement problems. Before, no such hardness was
known for these problems even assuming the Unique Games Conjecture.
These results not only establish the SmallSet Expansion Hypothesis as a
natural unifying hypothesis that implies the Unique Games Conjecture, all its
consequences and, in addition, hardness results for other problems like
Balanced Separator and Minimum Linear Arrangement, but our results also show
that the SmallSet Expansion Hypothesis problem lies at the combinatorial heart
of the Unique Games Conjecture.
The key technical ingredient is a new way of exploiting the structure of the
Unique Games instances obtained from the SmallSet Expansion Hypothesis via
(Raghavendra, Steurer, 2010). This additional structure allows us to modify
standard reductions in a way that essentially destroys their localgadget
nature. Using this modification, we can argue about the expansion in the graphs
produced by the reduction without relying on expansion properties of the
underlying Unique Games instance (which would be impossible for a localgadget
reduction).

In this paper we will be concerned with a class of packing and covering
problems which includes Vertex Cover and Independent Set. Typically, one can
write an LP relaxation and then round the solution. In this paper, we explain
why the simple LPbased rounding algorithm for the \\VC problem is optimal
assuming the UGC. Complementing Raghavendra's result, our result generalizes to
a class of strict, covering/packing type CSPs.

Green, Tao and Ziegler prove ``Dense Model Theorems'' of the following form:
if R is a (possibly very sparse) pseudorandom subset of set X, and D is a dense
subset of R, then D may be modeled by a set M whose density inside X is
approximately the same as the density of D in R. More generally, they show that
a function that is majorized by a pseudorandom measure can be written as a sum
of a bounded function having the same expectation plus a function that is
``indistinguishable from zero.'' This theorem plays a key role in the proof of
the GreenTao Theorem that the primes contain arbitrarily long arithmetic
progressions.
In this note, we present a new proof of the GreenTaoZiegler Dense Model
Theorem, which was discovered independently by ourselves and Gowers. We refer
to our full paper for variants of the result with connections and applications
to computational complexity theory, and to Gowers' paper for applications of
the proof technique to ``decomposition, ``structure,'' and ``transference''
theorems in arithmetic and extremal combinatorics (as well as a broader survey
of such theorems).