• ### Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics(1509.06191)

Dec. 23, 2018 cs.DM
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 half-spaces. 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 hyper-contraction with arguments from additive combinatorics.
• ### Bayesian Decision Making in Groups is Hard(1705.04770)

July 27, 2019 cs.MA, cs.SI, math.ST, stat.TH, cs.CC, cs.LG
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 NP-hard 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 NP-hard. 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 Probability of Intransitivity in Dice and Close Elections(1804.00394)

April 2, 2018 math.PR
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 non-standard 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$.
• ### Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem(1604.05757)

April 19, 2016 math.CO, cs.DM
We study a special kind of bounds (so called forbidden subgraph bounds, cf. Feige, Verbitsky '02) for parallel repetition of multi-prover games. First, we show that forbidden subgraph upper bounds for $r \ge 3$ provers imply the same bounds for the density Hales-Jewett 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 two-prover games with question graphs of treewidth at most two and show that our method cannot give exponential bounds for all two-prover graphs.
• ### Upper Tail Estimates with Combinatorial Proofs(1405.2349)

Jan. 15, 2015 cs.DM
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 black-box construction of a pseudorandom generator from a one-way 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}s-R\'enyi random graph, matching the one given by Janson, Oleszkiewicz and Ruci\'nski (Israel J. Math, 2002).