ﻻ يوجد ملخص باللغة العربية
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 most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $Omega(Dlog (n/D))$ are identical.
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph $G$ contains a cactus subgraph $C$ where $C$ contains at least a $frac{1}{6}$ fraction of the triangular faces of $G
We show in this note that the average number of terms in the optimal double-base number system is in Omega(n / log n). The lower bound matches the upper bound shown earlier by Dimitrov, Imbert, and Mishra (Math. of Comp. 2008).
The Index Erasure problem asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight $Omega(sqrt{n})$ lower bound on the quantum query complexity of the non-coherent case of
We prove that, for an undirected graph with $n$ vertices and $m$ edges, each labeled with a linear function of a parameter $lambda$, the number of different minimum spanning trees obtained as the parameter varies can be $Omega(mlog n)$.
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