We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements are input as words defined by straight-line programs defined over a finite generating set for the group. We prove also that, for any infinite hyperbolic group G, the compressed knapsack problem in G is NP-complete.

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Digital content is for copying: quotation, revision, plagiarism, and file sharing all create copies. Document fingerprinting is concerned with accurately identifying copying, including small partial copies, within large sets of documents.We introduce the class of local document fingerprinting algorithms, which seems to capture an essential property of any finger-printing technique guaranteed to detect copies. We prove a novel lower bound on the performance of any local algorithm. We also develop winnowing, an efficient local fingerprinting algorithm, and show that winnowing's performance is within 33% of the lower bound. Finally, we also give experimental results on Web data, and report experience with MOSS, a widely-used plagiarism detection service.

This paper presents a network mapping algorithm and proves its correctness assuming a traffic-free network.Respecting well-defined parameters, the algorithm produces a graph isomorphic to N -F, where N is the network of switches and hosts and F is the set of switches connected by a switch-bridge to the set of hosts I-I.We show its performance on a Myrinet system-area network with a fat-tree-like topology.It can map 36 nodes, 13 switches and 64 links in 248 ms and 100 nodes, 40 switches, and 193 linksin981 rns.From such maps, the system computes mutually deadlock-free routes and distributes them to all network interfaces.Switched, multi-gigabyte per second, system area networks are the enabling building-blocks for networks of workstations.Because of their core role, these networks should be dynamically recontigurable, automatically adapting to the addition or removal of hosts, switches and links. IntroductionSystem area networks [1] move switched, low-latency, high-speed networks away from the backplanes and cabinets of massively parallel processors into the traditional territory of local area networks.These networks commonly use source-based message routing through anonymous switches.In this regime, their topologies may no longer be the static, well-defined, and well-understood [2] graphs such as hypercubes, meshes.etc., and instead may be arbitrary graphs that change over time.Therefore, systems must periodically discover their topologies rather than assuming one a priori.Lacking an out-of-band mechanism for directly querying switches for their identities, systems must use in-band messaging to disambiguate switch identities when discovering the network topology.From the resulting maps, systems can compute mutually deadlock-free routes without relying upon properties of traditional multicomputer networks, e.g., static topologies, that may now be transient.

We present nearly tight bounds for wormhole muting on Butterfly networks which indicate it is fundamentally different from store-and-forward packet routing. For instance, consider the problem of routing N log N (randomly generated) log N length messages from the inputs to the outputs of an N input Butterfly. We show that with high probability that this must take time at least /spl Omega/(log/sup 3/N/(log log N)/sup 2/). The best lower bound known earlier was /spl Omega/(log/sup 2/ N), which is simply the flit congestion an each link. Thus our lower bound shows that wormhole routing (unlike store-and-forward-routing) is very ineffective in utilizing communication links. We also give a routing algorithm which nearly matches our lower bound. That is, we show that with high probability the time is O(log/sup 3/ N log log N), which improves upon, the previous best bound of O(log/sup 4/ N). Our method also extends to other networks such as the two-dimensional mesh, where it is nearly optimal. Finally, we consider the problem of offline wormhole routing, where we give optimal algorithms for trees and multidimensional meshes.>