• ### Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover(1802.08237)

Feb. 22, 2018 cs.DC, cs.DS
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].
• ### Round Compression for Parallel Matching Algorithms(1707.03478)

Feb. 1, 2018 cs.DC, cs.DS
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 large-scale 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} problem---one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate 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 near-linear 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.
• ### Robust Submodular Maximization: A Non-Uniform Partitioning Approach(1706.04918)

June 15, 2017 cs.LG, stat.ML
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 worst-case setting considered in (Orlin et al., 2016), in which a constant-factor 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).
• ### Exploring the Limits of Static Failover Routing(1409.0034)

July 27, 2016 cs.NI
We present and study the Static-Routing-Resiliency 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 destination-based 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 packet-duplication, with packet-header-rewriting) and present both positive and negative results that relate the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions $G$, to its resiliency.
• ### Resonant Thermoelectric Nanophotonics(1606.03313)

Photodetectors are typically based on photocurrent generation from electron-hole 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 bandgap-independent photodetection mechanism. We report results for both resonant nanophotonic bismuth telluride-antimony telluride structures and chromel-alumel structures as examples of a broad class of nanophotonic thermoelectric structures useful for fast, low-cost and robust optoelectronic applications such as non-bandgap-limited hyperspectral and broad-band photodetectors.
• ### Homometric sets in trees(1302.1386)

Nov. 6, 2013 math.CO
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$.