
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.

In 1970, Donald Ornstein proved a landmark result in dynamical systems, viz.,
two Bernoulli systems with the same entropy are isomorphic except for a measure
0 set. Keane and Smorodinsky gave a finitary proof of this result. They also
indicated how one can generalize the result to mixing Markov Shifts. We adapt
their construction to show that if two computable mixing Markov systems have
the same entropy, then there is a layerwise computable isomorphism defined on
all MartinLof random points in the system. Since the set of MartinLof random
points forms a measure 1 set, it implies the classical result for such systems.
This result uses several recent developments in computable analysis and
algorithmic randomness. Following the work by Braverman, Nandakumar, and Hoyrup
and Rojas introduced discontinuous functions into the study of algorithmic
randomness. We utilize Hoyrup and Rojas' elegant notion of layerwise computable
functions to produce the test of randomness in our result. Further, we use the
recent result of the effective ShannonMcMillanBreiman theorem, independently
established by Hochman and Hoyrup to prove the properties of our construction.
We show that the result cannot be improved to include all points in the
systems  only trivial computable isomorphisms exist between systems with the
same entropy.

In the online prediction framework, we use generalized entropy of to study
the loss rate of predictors when outcomes are drawn according to stationary
ergodic distributions over the binary alphabet. We show that the notion of
generalized entropy of a regular game \cite{KVV04} is welldefined for
stationary ergodic distributions. In proving this, we obtain new gametheoretic
proofs of some classical information theoretic inequalities. Using Birkhoff's
ergodic theorem and convergence properties of conditional distributions, we
prove that a classical ShannonMcMillanBreiman theorem holds for a restricted
class of regular games, when no computational constraints are imposed on the
prediction strategies.
If a game is mixable, then there is an optimal aggregating strategy which
loses at most an additive constant when compared to any other lower
semicomputable strategy. The loss incurred by this algorithm on an infinite
sequence of outcomes is called its predictive complexity. We use our version of
ShannonMcMillanBreiman theorem to prove that when a restriced regular game
has a predictive complexity, the predictive complexity converges to the
generalized entropy of the game almost everywhere with respect to the
stationary ergodic distribution.