We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge , as planarity requires). Such adjacencies define a map graph . We give an NP characterization for such graphs, derive some consequences regarding sparsity and coloring, and survey some algorithmic results.

We provide positive and negative results concerning the “standard method” of identifying a hidden subgroup of a nonabelian group using a quantum computer.

We consider the problem of designing a near-optimal linear decision tree to classify two given point sets B and W in $\Re^n$. A linear decision tree defines a polyhedral subdivision of space; it is a classifier if no leaf region contains points from both sets. We show hardness results for computing such a classifier with approximately optimal depth or size in polynomial time. In particular, we show that unless NP = ZPP, the depth of a classifier cannot be approximated within any constant factor, and that the total number of nodes cannot be approximated within any fixed polynomial. Our proof uses a simple connection between this problem and graph coloring and uses the result of Feige and Kilian on the inapproximability of the chromatic number. We also study the problem of designing a classifier with a single inequality that involves as few variables as possible and point out certain aspects of the difficulty of this problem.

CCF (Collaborative Computing Frameworks) is a suite of software systems, communications protocols, and tools that enable collaborative, computer-based cooperative work. CCF constructs a virtual work environment on multiple computer systems connected over the Internet, to form a Collaboratory. In this setting, participants interact with each other, simultaneously access and operate computer applications, refer to global data repositories or archives, collectively create and manipulate documents or other artifacts, perform computational transformations, and conduct a number of other activities via telepresence. Research issues addressed in this project include problem solving environments and methodologies for laboratory and instrument-based scientific disciplines, and computer science issues in heterogeneous distributed systems. New approaches are being investigated and developed for fast multiway communication, robust geographically distributed data management methodologies, high-performance computational transforms inlined within collaboration sessions, and related auxiliary issues such as active documents, security, archival storage, and experiment management and control. In this paper, we discuss the design philosophy and systems rationale behind CCF, describe the major subsystems of the collaborative computing environment, and discuss the salient features of the system.

We introduce and study a modified notion of planarity, in which two regions of a map are considered adjacent when they share any point of their boundaries (not an edge, as standard planarity requires).We seek to characterize the abstract graphs realized by such map adjacencies.We prove some preliiinary properGs of such graphs, and give a polynomial time algorithm for the following restricted problem: given an abstract graph, decide whether it is realized by a map in which at most four regions meet at any point.The general recognition problem remains open. 1 Introduction 1.1 Motivation: Topological Inference Suppose that you are told t.hat four planar regions relate in the following way: A is inside B; B overlaps G; C touches D on t.he outside; D overlaps B; D is disjoint from A; and C overlaps A. All four planar regions are "bubbles" with no holes (to be rigorous: disc homeomorphs).Is this possible?If so, we would like a model, a picture of four regions so related; if not, a proof of impossibility.This deceptively simple estension of propositional logic is known as the topological inference problem [5], and its special cases, extensions, and variants are studied in the area of geographic information systems [3, 4, 10, 5, 111.Despite much effort (and claims in t.he literature [12, 41.. .),no decision algorithm and f&rite asiomatization for this problem is known -although t,he problem becomes both finitely axiomatizable and polynomial-time decidable in any number of dimensions ot,her than two.In fact, the following special

We consider the special case of the traveling salesman problem (TSP) in which the distance metric is the shortest-path metric of a planar unweighted graph. We present a polynomial-time approximation scheme (PTAS) for this problem.

Let S be a set of n points in IR d . A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W . We show the existence of weak "-nets of size O i 1 " d log fi d 1 " j , where fi 2 = 0, fi 3 = 1, and fi d 0:149 \\Delta 2 d\\Gamma1 (d \\Gamma 1)!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time n(1=") O(1) . We also consider two special cases: when S is in convex position, we prove the existence of a net of size O( 1 " log 1:6 1 " ); for the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1=").

A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time $\lceil \lg n\rceil$, given that each message transmission takes one time unit and a vertex participates in at most one transmission per time step. This paper establishes tight bounds for $B( n )$, the minimum number of edges of a broadcast graph, and $D( n )$, the minimum maxdegree of a broadcast graph. Let $L( n )$ denote the number of consecutive leading 1’s in the binary representation of integer $n - 1$. It is shown that $B( n ) = \Theta ( L( n )\cdot n )$ and $D( n ) = \Theta ( \lg \lg n + L ( n ) )$ and for every n we give a construction simultaneously within a constant factor of both lower bounds. For all n, graphs with $O( n )$ edges and $O( \lg \lg n )$ maxdegree requiring at most $\lceil \lg n \rceil + 1$ time units to broadcast are constructed. These broadcast protocols may be implemented with local control and $O( \lg \lg n )$ bits overhead per message.