
Consider an expander graph in which a $\mu$ fraction of the vertices are
marked. A random walk starts at a uniform vertex and at each step continues to
a random neighbor. Gillman showed in 1993 that the number of marked vertices
seen in a random walk of length $n$ is concentrated around its expectation,
$\Phi := \mu n$, independent of the size of the graph. Here we provide a new
and sharp tail bound, improving on the existing bounds whenever $\mu$ is not
too large.

We prove hypergraph variants of the celebrated AlonRoichman theorem on
spectral expansion of sparse random Cayley graphs. One of these variants
implies that for every prime $p\geq 3$ and any $\varepsilon > 0$, there exists
a set of directions $D\subseteq \mathbb{F}_p^n$ of size
$O_{p,\varepsilon}(p^{(11/p +o(1))n})$ such that for every set $A\subseteq
\mathbb{F}_p^n$ of density $\alpha$, the fraction of lines in $A$ with
direction in $D$ is within $\varepsilon\alpha$ of the fraction of all lines in
$A$. Our proof uses new deviation bounds for sums of independent random
multilinear forms taking values in a generalization of the Birkhoff polytope.
The proof of our deviation bound is based on Dudley's integral inequality and a
probabilistic construction of $\varepsilon$nets. Using the polynomial method
we prove that a Cayley hypergraph with edges generated by a set~$D$ as above
requires $D \geq \Omega_p(n^{p1})$ for (our notion of) spectral expansion
for hypergraphs.

Two classes of distributions that are widely used in the analysis of Bayesian
auctions are the Monotone Hazard Rate (MHR) and Regular distributions. They can
both be characterized in terms of the rate of change of the associated virtual
value functions: for MHR distributions the condition is that for values $v <
v'$, $\phi(v')  \phi(v) \ge v'  v$, and for regular distributions, $\phi(v')
 \phi(v) \ge 0$. Cole and Roughgarden introduced the interpolating class of
$\alpha$Strongly Regular distributions ($\alpha$SR distributions for short),
for which $\phi(v')  \phi(v) \ge \alpha(v'  v)$, for $0 \le \alpha \le 1$.
In this paper, we investigate five distinct auction settings for which good
expected revenue bounds are known when the bidders' valuations are given by MHR
distributions. In every case, we show that these bounds degrade gracefully when
extended to $\alpha$SR distributions. For four of these settings, the auction
mechanism requires knowledge of these distribution(s) (in the other setting,
the distributions are needed only to ensure good bounds on the expected
revenue). In these cases we also investigate what happens when the
distributions are known only approximately via samples, specifically how to
modify the mechanisms so that they remain effective and how the expected
revenue depends on the number of samples.

For two functions $f,g:\{0,1\}^n\to\{0,1\}$ a mapping
$\psi:\{0,1\}^n\to\{0,1\}^n$ is said to be a $\textit{mapping from $f$ to $g$}$
if it is a bijection and $f(z)=g(\psi(z))$ for every $z\in\{0,1\}^n$. In this
paper we study Lipschitz mappings between boolean functions.
Our first result gives a construction of a $C$Lipschitz mapping from the
${\sf Majority}$ function to the ${\sf Dictator}$ function for some universal
constant $C$. On the other hand, there is no $n/2$Lipschitz mapping in the
other direction, namely from the ${\sf Dictator}$ function to the ${\sf
Majority}$ function. This answers an open problem posed by Daniel Varga in the
paper of Benjamini et al. (FOCS 2014).
We also show a mapping from ${\sf Dictator}$ to ${\sf XOR}$ that is 3local,
2Lipschitz, and its inverse is $O(\log(n))$Lipschitz, where by $L$local
mapping we mean that each of its output bits depends on at most $L$ input bits.
Next, we consider the problem of finding functions such that any mapping
between them must have large \emph{average stretch}, where the average stretch
of a mapping $\phi$ is defined as ${\sf avgStretch}(\phi) = {\mathbb
E}_{x,i}[dist(\phi(x),\phi(x+e_i)]$. We show that any mapping $\phi$ from ${\sf
XOR}$ to ${\sf Majority}$ must satisfy ${\sf avgStretch}(\phi) \geq
\Omega(\sqrt{n})$. In some sense, this gives a "function analogue" to the
question of Benjamini et al. (FOCS 2014), who asked whether there exists a set
$A \subset \{0,1\}^n$ of density 0.5 such that any bijection from
$\{0,1\}^{n1}$ to $A$ has large average stretch.
Finally, we show that for a random balanced function
$f:\{0,1\}^n\to\{0,1\}^n$ with high probability there is a mapping $\phi$ from
${\sf Dictator}$ to $f$ such that both $\phi$ and $\phi^{1}$ have constant
average stretch. In particular, this implies that one cannot obtain lower
bounds on average stretch by taking uniformly random functions.

The hitting time, h_uv, of a random walk on a finite graph G, is the expected
time for the walk to reach vertex v given that it started at vertex u. We
present two methods of calculating the hitting time between vertices of finite
graphs, along with applications to specific classes of graphs, including grids,
trees, and the 'tadpole' graphs.