
String matching is the problem of deciding whether a given $n$bit string
contains a given $k$bit pattern. We study the complexity of this problem in
three settings.
Communication complexity. For small $k$, we provide nearoptimal upper and
lower bounds on the communication complexity of string matching. For large $k$,
our bounds leave open an exponential gap; we exhibit some evidence for the
existence of a better protocol.
Circuit complexity. We present several upper and lower bounds on the size of
circuits with threshold and DeMorgan gates solving the string matching problem.
Similarly to the above, our bounds are nearoptimal for small $k$.
Learning. We consider the problem of learning a hidden pattern of length at
most $k$ relative to the classifier that assigns 1 to every string that
contains the pattern. We prove optimal bounds on the VC dimension and sample
complexity of this problem.

Given an arbitrary graph $G$ we study the chromatic number of a random
subgraph $G_{1/2}$ obtained from $G$ by removing each edge independently with
probability $1/2$. Studying $\chi(G_{1/2})$ has been suggested by
Bukh~\cite{Bukh}, who asked whether $\mathbb{E}[\chi(G_{1/2})] \geq \Omega(
\chi(G)/\log(\chi(G)))$ holds for all graphs $G$. In this paper we show that
for any graph $G$ with chromatic number $k = \chi(G)$ and for all $d \leq
k^{1/3}$ it holds that $\Pr[\chi(G_{1/2}) \leq d] < \exp \left(
\Omega\left(\frac{k(kd^3)}{d^3}\right)\right)$. In particular, $\Pr[G_{1/2}
\text{ is bipartite}] < \exp \left( \Omega \left(k^2 \right)\right)$. The
later bound is tight up to a constant in $\Omega(\cdot)$, and is attained when
$G$ is the complete graph on $k$ vertices.
As a technical lemma, that may be of independent interest, we prove that if
in \emph{any} $d^3$ coloring of the vertices of $G$ there are at least $t$
monochromatic edges, then $\Pr[\chi(G_{1/2}) \leq d] < e^{
\Omega\left(t\right)}$.
We also prove that for any graph $G$ with chromatic number $k = \chi(G)$ and
independence number $\alpha(G) \leq O(n/k)$ it holds that
$\mathbb{E}[\chi(G_{1/2})] \geq \Omega \left( k/\log(k) \right)$. This gives a
positive answer to the question of Bukh for a large family of graphs.

