ﻻ يوجد ملخص باللغة العربية
MapReduce (and its open source implementation Hadoop) has become the de facto platform for processing large data sets. MapReduce offers a streamlined computational framework by interleaving sequential and parallel computation while hiding underlying system issues from the programmer. Due to the popularity of MapReduce, there have been attempts in the theoretical computer science community to understand the power and limitations of the MapReduce framework. In the most widely studied MapReduce models each machine has memory sub-linear in the input size to the problem, hence cannot see the entire input. This restriction places many limitations on algorithms that can be developed for the model; however, the current understanding of these restrictions is still limited. In this paper, our goal is to work towards understanding problems which do not admit efficient algorithms in the MapReduce model. We study the basic question of determining if a graph is connected or not. We concentrate on instances of this problem where an algorithm is to determine if a graph consists of a single cycle or two disconnected cycles. In this problem, locally every part of the graph is similar and the goal is to determine the global structure of the graph. We consider a natural class of algorithms that can store/process/transfer the information only in the form of paths and show that no randomized algorithm cannot answer the decision question in a sub-logarithmic number of rounds. Currently, there are no absolute super constant lower bounds on the number of rounds known for any problem in MapReduce. We introduce some of the first lower bounds for a natural graph problem, albeit for a restricted class of algorithms. We believe our result makes progress towards understanding the limitations of MapReduce.
Let $G = (V,w)$ be a weighted undirected graph with $m$ edges. The cut dimension of $G$ is the dimension of the span of the characteristic vectors of the minimum cuts of $G$, viewed as vectors in ${0,1}^m$. For every $n ge 2$ we show that the cut dim
Given two strings $S$ and $P$, the Episode Matching problem is to compute the length of the shortest substring of $S$ that contains $P$ as a subsequence. The best known upper bound for this problem is $tilde O(nm)$ by Das et al. (1997), where $n,m$ a
M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model by Woeginger. BT model can be further divided
The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $ngeq Dgeq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at mo
We prove that with high probability over the choice of a random graph $G$ from the ErdH{o}s-Renyi distribution $G(n,1/2)$, a natural $n^{O(varepsilon^2 log n)}$-time, degree $O(varepsilon^2 log n)$ sum-of-squares semidefinite program cannot refute th