
There is a common theme to some research questions in additive combinatorics
and noise stability. Both study the following basic question: Let $\mathcal{P}$
be a probability distribution over a space $\Omega^\ell$ with all $\ell$
marginals equal. Let $\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}$
where $\underline{X}^{(j)} = (X_1^{(j)}, \ldots, X_n^{(j)})$ be random vectors
such that for every coordinate $i \in [n]$ the tuples $(X_i^{(1)}, \ldots,
X_i^{(\ell)})$ are i.i.d. according to $\mathcal{P}$.
A central question that is addressed in both areas is:
 Does there exist a function $c_{\mathcal{P}}()$ independent of $n$ such
that for every $f: \Omega^n \to [0, 1]$ with $\mathrm{E}[f(X^{(1)})] = \mu >
0$: \begin{align*} \mathrm{E} \left[ \prod_{j=1}^\ell f(X^{(j)}) \right]
\ge c(\mu) > 0 \, ? \end{align*}
Instances of this question include the finite field model version of Roth's
and Szemer\'edi's theorems as well as Borell's result about the optimality of
noise stability of halfspaces.
Our goal in this paper is to interpolate between the noise stability theory
and the finite field additive combinatorics theory and address the question
above in further generality than considered before. In particular, we settle
the question for $\ell = 2$ and when $\ell > 2$ and $\mathcal{P}$ has bounded
correlation $\rho(\mathcal{P}) < 1$. Under the same conditions we also
characterize the _obstructions_ for similar lower bounds in the case of $\ell$
different functions. Part of the novelty in our proof is the combination of
analytic arguments from the theories of influences and hypercontraction with
arguments from additive combinatorics.

We study the computations that Bayesian agents undertake when exchanging
opinions over a network. The agents act repeatedly on their private information
and take myopic actions that maximize their expected utility according to a
fully rational posterior belief. We show that such computations are NPhard for
two natural utility functions: one with binary actions, and another where
agents reveal their posterior beliefs. In fact, we show that distinguishing
between posteriors that are concentrated on different states of the world is
NPhard. Therefore, even approximating the Bayesian posterior beliefs is hard.
We also describe a natural search algorithm to compute agents' actions, which
we call elimination of impossible signals, and show that if the network is
transitive, the algorithm can be modified to run in polynomial time.

The phenomenon of intransitivity in elections, where the pairwise orderings
of three or more candidates induced by voter preference is not transitive, was
first observed by Condorcet in the 18th century, and is fundamental to modern
social choice theory. There has been some recent interest in understanding
intransitivity for three or more $n$sided dice (with nonstandard labelings),
where now the pairwise ordering is induced by the probability, relative to
$1/2$, that a throw from one dice is higher than the other. Conrey, Gabbard,
Grant, Liu and Morrison studied, via simulation, the probability of
intransitivity for a number of random dice models. Their findings led to a
Polymath project studying three i.i.d. random dice with i.i.d. faces drawn from
the uniform distribution on $\{1,\ldots,n\}$, and conditioned on the average of
faces equal to $(n+1)/2$. The Polymath project proved that the probability that
three such dice are intransitive is asymptotically $1/4$. The analogous
probability in the Condorcet voting model is known to be different than $1/4$
(it is approximately equal to $0.0877$).
We present some results concerning intransitive dice and Condorcet paradox.
Among others, we show that if we replace the uniform dice faces by Gaussian
faces, i.e., faces drawn from the standard normal distribution conditioned on
the average of faces equal to zero, then three dice are transitive with high
probability, in contrast to the behavior of the uniform model.
We also define a notion of almost tied elections in the standard social
choice voting model and show that the probability of Condorcet paradox for
those elections approaches $1/4$.

We study a special kind of bounds (so called forbidden subgraph bounds, cf.
Feige, Verbitsky '02) for parallel repetition of multiprover games.
First, we show that forbidden subgraph upper bounds for $r \ge 3$ provers
imply the same bounds for the density HalesJewett theorem for alphabet of size
$r$. As a consequence, this yields a new family of games with slow decrease in
the parallel repetition value.
Second, we introduce a new technique for proving exponential forbidden
subgraph upper bounds and explore its power and limitations. In particular, we
obtain exponential upper bounds for twoprover games with question graphs of
treewidth at most two and show that our method cannot give exponential bounds
for all twoprover graphs.

We study generalisations of a simple, combinatorial proof of a Chernoff bound
similar to the one by Impagliazzo and Kabanets (RANDOM, 2010).
In particular, we prove a randomized version of the hitting property of
expander random walks and apply it to obtain a concentration bound for expander
random walks which is essentially optimal for small deviations and a large
number of steps. At the same time, we present a simpler proof that still yields
a "right" bound settling a question asked by Impagliazzo and Kabanets.
Next, we obtain a simple upper tail bound for polynomials with input
variables in $[0, 1]$ which are not necessarily independent, but obey a certain
condition inspired by Impagliazzo and Kabanets. The resulting bound is used by
Holenstein and Sinha (FOCS, 2012) in the proof of a lower bound for the number
of calls in a blackbox construction of a pseudorandom generator from a oneway
function.
We then show that the same technique yields the upper tail bound for the
number of copies of a fixed graph in an Erd\H{o}sR\'enyi random graph,
matching the one given by Janson, Oleszkiewicz and Ruci\'nski (Israel J. Math,
2002).