
We present $O(\log\log n)$round algorithms in the Massively Parallel
Computation (MPC) model, with $\tilde{O}(n)$ memory per machine, that compute a
maximal independent set, a $1+\epsilon$ approximation of maximum matching, and
a $2+\epsilon$ approximation of minimum vertex cover, for any $n$vertex graph
and any constant $\epsilon>0$. These improve the state of the art as follows:
 Our MIS algorithm leads to a simple $O(\log\log \Delta)$round MIS
algorithm in the Congested Clique model of distributed computing. This result
improves exponentially on the $\tilde{O}(\sqrt{\log \Delta})$round algorithm
of Ghaffari [PODC'17].
 Our $O(\log\log n)$round $(1+\epsilon)$approximate maximum matching
algorithm simplifies and improves on a rather complex $O(\log^2\log n)$round
$(1+\epsilon)$approximation algorithm of Czumaj et al. [STOC'18].
 Our $O(\log\log n)$round $(2+\epsilon)$approximate minimum vertex cover
algorithm improves on an $O(\log\log n)$round $O(1)$approximation of Assadi
et al. [arXiv'17].

For over a decade now we have been witnessing the success of {\em massive
parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or
Spark. One of the reasons for their success is the fact that these frameworks
are able to accurately capture the nature of largescale computation. In
particular, compared to the classic distributed algorithms or PRAM models,
these frameworks allow for much more local computation. The fundamental
question that arises in this context is though: can we leverage this additional
power to obtain even faster parallel algorithms?
A prominent example here is the {\em maximum matching} problemone of the
most classic graph problems. It is well known that in the PRAM model one can
compute a 2approximate maximum matching in $O(\log{n})$ rounds. However, the
exact complexity of this problem in the MPC framework is still far from
understood. Lattanzi et al. showed that if each machine has $n^{1+\Omega(1)}$
memory, this problem can also be solved $2$approximately in a constant number
of rounds. These techniques, as well as the approaches developed in the follow
up work, seem though to get stuck in a fundamental way at roughly $O(\log{n})$
rounds once we enter the nearlinear memory regime. It is thus entirely
possible that in this regime, which captures in particular the case of sparse
graph computations, the best MPC round complexity matches what one can already
get in the PRAM model, without the need to take advantage of the extra local
computation power.
In this paper, we finally refute that perplexing possibility. That is, we
break the above $O(\log n)$ round complexity bound even in the case of {\em
slightly sublinear} memory per machine. In fact, our improvement here is {\em
almost exponential}: we are able to deliver a $(2+\epsilon)$approximation to
maximum matching, for any fixed constant $\epsilon>0$, in $O((\log \log n)^2)$
rounds.

We study the problem of maximizing a monotone submodular function subject to
a cardinality constraint $k$, with the added twist that a number of items
$\tau$ from the returned set may be removed. We focus on the worstcase setting
considered in (Orlin et al., 2016), in which a constantfactor approximation
guarantee was given for $\tau = o(\sqrt{k})$. In this paper, we solve a key
open problem raised therein, presenting a new Partitioned Robust (PRo)
submodular maximization algorithm that achieves the same guarantee for more
general $\tau = o(k)$. Our algorithm constructs partitions consisting of
buckets with exponentially increasing sizes, and applies standard submodular
optimization subroutines on the buckets in order to construct the robust
solution. We numerically demonstrate the performance of PRo in data
summarization and influence maximization, demonstrating gains over both the
greedy algorithm and the algorithm of (Orlin et al., 2016).

We present and study the StaticRoutingResiliency problem, motivated by
routing on the Internet: Given a graph $G$, a unique destination vertex $d$,
and an integer constant $c>0$, does there exist a static and destinationbased
routing scheme such that the correct delivery of packets from any source $s$ to
the destination $d$ is guaranteed so long as (1) no more than $c$ edges fail
and (2) there exists a physical path from $s$ to $d$? We embark upon a
systematic exploration of this fundamental question in a variety of models
(deterministic routing, randomized routing, with packetduplication, with
packetheaderrewriting) and present both positive and negative results that
relate the edgeconnectivity of a graph, i.e., the minimum number of edges
whose deletion partitions $G$, to its resiliency.

Photodetectors are typically based on photocurrent generation from
electronhole pairs in semiconductor structures and on bolometry for
wavelengths that are below bandgap absorption. In both cases, resonant
plasmonic and nanophotonic structures have been successfully used to enhance
performance. In this work, we demonstrate subwavelength thermoelectric
nanostructures designed for resonant spectrally selective absorption, which
creates large enough localized temperature gradients to generate easily
measureable thermoelectric voltages. We show that such structures are tunable
and are capable of highly wavelength specific detection, with an input power
responsivity of up to 119 V/W (referenced to incident illumination), and
response times of nearly 3 kHz, by combining resonant absorption and
thermoelectric junctions within a single structure, yielding a
bandgapindependent photodetection mechanism. We report results for both
resonant nanophotonic bismuth tellurideantimony telluride structures and
chromelalumel structures as examples of a broad class of nanophotonic
thermoelectric structures useful for fast, lowcost and robust optoelectronic
applications such as nonbandgaplimited hyperspectral and broadband
photodetectors.

Let $G = (V,E)$ denote a simple graph with the vertex set $V$ and the edge
set $E$. The profile of a vertex set $V'\subseteq V$ denotes the multiset of
pairwise distances between the vertices of $V'$. Two disjoint subsets of $V$
are \emph{homometric}, if their profiles are the same. If $G$ is a tree on $n$
vertices we prove that its vertex sets contains a pair of disjoint homometric
subsets of size at least $\sqrt{n/2}  1$. Previously it was known that such a
pair of size at least roughly $n^{1/3}$ exists. We get a better result in case
of haircomb trees, in which we are able to find a pair of disjoint homometric
sets of size at least $cn^{2/3}$ for a constant $c > 0$.