Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistinguishing Views in Symmetric Networks: A Tight Lower Bound
147
0
0.0
(
0
)
Added by
Adrian Kosowski
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing dense planar structures inside any graph: (i) A $frac{1}{6}$ approximation algorithm for, given any graph $G$, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous $frac{1}{11}$-approximation; (ii) An alternate (and arguably more illustrative) proof of the $frac{4}{9}$ approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
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 the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. The proof is based on evaluating certain Krein parameters of a symmetric association scheme defined over partial permutations. The study of this association scheme may be of independent interest.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