A $(k,\varepsilon)$nonmalleable extractor is a function ${\sf nmExt} :
\{0,1\}^n \times \{0,1\}^d \to \{0,1\}$ that takes two inputs, a weak source $X
\sim \{0,1\}^n$ of minentropy $k$ and an independent uniform seed $s \in
\{0,1\}^d$, and outputs a bit ${\sf nmExt}(X, s)$ that is $\varepsilon$close
to uniform, even given the seed $s$ and the value ${\sf nmExt}(X, s')$ for an
adversarially chosen seed $s' \neq s$. Dodis and Wichs~(STOC 2009) showed the
existence of $(k, \varepsilon)$nonmalleable extractors with seed length $d =
\log(nk1) + 2\log(1/\varepsilon) + 6$ that support sources of entropy $k >
\log(d) + 2 \log(1/\varepsilon) + 8$.
We show that the foregoing bound is essentially tight, by proving that any
$(k,\varepsilon)$nonmalleable extractor must satisfy the entropy bound $k >
\log(d) + 2 \log(1/\varepsilon)  \log\log(1/\varepsilon)  C$ for an absolute
constant $C$. In particular, this implies that nonmalleable extractors require
minentropy at least $\Omega(\log\log(n))$. This is in stark contrast to the
existence of strong seeded extractors that support sources of entropy $k =
O(\log(1/\varepsilon))$.
Our techniques strongly rely on coding theory. In particular, we reveal an
inherent connection between nonmalleable extractors and error correcting
codes, by proving a new lemma which shows that any
$(k,\varepsilon)$nonmalleable extractor with seed length $d$ induces a code
$C \subseteq \{0,1\}^{2^k}$ with relative distance $0.5  2\varepsilon$ and
rate $\frac{d1}{2^k}$.

A key feature of neural network architectures is their ability to support the
simultaneous interaction among large numbers of units in the learning and
processing of representations. However, how the richness of such interactions
trades off against the ability of a network to simultaneously carry out
multiple independent processes  a salient limitation in many domains of human
cognition  remains largely unexplored. In this paper we use a graphtheoretic
analysis of network architecture to address this question, where tasks are
represented as edges in a bipartite graph $G=(A \cup B, E)$. We define a new
measure of multitasking capacity of such networks, based on the assumptions
that tasks that \emph{need} to be multitasked rely on independent resources,
i.e., form a matching, and that tasks \emph{can} be multitasked without
interference if they form an induced matching. Our main result is an inherent
tradeoff between the multitasking capacity and the average degree of the
network that holds \emph{regardless of the network architecture}. These results
are also extended to networks of depth greater than $2$. On the positive side,
we demonstrate that networks that are randomlike (e.g., locally sparse) can
have desirable multitasking properties. Our results shed light into the
parallelprocessing limitations of neural systems and provide insights that may
be useful for the analysis and design of parallel architectures.

The sorting number of a graph with $n$ vertices is the minimum depth of a
sorting network with $n$ inputs and outputs that uses only the edges of the
graph to perform comparisons. Many known results on sorting networks can be
stated in terms of sorting numbers of different classes of graphs. In this
paper we show the following general results about the sorting number of graphs.
Any $n$vertex graph that contains a simple path of length $d$ has a sorting
network of depth $O(n \log(n/d))$.
Any $n$vertex graph with maximal degree $\Delta$ has a sorting network of
depth $O(\Delta n)$.
We also provide several results that relate the sorting number of a graph
with its routing number, size of its maximal matching, and other well known
graph properties. Additionally, we give some new bounds on the sorting number
for some typical graphs.

We present an adaptive tester for the unateness property of Boolean
functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n
\log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts
a unate function, and rejects with probability at least 0.9 if a function is
$\epsilon$far from being unate.

For a finite undirected graph $G = (V,E)$, let $p_{u,v}(t)$ denote the
probability that a continuoustime random walk starting at vertex $u$ is in $v$
at time $t$. In this note we give an example of a Cayley graph $G$ and two
vertices $u,v \in G$ for which the function \[ r_{u,v}(t) =
\frac{p_{u,v}(t)}{p_{u,u}(t)} \qquad t \geq 0 \] is not monotonically
nondecreasing. This answers a question asked by Peres in 2013.

We consider the robustness of computational hardness of problems whose input
is obtained by applying independent random deletions to worstcase instances.
For some classical $NP$hard problems on graphs, such as Coloring,
VertexCover, and Hamiltonicity, we examine the complexity of these problems
when edges (or vertices) of an arbitrary graph are deleted independently with
probability $1p > 0$. We prove that for $n$vertex graphs, these problems
remain as hard as in the worstcase, as long as $p > \frac{1}{n^{1\epsilon}}$
for arbitrary $\epsilon \in (0,1)$, unless $NP \subseteq BPP$.
We also prove hardness results for Constraint Satisfaction Problems, where
random deletions are applied to clauses or variables, as well as the SubsetSum
problem, where items of a given instance are deleted at random.

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.

In this paper we consider an excited random walk on $\mathbb{Z}$ in
identically piled periodic environment. This is a discrete time process on
$\mathbb{Z}$ defined by parameters $(p_1,\dots p_M) \in [0,1]^M$ for some
positive integer $M$, where the walker upon the $i$th visit to $z \in
\mathbb{Z}$ moves to $z+1$ with probability $p_{i\pmod M}$, and moves to $z1$
with probability $1p_{i \pmod M}$. We give an explicit formula in terms of the
parameters $(p_1,\dots,p_M)$ which determines whether the walk is recurrent,
transient to the left, or transient to the right. In particular, in the case
that $\frac{1}{M}\sum_{i=1}^{M}p_{i}=\frac {1}{2}$ all behaviors are possible,
and may depend on the order of the $p_i$. Our framework allows us to reprove
some known results on ERW with no additional effort.

We define the following parameter of connected graphs. For a given graph $G$
we place one agent in each vertex of $G$. Every pair of agents sharing a common
edge is declared to be acquainted. In each round we choose some matching of $G$
(not necessarily a maximal matching), and for each edge in the matching the
agents on this edge swap places. After the swap, again, every pair of agents
sharing a common edge become acquainted, and the process continues. We define
the \emph{acquaintance time} of a graph $G$, denoted by $AC(G)$, to be the
minimal number of rounds required until every two agents are acquainted.
We first study the acquaintance time for some natural families of graphs
including the path, expanders, the binary tree, and the complete bipartite
graph. We also show that for all positive integers $n$ and $k \leq n^{1.5}$
there exists an $n$vertex graph $G$ such that $AC(G) =\Theta(k)$. We also
prove that for all $n$vertex connected graphs $G$ we have $AC(G) =
O\left(\frac{n^2}{\log(n)/\log\log(n)}\right)$, improving the $O(n^2)$ trivial
upper bound achieved by sequentially letting each agent perform depthfirst
search along a spanning tree of $G$.
Studying the computational complexity of this problem, we prove that for any
constant $t \geq 1$ the problem of deciding that a given graph $G$ has $AC(G)
\leq t$ or $AC(G) \geq 2t$ is $\mathcal{NP}$complete. That is, $AC(G)$ is
$\mathcal{NP}$hard to approximate within multiplicative factor of 2, as well
as within any additive constant factor.
On the algorithmic side, we give a deterministic algorithm that given a graph
$G$ with $AC(G)=1$ finds a ${\lceil n/c\rceil}$rounds strategy for
acquaintance in time $n^{c+O(1)}$. We also design a randomized polynomial time
algorithm that given a graph $G$ with $AC(G)=1$ finds with high probability an
$O(\log(n))$rounds strategy for acquaintance.

We construct a biLipschitz bijection from the Boolean cube to the Hamming
ball of equal volume. More precisely, we show that for all even n there exists
an explicit bijection f from the ndimensional Boolean cube to the Hamming ball
of equal volume embedded in (n+1)dimensional Boolean cube, such that for all x
and y it holds that distance(x,y) / 5 <= distance(f(x),f(y)) <= 4 distance(x,y)
where distance(,) denotes the Hamming distance. In particular, this implies
that the Hamming ball is biLipschitz transitive.
This result gives a strong negative answer to an open problem of Lovett and
Viola [CC 2012], who raised the question in the context of sampling
distributions in lowlevel complexity classes. The conceptual implication is
that the problem of proving lower bounds in the context of sampling
distributions will require some new ideas beyond the sensitivitybased
structural results of Boppana [IPL 97].
We study the mapping f further and show that it (and its inverse) are
computable in DLOGTIMEuniform TC0, but not in AC0. Moreover, we prove that f
is "approximately local" in the sense that all but the last output bit of f are
essentially determined by a single input bit.

In this note we confirm a conjecture raised by Benjamini et al. \cite{BST} on
the acquaintance time of graphs, proving that for all graphs $G$ with $n$
vertices it holds that $\AC(G) = O(n^{3/2})$, which is tight up to a
multiplicative constant. This is done by proving that for all graphs $G$ with
$n$ vertices and maximal degree $\Delta$ it holds that $\AC(G) \leq 20 \Delta
n$. Combining this with the bound $\AC(G) \leq O(n^2/\Delta)$ from \cite{BST}
gives the foregoing uniform upper bound of all $n$vertex graphs.
We also prove that for the $n$vertex path $P_n$ it holds that
$\AC(P_n)=n2$. In addition we show that the barbell graph $B_n$ consisting of
two cliques of sizes $\ceil{n/2}$ and $\floor{n/2}$ connected by a single edge
also has $\AC(B_n) = n2$. This shows that it is possible to add $\Omega(n^2)$
edges to $P_n$ without changing the $\AC$ value of the graph.

We study a discrete time self interacting random process on graphs, which we
call Greedy Random Walk. The walker is located initially at some vertex. As
time evolves, each vertex maintains the set of adjacent edges touching it that
have not been crossed yet by the walker. At each step, the walker being at some
vertex, picks an adjacent edge among the edges that have not traversed thus far
according to some (deterministic or randomized) rule. If all the adjacent edges
have already been traversed, then an adjacent edge is chosen uniformly at
random. After picking an edge the walk jumps along it to the neighboring
vertex. We show that the expected edge cover time of the greedy random walk is
linear in the number of edges for certain natural families of graphs. Examples
of such graphs include the complete graph, even degree expanders of logarithmic
girth, and the hypercube graph. We also show that GRW is transient in $\Z^d$
for all $d \geq 3$.