title: Polygonal Chains Cannot Lock in 4D

abstract: We prove that, in all dimensions d>=4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of ``moves.'' These results contrast to those known for d=2, where trees can ``lock,'' and for d=3, where open and closed chains can lock.


title: Computational Geometry Column 36

abstract: Two results in "computational origami" are illustrated.


title: Computational Geometry Column 37

abstract: Open problems from the 15th Annual ACM Symposium on Computational Geometry.


title: Secure Multicast in a WAN

abstract: A secure reliable multicast protocol enables a process to send a message to a group of recipients such that all correct destinations receive the same message, despite the malicious efforts of fewer than a third of the total number of processes, including the sender. This has been sh own to be a useful tool in building secure distributed services, albeit with a cost that typically grows linearly with the size of the system. For very large networks, for which this is prohibitive, we present two approaches for reducing the cost: First, we show a protocol whose cost is on the order of the number of tolerated failures. Secondly, we show how relaxing the consistency requirement to a probabilistic guarantee can reduce the associated cost, effectively to a constant.


title: Secure Execution of Java Applets using a Remote Playground

abstract: Mobile code presents a number of threats to machines that execute it. We introduce an approach for protecting machines and the resources they hold from mobile code, and describe a system based on our approach for protecting host machines from Java 1.1 applets. In our approach, each Java applet downloaded to the protected domain is rerouted to a dedicated machine (or set of machines), the {\em playground}, at which it is executed. Prior to execution the applet is transformed to use the downloading user's web browser as a graphics terminal for its input and output, and so the user has the illusion that the applet is running on her own machine. In reality, however, mobile code runs only in the sanitized environment of the playground, where user files cannot be mounted and from which only limited network connections are accepted by machines in the protected domain. Our playground thus provides a second level of defense against mobile code that circumvents language-based defenses. The paper presents the design and implementation of a playground for Java 1.1 applets, and discusses extensions of it for other forms of mobile code including Java 1.2.


title: On Propagating Updates in a Byzantine Environment

abstract: We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than $t$ replicas fail, and that each update is initially received by at least $t$ correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least $t$ others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failures---which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal.


title: The Load and Availability of Byzantine Quorum Systems

abstract: Replicated services accessed via {\em quorums} enable each access to be performed at only a subset (quorum) of the servers, and achieve consistency across accesses by requiring any two quorums to intersect. Recently, $b$-masking quorum systems, whose intersections contain at least $2b+1$ servers, have been proposed to construct replicated services tolerant of $b$ arbitrary (Byzantine) server failures. In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones. We present four novel constructions for $b$-masking quorum systems in this model, each of which has optimal {\em load} (the probability of access of the busiest server) or optimal availability (probability of some quorum surviving failures). To show optimality we also prove lower bounds on the load and availability of any $b$-masking quorum system in this model.


title: Safe Deals Between Strangers

abstract: E-business, information serving, and ubiquitous computing will create heavy request traffic from strangers or even incognitos. Such requests must be managed automatically. Two ways of doing this are well known: giving every incognito consumer the same treatment, and rendering service in return for money. However, different behavior will be often wanted, e.g., for a university library with different access policies for undergraduates, graduate students, faculty, alumni, citizens of the same state, and everyone else. For a data or process server contacted by client machines on behalf of users not previously known, we show how to provide reliable automatic access administration conforming to service agreements. Implementations scale well from very small collections of consumers and producers to immense client/server networks. Servers can deliver information, effect state changes, and control external equipment. Consumer privacy is easily addressed by the same protocol. We support consumer privacy, but allow servers to deny their resources to incognitos. A protocol variant even protects against statistical attacks by consortia of service organizations. One e-commerce application would put the consumer's tokens on a smart card whose readers are in vending kiosks. In e-business we can simplify supply chain administration. Our method can also be used in sensitive networks without introducing new security loopholes.


title: Collective Intelligence for Control of Distributed Dynamical Systems

abstract: We consider the El Farol bar problem, also known as the minority game (W. B. Arthur, ``The American Economic Review'', 84(2): 406--411 (1994), D. Challet and Y.C. Zhang, ``Physica A'', 256:514 (1998)). We view it as an instance of the general problem of how to configure the nodal elements of a distributed dynamical system so that they do not ``work at cross purposes'', in that their collective dynamics avoids frustration and thereby achieves a provided global goal. We summarize a mathematical theory for such configuration applicable when (as in the bar problem) the global goal can be expressed as minimizing a global energy function and the nodes can be expressed as minimizers of local free energy functions. We show that a system designed with that theory performs nearly optimally for the bar problem.

categories: cs.LG adap-org cond-mat cs.AI cs.DC cs.MA nlin.AO


title: An Introduction to Collective Intelligence

abstract: This paper surveys the emerging science of how to design a ``COllective INtelligence'' (COIN). A COIN is a large multi-agent system where: (i) There is little to no centralized communication or control; and (ii) There is a provided world utility function that rates the possible histories of the full system. In particular, we are interested in COINs in which each agent runs a reinforcement learning (RL) algorithm. Rather than use a conventional modeling approach (e.g., model the system dynamics, and hand-tune agents to cooperate), we aim to solve the COIN design problem implicitly, via the ``adaptive'' character of the RL algorithms of each of the agents. This approach introduces an entirely new, profound design problem: Assuming the RL algorithms are able to achieve high rewards, what reward functions for the individual agents will, when pursued by those agents, result in high world utility? In other words, what reward functions will best ensure that we do not have phenomena like the tragedy of the commons, Braess's paradox, or the liquidity trap? Although still very young, research specifically concentrating on the COIN design problem has already resulted in successes in artificial domains, in particular in packet-routing, the leader-follower problem, and in variants of Arthur's El Farol bar problem. It is expected that as it matures and draws upon other disciplines related to COINs, this research will greatly expand the range of tasks addressable by human engineers. Moreover, in addition to drawing on them, such a fully developed scie nce of COIN design may provide much insight into other already established scientific fields, such as economics, game theory, and population biology.

categories: cs.LG adap-org cond-mat cs.DC cs.MA nlin.AO


title: Representing Scholarly Claims in Internet Digital Libraries: A Knowledge Modelling Approach

abstract: This paper is concerned with tracking and interpreting scholarly documents in distributed research communities. We argue that current approaches to document description, and current technological infrastructures particularly over the World Wide Web, provide poor support for these tasks. We describe the design of a digital library server which will enable authors to submit a summary of the contributions they claim their documents makes, and its relations to the literature. We describe a knowledge-based Web environment to support the emergence of such a community-constructed semantic hypertext, and the services it could provide to assist the interpretation of an idea or document in the context of its literature. The discussion considers in detail how the approach addresses usability issues associated with knowledge structuring environments.


title: Quadrilateral Meshing by Circle Packing

abstract: We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoi diagram, (2) all elements have two opposite right angles, (3) all elements are kites, or (4) all angles are at most 120 degrees. In each case the total number of elements is O(n), where n is the number of input vertices.


title: A Differential Invariant for Zooming

abstract: This paper presents an invariant under scaling and linear brightness change. The invariant is based on differentials and therefore is a local feature. Rotationally invariant 2-d differential Gaussian operators up to third order are proposed for the implementation of the invariant. The performance is analyzed by simulating a camera zoom-out.


title: Construction of regular languages and recognizability of polynomials

abstract: A generalization of numeration system in which the set N of the natural numbers is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite regular language. Here we show that if P belonging to Q[x] is a polynomial such that P(N) is a subset of N then we can construct a numeration system in which the set of representations of P(N) is regular. The main issue in this construction is to setup a regular language with a density function equals to P(n+1)-P(n) for n large enough.


title: Emerging Challenges in Computational Topology

abstract: Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.


title: Semantic robust parsing for noun extraction from natural language queries

abstract: This paper describes how robust parsing techniques can be fruitful applied for building a query generation module which is part of a pipelined NLP architecture aimed at process natural language queries in a restricted domain. We want to show that semantic robustness represents a key issue in those NLP systems where it is more likely to have partial and ill-formed utterances due to various factors (e.g. noisy environments, low quality of speech recognition modules, etc...) and where it is necessary to succeed, even if partially, in extracting some meaningful information.


title: Iterative Deepening Branch and Bound

abstract: In tree search problem the best-first search algorithm needs too much of space . To remove such drawbacks of these algorithms the IDA* was developed which is both space and time cost efficient. But again IDA* can give an optimal solution for real valued problems like Flow shop scheduling, Travelling Salesman and 0/1 Knapsack due to their real valued cost estimates. Thus further modifications are done on it and the Iterative Deepening Branch and Bound Search Algorithms is developed which meets the requirements. We have tried using this algorithm for the Flow Shop Scheduling Problem and have found that it is quite effective.


title: Convex Tours of Bounded Curvature

abstract: We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m vertices, containing an obstacle in a form of a simple polygon with $n$ vertices. We present an O(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible.


title: Computing largest circles separating two sets of segments

abstract: A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased while still separating the two given sets. An Theta(n log n) optimal algorithm is proposed to find all largest circles separating two given sets of line segments when line segments are allowed to meet only at their endpoints. In the general case, when line segments may intersect $\Omega(n^2)$ times, our algorithm can be adapted to work in O(n alpha(n) log n) time and O(n \alpha(n)) space, where alpha(n) represents the extremely slowly growing inverse of the Ackermann function.


title: Motion Planning of Legged Robots

abstract: We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to two constraints: each leg has a maximal extension R (accessibility constraint) and the body of the robot must lie above the convex hull of its feet (stability constraint). Moreover, the robot can only put its feet on some regions, called the foothold regions. The free space F is the set of positions of the body of the robot such that there exists a set of accessible footholds for which the robot is stable. We present an efficient algorithm that computes F in O(n2 log n) time using O(n2 alpha(n)) space for n discrete point footholds where alpha(n) is an extremely slowly growing function (alpha(n) <= 3 for any practical value of n). We also present an algorithm for computing F when the foothold regions are pairwise disjoint polygons with n edges in total. This algorithm computes F in O(n2 alpha8(n) log n) time using O(n2 alpha8(n)) space (alpha8(n) is also an extremely slowly growing function). These results are close to optimal since Omega(n2) is a lower bound for the size of F.


title: Circular Separability of Polygons

abstract: Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the query lines.


title: Not Just a Matter of Time: Field Differences and the Shaping of Electronic Media in Supporting Scientific Communication

abstract: The shift towards the use of electronic media in scholarly communication appears to be an inescapable imperative. However, these shifts are uneven, both with respect to field and with respect to the form of communication. Different scientific fields have developed and use distinctly different communicative forums, both in the paper and electronic arenas, and these forums play different communicative roles within the field. One common claim is that we are in the early stages of an electronic revolution, that it is only a matter of time before other fields catch up with the early adopters, and that all fields converge on a stable set of electronic forums. A social shaping of technology (SST) perspective helps us to identify important social forces centered around disciplinary constructions of trust and of legitimate communication that pull against convergence. This analysis concludes that communicative plurality and communicative heterogeneity are durable features of the scholarly landscape, and that we are likely to see field differences in the use of and meaning ascribed to communications forums persist, even as overall use of electronic communications technologies both in science and in society as a whole increases.


title: The Rough Guide to Constraint Propagation

abstract: We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In particular, using the notions commutativity and semi-commutativity, we show how the well-known AC-3, PC-2, DAC and DPC algorithms are instances of a single generic algorithm. The work reported here extends and simplifies that of Apt, cs.AI/9811024.


title: Automatic Generation of Constraint Propagation Algorithms for Small Finite Domains

abstract: We study here constraint satisfaction problems that are based on predefined, explicitly given finite constraints. To solve them we propose a notion of rule consistency that can be expressed in terms of rules derived from the explicit representation of the initial constraints. This notion of local consistency is weaker than arc consistency for constraints of arbitrary arity but coincides with it when all domains are unary or binary. For Boolean constraints rule consistency coincides with the closure under the well-known propagation rules for Boolean constraints. By generalizing the format of the rules we obtain a characterization of arc consistency in terms of so-called inclusion rules. The advantage of rule consistency and this rule based characterization of the arc consistency is that the algorithms that enforce both notions can be automatically generated, as CHR rules. So these algorithms could be integrated into constraint logic programming systems such as Eclipse. We illustrate the usefulness of this approach to constraint propagation by discussing the implementations of both algorithms and their use on various examples, including Boolean constraints, three valued logic of Kleene, constraints dealing with Waltz's language for describing polyhedreal scenes, and Allen's qualitative approach to temporal logic.


title: Distributed Algorithms in Multihop Broadcast Networks

abstract: Broadcast networks are often used in modern communication systems. A common broadcast network is a single hop shared media system, where a transmitted message is heard by all neighbors, such as some LAN networks. In this work we consider a more complex environment, in which a transmitted message is heard only by a group of neighbors, such as Ad-Hoc networks, satellite and radio networks, as well as wireless multistation backbone system for mobile communication. It is important to design efficient algorithms for such environments. Our main result is a new Leader Election algorithm, with O(n) time complexity and O(n*lg(n)) message transmission complexity. Our distributed solution uses a propagation of information with feedback (PIF) building block tuned to the broadcast media, and a special counting and joining approach for the election procedure phase. The latter is required for achieving the linear time. It is demonstrated that the broadcast model requires solutions which are different from the known point-to-point model.


title: Certificate Revocation Paradigms

abstract: Research in the field of electronic signature confirmation has been active for some 20 years now. Unfortunately present certificate-based solutions also come from that age when no-one knew about online data transmission. The official standardized X.509 framework also depends heavily on offline operations, one of the most complicated ones being certificate revocation handling. This is done via huge Certificate Revocation Lists which are both inconvenient and expencive. Several improvements to these lists are proposed and in this report we try to analyze them briefly. We conclude that although it is possible to do better than in the original X.509 setting, none of the solutions presented this far is good enough.


title: Self-stabilizing mutual exclusion on a ring, even if K=N

abstract: We show that, contrary to common belief, Dijkstra's self-stabilizing mutual exclusion algorithm on a ring [Dij74,Dij82] also stabilizes when the number of states per node is one less than the number of nodes on the ring.


title: Reasoning About Common Knowledge with Infinitely Many Agents

abstract: Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G - G', where G and G' are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.


title: A decision-theoretic approach to reliable message delivery

abstract: We argue that the tools of decision theory need to be taken more seriously in the specification and analysis of systems. We illustrate this by considering a simple problem involving reliable communication, showing how considerations of utility and probability can be used to decide when it is worth sending heartbeat messages and, if they are sent, how often they should be sent.


title: Least expected cost query optimization: an exercise in utility

abstract: We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of the chosen evaluation plans. One assumption is that it is enough to optimize for the expected case---that is, the case where various parameters (like available memory) take on their expected value. The other assumption is that the parameters are constant throughout the execution of the query. We present an algorithm based on the ``System R''-style query optimization algorithm that does not rely on these assumptions. The algorithm we present chooses the plan of the least expected cost instead of the plan of least cost given some fixed value of the parameters. In execution environments that exhibit a high degree of variability, our techniques should result in better performance.


title: Finding an ordinary conic and an ordinary hyperplane

abstract: Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ordinary line. An efficient algorithm for computing such a line was proposed by Mukhopadhyay et al. In this note we extend this result in two directions. We first show how to use this algorithm to compute an ordinary conic, that is, a conic passing through exactly five points, assuming that all the points do not lie on the same conic. Both our proofs of existence and the consequent algorithms are simpler than previous ones. We next show how to compute an ordinary hyperplane in three and higher dimensions.


title: Geometric compression for progressive transmission

abstract: The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of them the following approach: the vertices of the mesh are coded in an order such that it contains partially the topology of the mesh. In the same time, some simple rules attempt to predict the position of the current vertex from the positions of its neighbours that have been previously coded. In this article, we describe a compression algorithm whose principle is completely different: the order of the vertices is used to compress their coordinates, and then the topology of the mesh is reconstructed from the vertices. This algorithm, particularly suited for terrain models, achieves compression factors that are slightly greater than those of the currently available algorithms, and moreover, it allows progressive and interactive transmission of the meshes.


title: Knowledge in Multi-Agent Systems: Initial Configurations and Broadcast

abstract: The semantic framework for the modal logic of knowledge due to Halpern and Moses provides a way to ascribe knowledge to agents in distributed and multi-agent systems. In this paper we study two special cases of this framework: full systems and hypercubes. Both model static situations in which no agent has any information about another agent's state. Full systems and hypercubes are an appropriate model for the initial configurations of many systems of interest. We establish a correspondence between full systems and hypercube systems and certain classes of Kripke frames. We show that these classes of systems correspond to the same logic. Moreover, this logic is also the same as that generated by the larger class of weakly directed frames. We provide a sound and complete axiomatization, S5WDn, of this logic. Finally, we show that under certain natural assumptions, in a model where knowledge evolves over time, S5WDn characterizes the properties of knowledge not just at the initial configuration, but also at all later configurations. In particular, this holds for homogeneous broadcast systems, which capture settings in which agents are initially ignorant of each others local states, operate synchronously, have perfect recall and can communicate only by broadcasting.


title: Query Order

abstract: We study the effect of query order on computational power, and show that $\pjk$-the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy-equals $\redttnp{j+2k-1}$ if j is even and k is odd, and equals $\redttnp{j+2k}$ otherwise. Thus, unless the polynomial hierarchy collapses, it holds that for each $1\leq j \leq k$: $\pjk = \pkj \iff (j=k) \lor (j{is even} \land k=j+1)$. We extend our analysis to apply to more general query classes.


title: Fixed-parameter tractability, definability, and model checking

abstract: In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t >= 0 we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy. On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi Theorem characterizing the class PTIME in terms of definability in least fixed-point logic.


title: What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses

abstract: During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what beforehand were thought to be) lower complexity levels. For example, for each $k\geq 2$ it is now known that if $\psigkone=\psigktwo$ then $\ph=\sigmak$. This article surveys the history, the results, and the technique---the so-called easy-hard method---of these nine papers.


title: R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness

abstract: Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely a downward closure of NP, \rsnnp - has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that \rsnnp has many equivalent forms having to do with ordered and parallel access to $\np$ and $\npinterconp$.


title: An Introduction to Query Order

abstract: Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the polynomial hierarchy collapses-for both the polynomial hierarchy and the boolean hierarchy. In the polynomial hierarchy, query order never matters. In the boolean hierarchy, query order sometimes does not matter and, unless the polynomial hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.


title: Query Order and the Polynomial Hierarchy

abstract: Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed. The present paper studies, for the first time, query order as it applies to the levels of the polynomial hierarchy. We prove that the levels of the polynomial hierarchy are order-oblivious. Yet, we also show that these ordered query classes form new levels in the polynomial hierarchy unless the polynomial hierarchy collapses. We prove that all leaf language classes - and thus essentially all standard complexity classes - inherit all order-obliviousness results that hold for P.


title: Self-Specifying Machines

abstract: We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natural variant accepts exactly the languages that $\manyonesharp$-reduce to P sets. We show that these two classes coincide if and only if $\psone = \psnnoplusbigohone$, where the latter class denotes the sets acceptable via at most one question to $\sharpp$ followed by at most a constant number of questions to $\np$.


title: A Downward Collapse within the Polynomial Hierarchy

abstract: Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k > 2, if $\psigkone = \psigktwo$ then $\sigmak = \pik = \ph$. We extend this to obtain a more general downward collapse result.


title: Translating Equality Downwards

abstract: Downward translation of equality refers to cases where a collapse of some pair of complexity classes would induce a collapse of some other pair of complexity classes that (a priori) one expects are smaller. Recently, the first downward translation of equality was obtained that applied to the polynomial hierarchy-in particular, to bounded access to its levels [cs.CC/9910007]. In this paper, we provide a much broader downward translation that extends not only that downward translation but also that translation's elegant enhancement by Buhrman and Fortnow. Our work also sheds light on previous research on the structure of refined polynomial hierarchies, and strengthens the connection between the collapse of bounded query hierarchies and the collapse of the polynomial hierarchy.


title: Locked and Unlocked Polygonal Chains in 3D

abstract: In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a simple orthogonal projection onto some plane, it can be straightened. For closed chains, we show that there are unknotted but locked closed chains, and we provide an algorithm for convexifying a planar simple polygon in 3D. All our algorithms require only O(n) basic ``moves'' and run in linear time.


title: Communication Complexity Lower Bounds by Polynomials

abstract: The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the log-rank lower bound extends to the strongest model (qubit communication + unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log-rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.


title: A statistical model for word discovery in child directed speech

abstract: A statistical model for segmentation and word discovery in child directed speech is presented. An incremental unsupervised learning algorithm to infer word boundaries based on this model is described and results of empirical tests showing that the algorithm is competitive with other models that have been used for similar tasks are also presented.


title: The Complexity of Temporal Logic over the Reals

abstract: It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete.


title: Map Graphs

abstract: 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, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point.


title: Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic

abstract: The logic of equality with uninterpreted functions (EUF) provides a means of abstracting the manipulation of data by a processor when verifying the correctness of its control logic. By reducing formulas in this logic to propositional formulas, we can apply Boolean methods such as Ordered Binary Decision Diagrams (BDDs) and Boolean satisfiability checkers to perform the verification. We can exploit characteristics of the formulas describing the verification conditions to greatly simplify the propositional formulas generated. In particular, we exploit the property that many equations appear only in positive form. We can therefore reduce the set of interpretations of the function symbols that must be considered to prove that a formula is universally valid to those that are ``maximally diverse.'' We present experimental results demonstrating the efficiency of this approach when verifying pipelined processors using the method proposed by Burch and Dill.


title: PIPE: Personalizing Recommendations via Partial Evaluation

abstract: It is shown that personalization of web content can be advantageously viewed as a form of partial evaluation --- a technique well known in the programming languages community. The basic idea is to model a recommendation space as a program, then partially evaluate this program with respect to user preferences (and features) to obtain specialized content. This technique supports both content-based and collaborative approaches, and is applicable to a range of applications that require automatic information integration from multiple web sources. The effectiveness of this methodology is illustrated by two example applications --- (i) personalizing content for visitors to the Blacksburg Electronic Village (http://www.bev.net), and (ii) locating and selecting scientific software on the Internet. The scalability of this technique is demonstrated by its ability to interface with online web ontologies that index thousands of web pages.


title: Probabilistic Agent Programs

abstract: Agents are small programs that autonomously take actions based on changes in their environment or ``state.'' Over the last few years, there have been an increasing number of efforts to build agents that can interact and/or collaborate with other agents. In one of these efforts, Eiter, Subrahmanian amd Pick (AIJ, 108(1-2), pages 179-255) have shown how agents may be built on top of legacy code. However, their framework assumes that agent states are completely determined, and there is no uncertainty in an agent's state. Thus, their framework allows an agent developer to specify how his agents will react when the agent is 100% sure about what is true/false in the world state. In this paper, we propose the concept of a \emph{probabilistic agent program} and show how, given an arbitrary program written in any imperative language, we may build a declarative ``probabilistic'' agent program on top of it which supports decision making in the presence of uncertainty. We provide two alternative semantics for probabilistic agent programs. We show that the second semantics, though more epistemically appealing, is more complex to compute. We provide sound and complete algorithms to compute the semantics of \emph{positive} agent programs.


title: Finite-resolution hidden surface removal

abstract: We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in Real^3 and p sample points (``pixels'') in the xy-plane, determine the first triangle directly behind each pixel. Our algorithm constructs the sampled visibility map of the triangles with respect to the pixels, which is the subset of the trapezoids in a trapezoidal decomposition of the analytic visibility map that contain at least one pixel. The sampled visibility map adapts to local changes in image complexity, and its complexity is bounded both by the number of pixels and by the complexity of the analytic visibility map. Our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + p), where t is the output size and e is any positive constant. This is nearly optimal in the worst case and compares favorably with the best output-sensitive algorithms for both ray casting and analytic hidden surface removal. In the special case where the pixels form a regular grid, a sweepline variant of our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + t log p), which is usually sublinear in the number of pixels.


title: Decoupling Control from Data for TCP Congestion Control

abstract: Many applications want to use TCP congestion control to regulate the transmission rate of a data packet stream. A natural way to achieve this goal is to transport the data packet stream on a TCP connection. However, because TCP implements both congestion and error control, transporting a data packet stream directly using a TCP connection forces the data packet stream to be subject to TCP's other properties caused by TCP error control, which may be inappropriate for these applications. The TCP decoupling approach proposed in this thesis is a novel way of applying TCP congestion control to a data packet stream without actually transporting the data packet stream on a TCP connection. Instead, a TCP connection using the same network path as the data packet stream is set up separately and the transmission rate of the data packet stream is then associated with that of the TCP packets. Since the transmission rate of these TCP packets is under TCP congestion control, so is that of the data packet stream. Furthermore, since the data packet stream is not transported on a TCP connection, the regulated data packet stream is not subject to TCP error control. Because of this flexibility, the TCP decoupling approach opens up many new opportunities, solves old problems, and improves the performance of some existing applications. All of these advantages will be demonstrated in the thesis. This thesis presents the design, implementation, and analysis of the TCP decoupling approach, and its successful applications in TCP trunking, wireless communication, and multimedia streaming.


title: Consistent Checkpointing in Distributed Databases: Towards a Formal Approach

abstract: Whether it is for audit or for recovery purposes, data checkpointing is an important problem of distributed database systems. Actually, transactions establish dependence relations on data checkpoints taken by data object managers. So, given an arbitrary set of data checkpoints (including at least a single data checkpoint from a data manager, and at most a data checkpoint from each data manager), an important question is the following one: ``Can these data checkpoints be members of a same consistent global checkpoint?''. This paper answers this question by providing a necessary and sufficient condition suited for database systems. Moreover, to show the usefulness of this condition, two {\em non-intrusive} data checkpointing protocols are derived from this condition. It is also interesting to note that this paper, by exhibiting ``correspondences'', establishes a bridge between the data object/transaction model and the process/message-passing model.


title: Selective Sampling for Example-based Word Sense Disambiguation

abstract: This paper proposes an efficient example sampling method for example-based word sense disambiguation systems. To construct a database of practical size, a considerable overhead for manual sense disambiguation (overhead for supervision) is required. In addition, the time complexity of searching a large-sized database poses a considerable problem (overhead for search). To counter these problems, our method selectively samples a smaller-sized effective subset from a given example set for use in word sense disambiguation. Our method is characterized by the reliance on the notion of training utility: the degree to which each example is informative for future example sampling when used for the training of the system. The system progressively collects examples by selecting those with greatest utility. The paper reports the effectiveness of our method through experiments on about one thousand sentences. Compared to experiments with other example sampling methods, our method reduced both the overhead for supervision and the overhead for search, without the degeneration of the performance of the system.


title: Efficient and Extensible Algorithms for Multi Query Optimization

abstract: Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expressions, either within a single query, or across multiple such queries run as a batch. Multi-query optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space. In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy, and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly. Our algorithms are designed to be easily added to existing optimizers. We present a performance study comparing the algorithms, using workloads consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.


title: Practical experiments with regular approximation of context-free languages

abstract: Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the original context-free language. Some of these methods of regular approximation are new, and some others are presented here in a more refined form with respect to existing literature. Practical experiments with the different methods of regular approximation are performed for spoken-language input: hypotheses from a speech recognizer are filtered through a finite automaton.


title: A System of Interaction and Structure

abstract: This paper introduces a logical system, called BV, which extends multiplicative linear logic by a non-commutative self-dual logical operator. This extension is particularly challenging for the sequent calculus, and so far it is not achieved therein. It becomes very natural in a new formalism, called the calculus of structures, which is the main contribution of this work. Structures are formulae submitted to certain equational laws typical of sequents. The calculus of structures is obtained by generalising the sequent calculus in such a way that a new top-down symmetry of derivations is observed, and it employs inference rules that rewrite inside structures at any depth. These properties, in addition to allow the design of BV, yield a modular proof of cut elimination.


title: On Reconfiguring Tree Linkages: Trees can Lock

abstract: It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an $N$-link tree can have $2^{\Omega(N)}$ equivalence classes of configurations.


title: Semantics of Programming Languages: A Tool-Oriented Approach

abstract: By paying more attention to semantics-based tool generation, programming language semantics can significantly increase its impact. Ultimately, this may lead to ``Language Design Assistants'' incorporating substantial amounts of semantic knowledge.


title: Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series

abstract: Generalizations of numeration systems in which N is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L over a finite alphabet A. For these systems, we obtain a characterization of recognizable sets of integers in terms of rational formal series. We also show that, if the complexity of L is Theta (n^q) (resp. if L is the complement of a polynomial language), then multiplication by an integer k preserves recognizability only if k=t^{q+1} (resp. if k is not a power of the cardinality of A) for some integer t. Finally, we obtain sufficient conditions for the notions of recognizability and U-recognizability to be equivalent, where U is some positional numeration system related to a sequence of integers.


title: Subgraph Isomorphism in Planar Graphs and Related Problems

abstract: We solve the subgraph isomorphism problem in planar graphs in linear time, for any pattern of constant size. Our results are based on a technique of partitioning the planar graph into pieces of small tree-width, and applying dynamic programming within each piece. The same methods can be used to solve other planar graph problems including connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths.


title: Graph Ramsey games

abstract: We consider combinatorial avoidance and achievement games based on graph Ramsey theory: The players take turns in coloring still uncolored edges of a graph G, each player being assigned a distinct color, choosing one edge per move. In avoidance games, completing a monochromatic subgraph isomorphic to another graph A leads to immediate defeat or is forbidden and the first player that cannot move loses. In the avoidance+ variants, both players are free to choose more than one edge per move. In achievement games, the first player that completes a monochromatic subgraph isomorphic to A wins. Erdos & Selfridge (1973) were the first to identify some tractable subcases of these games, followed by a large number of further studies. We complete these investigations by settling the complexity of all unrestricted cases: We prove that general graph Ramsey avoidance, avoidance+, and achievement games and several variants thereof are PSPACE-complete. We ultra-strongly solve some nontrivial instances of graph Ramsey avoidance games that are based on symmetric binary Ramsey numbers and provide strong evidence that all other cases based on symmetric binary Ramsey numbers are effectively intractable. Keywords: combinatorial games, graph Ramsey theory, Ramsey game, PSPACE-completeness, complexity, edge coloring, winning strategy, achievement game, avoidance game, the game of Sim, Polya's enumeration formula, probabilistic counting, machine learning, heuristics, Java applet


title: What Next? A Dozen Information-Technology Research Goals

abstract: Charles Babbage's vision of computing has largely been realized. We are on the verge of realizing Vannevar Bush's Memex. But, we are some distance from passing the Turing Test. These three visions and their associated problems have provided long-range research goals for many of us. For example, the scalability problem has motivated me for several decades. This talk defines a set of fundamental research problems that broaden the Babbage, Bush, and Turing visions. They extend Babbage's computational goal to include highly-secure, highly-available, self-programming, self-managing, and self-replicating systems. They extend Bush's Memex vision to include a system that automatically organizes, indexes, digests, evaluates, and summarizes information (as well as a human might). Another group of problems extends Turing's vision of intelligent machines to include prosthetic vision, speech, hearing, and other senses. Each problem is simply stated and each is orthogonal from the others, though they share some common core technologies


title: Question Answering System Using Syntactic Information

abstract: Question answering task is now being done in TREC8 using English documents. We examined question answering task in Japanese sentences. Our method selects the answer by matching the question sentence with knowledge-based data written in natural language. We use syntactic information to obtain highly accurate answers.


title: One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties

abstract: We survey recent developments in the study of (worst-case) one-way functions having strong algebraic and security properties. According to [RS93], this line of research was initiated in 1984 by Rivest and Sherman who designed two-party secret-key agreement protocols that use strongly noninvertible, total, associative one-way functions as their key building blocks. If commutativity is added as an ingredient, these protocols can be used by more than two parties, as noted by Rabi and Sherman [RS93] who also developed digital signature protocols that are based on such enhanced one-way functions. Until recently, it was an open question whether one-way functions having the algebraic and security properties that these protocols require could be created from any given one-way function. Recently, Hemaspaandra and Rothe [HR99] resolved this open issue in the affirmative, by showing that one-way functions exist if and only if strong, total, commutative, associative one-way functions exist. We discuss this result, and the work of Rabi, Rivest, and Sherman, and recent work of Homan [Hom99] that makes progress on related issues.


title: On quantum and classical space-bounded processes with algebraic transition amplitudes

abstract: We define a class of stochastic processes based on evolutions and measurements of quantum systems, and consider the complexity of predicting their long-term behavior. It is shown that a very general class of decision problems regarding these stochastic processes can be efficiently solved classically in the space-bounded case. The following corollaries are implied by our main result: (1) Any space O(s) uniform family of quantum circuits acting on s qubits and consisting of unitary gates and measurement gates defined in a typical way by matrices of algebraic numbers can be simulated by an unbounded error space O(s) ordinary (i.e., fair-coin flipping) probabilistic Turing machine, and hence by space O(s) uniform classical (deterministic) circuits of depth O(s^2) and size 2^(O(s)). The quantum circuits are not required to operate with bounded error and may have depth exponential in s. (2) Any (unbounded error) quantum Turing machine running in space s, having arbitrary algebraic transition amplitudes, allowing unrestricted measurements during its computation, and having no restrictions on running time can be simulated by an unbounded error space O(s) ordinary probabilistic Turing machine, and hence deterministically in space O(s^2).


title: Two-way finite automata with quantum and classical states

abstract: We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implement than unrestricted 2qfa's; the internal state of a 2qcfa may include a quantum part that may be in a (mixed) quantum state, but the tape head position is required to be classical. We show two languages for which 2qcfa's are better than classical 2-way automata. First, 2qcfa's can recognize palindromes, a language that cannot be recognized by 2-way deterministic or probabilistic finite automata. Second, in polynomial time 2qcfa's can recognize {a^n b^n | n>=0}, a language that can be recognized classically by a 2-way probabilistic automaton but only in exponential time.


title: The Sources of Certainty in Computation and Formal Systems

abstract: In his Discourse on the Method of Rightly Conducting the Reason, and Seeking Truth in the Sciences, Rene Descartes sought ``clear and certain knowledge of all that is useful in life.'' Almost three centuries later, in ``The foundations of mathematics,'' David Hilbert tried to ``recast mathematical definitions and inferences in such a way that they are unshakable.'' Hilbert's program relied explicitly on formal systems (equivalently, computational systems) to provide certainty in mathematics. The concepts of computation and formal system were not defined in his time, but Descartes' method may be understood as seeking certainty in essentially the same way. In this article, I explain formal systems as concrete artifacts, and investigate the way in which they provide a high level of certainty---arguably the highest level achievable by rational discourse. The rich understanding of formal systems achieved by mathematical logic and computer science in this century illuminates the nature of programs, such as Descartes' and Hilbert's, that seek certainty through rigorous analysis.


title: One-Level Prosodic Morphology

abstract: Recent developments in theoretical linguistics have lead to a widespread acceptance of constraint-based analyses of prosodic morphology phenomena such as truncation, infixation, floating morphemes and reduplication. Of these, reduplication is particularly challenging for state-of-the-art computational morphology, since it involves copying of some part of a phonological string. In this paper I argue for certain extensions to the one-level model of phonology and morphology (Bird & Ellison 1994) to cover the computational aspects of prosodic morphology using finite-state methods. In a nutshell, enriched lexical representations provide additional automaton arcs to repeat or skip sounds and also to allow insertion of additional material. A kind of resource consciousness is introduced to control this additional freedom, distinguishing between producer and consumer arcs. The non-finite-state copying aspect of reduplication is mapped to automata intersection, itself a non-finite-state operation. Bounded local optimization prunes certain automaton arcs that fail to contribute to linguistic optimisation criteria. The paper then presents implemented case studies of Ulwa construct state infixation, German hypocoristic truncation and Tagalog over-applying reduplication that illustrate the expressive power of this approach, before its merits and limitations are discussed and possible extensions are sketched. I conclude that the one-level approach to prosodic morphology presents an attractive way of extending finite-state techniques to difficult phenomena that hitherto resisted elegant computational analyses.


title: Cox's Theorem Revisited

abstract: The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong and, arguably, not natural.


title: PushPush is NP-hard in 3D

abstract: We prove that a particular pushing-blocks puzzle is intractable in 3D. The puzzle, inspired by the game PushPush, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 3D by reduction from SAT. The corresponding problem in 2D remains open.


title: The Complexity of Poor Man's Logic

abstract: Motivated by description logics, we investigate what happens to the complexity of modal satisfiability problems if we only allow formulas built from literals, $\wedge$, $\Diamond$, and $\Box$. Previously, the only known result was that the complexity of the satisfiability problem for K dropped from PSPACE-complete to coNP-complete (Schmidt-Schauss and Smolka, 1991 and Donini et al., 1992). In this paper we show that not all modal logics behave like K. In particular, we show that the complexity of the satisfiability problem with respect to frames in which each world has at least one successor drops from PSPACE-complete to P, but that in contrast the satisfiability problem with respect to the class of frames in which each world has at most two successors remains PSPACE-complete. As a corollary of the latter result, we also solve the open problem from Donini et al.'s complexity classification of description logics (Donini et al., 1997). In the last section, we classify the complexity of the satisfiability problem for K for all other restrictions on the set of operators.


title: The phase transition in random Horn satisfiability and its algorithmic implications

abstract: Let c>0 be a constant, and $\Phi$ be a random Horn formula with n variables and $m=c\cdot 2^{n}$ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing \PUR, a natural implementation of positive unit resolution, we show that $\lim_{n\goesto \infty} \PR ({$\Phi$ is satisfiable})= 1-F(e^{-c})$, where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)... $. Our method also yields as a byproduct an average-case analysis of this algorithm.


title: A Geometric Model for Information Retrieval Systems

abstract: This decade has seen a great deal of progress in the development of information retrieval systems. Unfortunately, we still lack a systematic understanding of the behavior of the systems and their relationship with documents. In this paper we present a completely new approach towards the understanding of the information retrieval systems. Recently, it has been observed that retrieval systems in TREC 6 show some remarkable patterns in retrieving relevant documents. Based on the TREC 6 observations, we introduce a geometric linear model of information retrieval systems. We then apply the model to predict the number of relevant documents by the retrieval systems. The model is also scalable to a much larger data set. Although the model is developed based on the TREC 6 routing test data, I believe it can be readily applicable to other information retrieval systems. In Appendix, we explained a simple and efficient way of making a better system from the existing systems.


title: Resolution of Indirect Anaphora in Japanese Sentences Using Examples 'X no Y (Y of X)'

abstract: A noun phrase can indirectly refer to an entity that has already been mentioned. For example, ``I went into an old house last night. The roof was leaking badly and ...'' indicates that ``the roof'' is associated with `` an old house}'', which was mentioned in the previous sentence. This kind of reference (indirect anaphora) has not been studied well in natural language processing, but is important for coherence resolution, language understanding, and machine translation. In order to analyze indirect anaphora, we need a case frame dictionary for nouns that contains knowledge of the relationships between two nouns but no such dictionary presently exists. Therefore, we are forced to use examples of ``X no Y'' (Y of X) and a verb case frame dictionary instead. We tried estimating indirect anaphora using this information and obtained a recall rate of 63% and a precision rate of 68% on test sentences. This indicates that the information of ``X no Y'' is useful to a certain extent when we cannot make use of a noun case frame dictionary. We estimated the results that would be given by a noun case frame dictionary, and obtained recall and precision rates of 71% and 82% respectively. Finally, we proposed a way to construct a noun case frame dictionary by using examples of ``X no Y.''


title: Pronoun Resolution in Japanese Sentences Using Surface Expressions and Examples

abstract: In this paper, we present a method of estimating referents of demonstrative pronouns, personal pronouns, and zero pronouns in Japanese sentences using examples, surface expressions, topics and foci. Unlike conventional work which was semantic markers for semantic constraints, we used examples for semantic constraints and showed in our experiments that examples are as useful as semantic markers. We also propose many new methods for estimating referents of pronouns. For example, we use the form ``X of Y'' for estimating referents of demonstrative adjectives. In addition to our new methods, we used many conventional methods. As a result, experiments using these methods obtained a precision rate of 87% in estimating referents of demonstrative pronouns, personal pronouns, and zero pronouns for training sentences, and obtained a precision rate of 78% for test sentences.


title: An Estimate of Referent of Noun Phrases in Japanese Sentences

abstract: In machine translation and man-machine dialogue, it is important to clarify referents of noun phrases. We present a method for determining the referents of noun phrases in Japanese sentences by using the referential properties, modifiers, and possessors of noun phrases. Since the Japanese language has no articles, it is difficult to decide whether a noun phrase has an antecedent or not. We had previously estimated the referential properties of noun phrases that correspond to articles by using clue words in the sentences. By using these referential properties, our system determined the referents of noun phrases in Japanese sentences. Furthermore we used the modifiers and possessors of noun phrases in determining the referents of noun phrases. As a result, on training sentences we obtained a precision rate of 82% and a recall rate of 85% in the determination of the referents of noun phrases that have antecedents. On test sentences, we obtained a precision rate of 79% and a recall rate of 77%.


title: Resolution of Verb Ellipsis in Japanese Sentence using Surface Expressions and Examples

abstract: Verbs are sometimes omitted in Japanese sentences. It is necessary to recover omitted verbs for purposes of language understanding, machine translation, and conversational processing. This paper describes a practical way to recover omitted verbs by using surface expressions and examples. We experimented the resolution of verb ellipses by using this information, and obtained a recall rate of 73% and a precision rate of 66% on test sentences.


title: An Example-Based Approach to Japanese-to-English Translation of Tense, Aspect, and Modality

abstract: We have developed a new method for Japanese-to-English translation of tense, aspect, and modality that uses an example-based method. In this method the similarity between input and example sentences is defined as the degree of semantic matching between the expressions at the ends of the sentences. Our method also uses the k-nearest neighbor method in order to exclude the effects of noise; for example, wrongly tagged data in the bilingual corpora. Experiments show that our method can translate tenses, aspects, and modalities more accurately than the top-level MT software currently available on the market can. Moreover, it does not require hand-craft rules.


title: New Error Bounds for Solomonoff Prediction

abstract: Solomonoff sequence prediction is a scheme to predict digits of binary strings without knowing the underlying probability distribution. We call a prediction scheme informed when it knows the true probability distribution of the sequence. Several new relations between universal Solomonoff sequence prediction and informed prediction and general probabilistic prediction schemes will be proved. Among others, they show that the number of errors in Solomonoff prediction is finite for computable distributions, if finite in the informed case. Deterministic variants will also be studied. The most interesting result is that the deterministic variant of Solomonoff prediction is optimal compared to any other probabilistic or deterministic prediction scheme apart from additive square root corrections only. This makes it well suited even for difficult prediction problems, where it does not suffice when the number of errors is minimal to within some factor greater than one. Solomonoff's original bound and the ones presented here complement each other in a useful way.


title: Deduction over Mixed-Level Logic Representations for Text Passage Retrieval

abstract: A system is described that uses a mixed-level representation of (part of) meaning of natural language documents (based on standard Horn Clause Logic) and a variable-depth search strategy that distinguishes between the different levels of abstraction in the knowledge representation to locate specific passages in the documents. Mixed-level representations as well as variable-depth search strategies are applicable in fields outside that of NLP.


title: Scalability Terminology: Farms, Clones, Partitions, Packs, RACS and RAPS

abstract: Defines a vocabulary for scaleable systems: Geoplexes, Farms, Clones, RACS, RAPS, clones, partitions, and packs and dicusses the design tradeoffs of using clones, partitons, and packs.


title: Adaptivity in Agent-Based Routing for Data Networks

abstract: Adaptivity, both of the individual agents and of the interaction structure among the agents, seems indispensable for scaling up multi-agent systems (MAS's) in noisy environments. One important consideration in designing adaptive agents is choosing their action spaces to be as amenable as possible to machine learning techniques, especially to reinforcement learning (RL) techniques. One important way to have the interaction structure connecting agents itself be adaptive is to have the intentions and/or actions of the agents be in the input spaces of the other agents, much as in Stackelberg games. We consider both kinds of adaptivity in the design of a MAS to control network packet routing. We demonstrate on the OPNET event-driven network simulator the perhaps surprising fact that simply changing the action space of the agents to be better suited to RL can result in very large improvements in their potential performance: at their best settings, our learning-amenable router agents achieve throughputs up to three and one half times better than that of the standard Bellman-Ford routing algorithm, even when the Bellman-Ford protocol traffic is maintained. We then demonstrate that much of that potential improvement can be realized by having the agents learn their settings when the agent interaction structure is itself adaptive.


title: Avoiding Braess' Paradox through Collective Intelligence

abstract: In an Ideal Shortest Path Algorithm (ISPA), at each moment each router in a network sends all of its traffic down the path that will incur the lowest cost to that traffic. In the limit of an infinitesimally small amount of traffic for a particular router, its routing that traffic via an ISPA is optimal, as far as cost incurred by that traffic is concerned. We demonstrate though that in many cases, due to the side-effects of one router's actions on another routers performance, having routers use ISPA's is suboptimal as far as global aggregate cost is concerned, even when only used to route infinitesimally small amounts of traffic. As a particular example of this we present an instance of Braess' paradox for ISPA's, in which adding new links to a network decreases overall throughput. We also demonstrate that load-balancing, in which the routing decisions are made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to "side-effects", in this case of current routing decision on future traffic. The theory of COllective INtelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects. We present key concepts from that theory and use them to derive an idealized algorithm whose performance is better than that of the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm avoids Braess' paradox.


title: Multivariate Regression Depth

abstract: The regression depth of a hyperplane with respect to a set of n points in R^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d-1. The k=0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat.


title: Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs

abstract: We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs, we show how to insert and delete objects from an n-object set, maintaining the closest pair, in O(n log^2 n) time per update and O(n) space. With quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, O(n) per update. We apply these data structures to hierarchical clustering, greedy matching, and TSP heuristics, and discuss other potential applications in machine learning, Groebner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics.


title: Comparative Analysis of Five XML Query Languages

abstract: XML is becoming the most relevant new standard for data representation and exchange on the WWW. Novel languages for extracting and restructuring the XML content have been proposed, some in the tradition of database query languages (i.e. SQL, OQL), others more closely inspired by XML. No standard for XML query language has yet been decided, but the discussion is ongoing within the World Wide Web Consortium and within many academic institutions and Internet-related major companies. We present a comparison of five, representative query languages for XML, highlighting their common features and differences.


title: HMM Specialization with Selective Lexicalization

abstract: We present a technique which complements Hidden Markov Models by incorporating some lexicalized states representing syntactically uncommon words. Our approach examines the distribution of transitions, selects the uncommon words, and makes lexicalized states for the words. We performed a part-of-speech tagging experiment on the Brown corpus to evaluate the resultant language model and discovered that this technique improved the tagging accuracy by 0.21% at the 95% level of confidence.


title: Mixed-Level Knowledge Representation and Variable-Depth Inference in Natural Language Processing

abstract: A system is described that uses a mixed-level knowledge representation based on standard Horn Clause Logic to represent (part of) the meaning of natural language documents. A variable-depth search strategy is outlined that distinguishes between the different levels of abstraction in the knowledge representation to locate specific passages in the documents. A detailed description of the linguistic aspects of the system is given. Mixed-level representations as well as variable-depth search strategies are applicable in fields outside that of NLP.


title: Computation in an algebra of test selection criteria

abstract: One of the key concepts in testing is that of adequate test sets. A test selection criterion decides which test sets are adequate. In this paper, a language schema for specifying a large class of test selection criteria is developed; the schema is based on two operations for building complex criteria from simple ones. Basic algebraic properties of the two operations are derived. In the second part of the paper, a simple language-an instance of the general schema-is studied in detail, with the goal of generating small adequate test sets automatically. It is shown that one version of the problem is intractable, while another is solvable by an efficient algorithm. An implementation of the algorithm is described.


title: Quantum Bit Commitment Expansion

abstract: The paper was retracted.


title: Additive models in high dimensions

abstract: We discuss some aspects of approximating functions on high-dimensional data sets with additive functions or ANOVA decompositions, that is, sums of functions depending on fewer variables each. It is seen that under appropriate smoothness conditions, the errors of the ANOVA decompositions are of order $O(n^{m/2})$ for approximations using sums of functions of up to $m$ variables under some mild restrictions on the (possibly dependent) predictor variables. Several simulated examples illustrate this behaviour.


title: Seeing the Forest in the Tree: Applying VRML to Mathematical Problems in Number Theory

abstract: We show how VRML (Virtual Reality Modeling Language) can provide potentially powerful insight into the 3x + 1 problem via the introduction of a unique geometrical object, called the 'G-cell', akin to a fractal generator. We present an example of a VRML world developed programmatically with the G-cell. The role of VRML as a tool for furthering the understanding the 3x+1 problem is potentially significant for several reasons: a) VRML permits the observer to zoom into the geometric structure at all scales (up to limitations of the computing platform). b) VRML enables rotation to alter comparative visual perspective (similar to Tukey's data-spinning concept). c) VRML facilitates the demonstration of interesting tree features between collaborators on the internet who might otherwise have difficulty conveying their ideas unambiguously. d) VRML promises to reveal any dimensional dependencies among 3x+1 sequences.


title: On extremals with prescribed Lagrangian densities

abstract: Consider two manifolds~$M^m$ and $N^n$ and a first-order Lagrangian $L(u)$ for mappings $u:M\to N$, i.e., $L$ is an expression involving $u$ and its first derivatives whose value is an $m$-form (or more generally, an $m$-density) on~$M$. One is usually interested in describing the extrema of the functional $\Cal L(u) = \int_M L(u)$, and these are characterized locally as the solutions of the Euler-Lagrange equation~$E_L(u)=0$ associated to~$L$. In this note I will discuss three problems which can be understood as trying to determine how many solutions exist to the Euler-Lagrange equation which also satisfy $L(u) = \Phi$, where $\Phi$ is a specified $m$-form or $m$-density on~$M$. The first problem, which is solved completely, is to determine when two minimal graphs over a domain in the plane can induce the same area form without merely differing by a vertical translation or reflection. The second problem, described more fully below, arose in Professor Calabi's study of extremal isosystolic metrics on surfaces. The third problem, also solved completely, is to determine the (local) harmonic maps between spheres which have constant energy density.


title: Characteristic Numbers and Generalized Path Integrals

abstract: This is an extended write-up of a talk given in April, 1993 in honor of Raoul Bott's 70th birthday. We first illustrate how some traditional topological and geometric invariants obey ``gluing laws'' inspired by those in classical and quantum field theory. Here we discuss characteristic numbers, particularly the Euler number of a complex line bundle over an oriented surface. In the second part of the paper we show how path integrals give rise to invariants which obey gluing laws. The argument is formal in general, but for a particular example of invariants related to finite groups it is rigorous. In that ``toy model'' we show how to go further and generalize the path integral to obtain more exotic gluing laws. This idea was used--at least in this toy model--to directly construct quantum groups from 3 dimensional Chern-Simons invariants.


title: On the Existence of Jenkins-Strebel Differentials Using Harmonic Maps from Surfaces to Graphs

abstract: We give a new proof of the existence (\cite{HM}, \cite{Ren}) of a Jenkins-Strebel differential $\Phi$ on a Riemann surface $\SR$ with prescribed heights of cylinders by considering the harmonic map from $\SR$ to the leaf space of the vertical foliation of $\Phi$, thought of as a Riemannian graph. The novelty of the argument is that it is essentially Riemannian as well as elementary; moreover, the harmonic maps existence theory on which it relies is classical, due mostly to Morrey (\cite{Mo}).


title: Moduli Spaces of Singular Yamabe Metrics

abstract: Complete, conformally flat metrics of constant positive scalar curvature on the complement of $k$ points in the $n$-sphere, $k \ge 2$, $n \ge 3$, were constructed by R\. Schoen [S2]. We consider the problem of determining the moduli space of all such metrics. All such metrics are asymptotically periodic, and we develop the linear analysis necessary to understand the nonlinear problem. This includes a Fredholm theory and asymptotic regularity theory for the Laplacian on asymptotically periodic manifolds, which is of independent interest. The main result is that the moduli space is a locally real analytic variety of dimension $k$. For a generic set of nearby conformal classes the moduli space is shown to be a $k-$dimensional real analytic manifold. The structure as a real analytic variety is obtained by writing the space as an intersection of a Fredholm pair of infinite dimensional real analytic manifolds.


title: $n$-transitivity of certain diffeomorphism groups

abstract: Some groups of real analytic diffeomorphism act n-transitively for each finite n.


title: Basic differential forms for actions of Lie groups

abstract: A section of a Riemannian $G$-manifold $M$ is a closed submanifold $\Sigma$ which meets each orbit orthogonally. It is shown that the algebra of $G$-invariant differential forms on $M$ which are horizontal in the sense that they kill every vector which is tangent to some orbit, is isomorphic to the algebra of those differential forms on $\Sigma$ which are invariant with respect to the generalized Weyl group of this orbit, under some condition.


title: The Spectral Flow of the Odd Signature operator and Higher Massey Products

abstract: We show how to compute the spectral flow of the odd signature operator $\pm *d_{a_t}-d_{a_t}*$ along an analytic path of flat connections $a_t$ on a bundle over a closed odd-dimensional manifold in terms of Massey products in the DGLA of bundle-valued differential forms. To obtain this information, we set up a sequence of cochain complexes $\{\calg^*_n,\delta_n\}$, for $n=0,1,2,\ldots$ and Hermitian forms $$Q_n:\calg_n\times\calg_n\ra \bbbC$$ whose signatures determine the spectral flow through $t=0$. The complexes and Hermitian forms are constructed using Massey products.


title: Teichmuller Space is Not Gromov Hyperbolic

abstract: We prove that the Teichmuller Space of Riemann Surfaces of genus g>1, equipped with the Teichmuller metric, is not a Gromov Hyperbolic space.


title: A ``stable'' version of the Gromov-Lawson conjecture

abstract: We discuss a conjecture of Gromov and Lawson, later modified by Rosenberg, concerning the existence of metrics of positive scalar curvature. It says that a closed spin manifold $M$ of dimension $n\ge 5$ has such a metric if and only if the index of a suitable ``Dirac" operator in $KO_n(C^* (\pi_1(M)))$, the real $K$-theory of the group $C^*$-algebra of the fundamental group of $M$, vanishes. It is known that the vanishing of the index is necessary for existence of a positive scalar curvature metric on $M$, but this is known to be a sufficient condition only if $\pi_1(M)$ is the trivial group, $\Bbb Z/2$, an odd order cyclic group, or one of a fairly small class of torsion-free groups. \par We note that the groups $KO_n(C^*(\pi))$ are periodic in $n$ with period $8$, whereas there is no obvious periodicity in the original geometric problem. This leads us to introduce a ``stable'' version of the Gromov-Lawson conjecture, which makes the weaker statement that the product of $M$ with enough copies of the ``Bott manifold" $B$ has a positive scalar curvature metric if and only if the index of the Dirac operator on $M$ vanishes. (Here $B$ is a simply connected $8$-manifold which represents the periodicity element in $KO_8(pt)$.) We prove the stable Gromov-Lawson conjecture for all spin manifolds with finite fundamental group and for many spin manifolds with infinite fundamental group.


title: Proper group actions and symplectic stratified spaces

abstract: Let $(M,\omega)$ be a Hamiltonian $G$-space with a momentum map $F:M \to {\frak g}^*$. It is well-known that if $\alpha$ is a regular value of $F$ and $G$ acts freely and properly on the level set $F^{-1}(G\cdot \alpha)$, then the reduced space $M_\alpha :=F^{-1}(G\cdot \alpha)/G$ is a symplectic manifold. We show that if the regularity assumptions are dropped the space $M_\alpha $ is a union of symplectic manifolds, and that the symplectic manifolds fit together in a nice way. In other words the reduced space is a {\em symplectic stratified space}. This extends results known for the Hamiltonian action of compact groups.


title: Transformation de Fourier-Mukai sur les Surfaces Hyperk\"ahl\'eriennes

abstract: Given two compact hyperk\"ahler surfaces $X$ and $Y$ and a holomorphic vector bundle $Q$ on $X\times Y$, which is a generalized instanton, one can define a Fourier-Mukai transform, which, under suitable assumptions, maps vector bundles on $X$ to vector bundles on $Y$. If $X$ and $Y$ are dual complex tori, this transform maps instantons on $X$ to instantons on $Y$. After a quick review of these results, we define a Fourier-Mukai transform in the case when $X$ is a K3 surface, and study the behaviour of instantons on $X$ under this transform. Hard copies may be mailed on request


title: A note on the index bundle over the moduli space of monopoles

abstract: Donaldson has shown that the moduli space of monopoles $M_k$ is diffeomorphic to the space $\Rat_k$ of based rational maps from the two-sphere to itself. We use this diffeomorphism to give an explicit description of the bundle on $\Rat_k$ obtained by pushing out the index bundle from $M_k$. This gives an alternative and more explicit proof of some earlier results of Cohen and Jones.


title: All regulators of flat bundles are torsion

abstract: I prove the Bloch conjecture:all secondary characteristic classes of flat bundles over complex projective varietes are torsion, except the first.


title: Rationality of secondary classes

abstract: We prove the Bloch conjecture : $ c_2(E) \in H^4_\cald (X,\bbz(2))$ is torsion for holomorphic rank two vector bundles $E$ with an integrable connection over a complex projective variety $X$. We prove also the rationality of the Chern-Simons invariant of compact arithmetic hyperbolic three-manifolds. We give a sharp higher-dimensional Milnor inequality for the volume regulator of all representations to $PSO(1,n)$ of fundamental groups of compact $n$-dimensional hyperbolic manifolds, announced in our earlier paper.


title: Jumps of the eta invariant

abstract: We study the eta-invariant, defined by Atiyah-Patodi-Singer a real valued invariant of an oriented odd-dimensional Riemannian manifold equipped with a unitary representation of its fundamental group. When the representation varies analytically, the corresponding eta-invariant may have an integral jump, known also as the spectral flow. The main result of the paper establishes a formula for this spectral jump in terms of the signatures of some homological forms, defined naturally by the path of representations. These signatures may also be computed by means of a spectral sequence of Hermitian forms,defined by the deformation data. Our theorem on the spectral jump has a generalization to arbitrary analytic families of self-adjoint elliptic operators. As an application we consider the problem of homotopy invariance of the rho-invariant. We give an intrinsic homotopy theoretic definition of the rho-invariant, up to indeterminacy in the form of a locally constant function on the space of unitary representations. In an Appendix, written by S.Weinberger, it is shown (using the results of this paper) that the difference in the rho-invariants of homotopy-equivalent manifolds is always rational.


title: Int\'egration symplectique des vari\'et\'es de Poisson r\'eguli\`eres

abstract: A symplectic integration of a Poisson manifold $(M,\Lambda)$ is a symplectic groupoid $(\Gamma,\eta)$ which realizes the given Poisson manifold, i.e. such that the space of units $\Gamma_0$ with the induced Poisson structure $\Lambda_0$ is isomorphic to $(M,\Lambda)$. This notion was introduced by A. Weinstein in order to quantize Poisson manifolds by quantizing their symplectic integration. Any Poisson manifold can be integrated by a local symplectic groupoid but already for regular Poisson manifolds there are obstructions to global integrability. The aim of this paper is to summarize all the known obstructions and present a sufficient topological condition for integrability of regular Poisson manifolds; we will indeed describe a concrete procedure for this integration. Further our criterion will provide necessary and sufficient if we require $\Gamma$ to be Hausdorff, which is a suitable condition to proceed to Weinstein's program of quantization. These integrability results may be interpreted as an generalization of the Cartan-Smith proof of Lie's third theorem in the infinite dimensional case.


title: Quadratic Equations in Groups from the Global Geometry Viewpoint

abstract: I use harmonic maps and minimal surfaces to study quadratic equations in groups.


title: Pr\'equantification de Certaines Vari\'et\'es de Poisson

abstract: A surjective submersion $\pi : M \to B$ carrying a field of simplectic structures on the fibres is symplectic if this Poisson structure is minimal. A symplectic submersion may be interpreted as a family of mechanical systems depending on a parameter in $B$. We give some conditions to find a closed form which represent the foliated form $\sigma$ gluing the symplectic forms on the fibres. This is the first step to prequantize all these systems at once. We will indeed exhibit an integrality condition which does not depend on the closed form representing $\sigma$: if the fibres are 1-connected and $H^3(B;Z)=0$, then there exists a $S^1$-principal fibre bundle with a connection whose curvature represents $\sigma$ iff the group of spherical periods of $\sigma$ is a discrete subgroup of R. The symplectic integration of a Poisson manifold $(M,\Lambda)$ is a symplectic groupoid $(\Gamma,\eta)$ with 1-connected fibres such that the space of units with the induced Poisson structure is isomorphic to $(M,\Lambda)$. This notion was introduced by A. Weinstein in order to quantize Poisson manifolds by quantizing their symplectic integration. We show that if the symplectic integration is prequantizable, then there exists a unique prequantization which is trivial over $M$. We show that the symplectic integration of a minimal Poisson manifold is prequantizable iff the group of spherical periods is discrete. Moreover we prove that a {\em totally aspherical} Poisson manifold (any vanishing cycle is trivial and the $\pi_2$ of the leaves is zero) is prequantized in the sense of Weinstein by a trivial fibre bundle.


title: Theta and zeta functions for odd-dimensional locally symmetric spaces of rank one

abstract: This paper is a continuation of our work on theta and zeta functions In the previous papers we considered the case of even dimensional rank one symmetric spaces of non-compact type. The present is concerned with the odd-dimensional case, i.e. with odd-dimensional real hyperbolic manifolds. It is the natural appearence of eta invariants in connection with super theta and zeta functions what makes this case particularly interesting. (authors name corrected)


title: Theta and zeta functions for locally symmetric spaces of rank one

abstract: We study the Selberg zeta and the theta function associated to bundles over even-dimensional locally symmetric spaces of rank one.


title: A theta function for hyperbolic surfaces with cusps

abstract: For a Riemann surface with cusps we define a theta function using the eigenvalues of the Laplacian and the singularities of the scattering determinant. We provide its meromorphic continuation and discuss its singularities.


title: Bundle gerbes

abstract: Just as $\Cstar$ principal bundles provide a geometric realisation of two-dimensional integral cohomology; gerbes or sheaves of groupoids, provide a geometric realisation of three dimensional integral cohomology through their Dixmier-Douady class. I consider an alternative, related, geometric realisation of three dimensional cohomology called a bundle gerbe. Every bundle gerbe gives rise to a gerbe and most of the well-known examples examples of gerbes are bundle gerbes. I discuss the properties of bundle gerbes, in particular bundle gerbe connections and curvature and their associated Dixmier-Douady class.


title: Convexity Properties of the Moment Mapping Re-examined

abstract: Consider a Hamiltonian action of a compact Lie group on a compact symplectic manifold. A theorem of Kirwan's says that the image of the momentum mapping intersects the positive Weyl chamber in a convex polytope. I present a new proof of Kirwan's theorem, which gives explicit information on how the vertices of the polytope come about and on how the shape of the polytope near any point can be read off from infinitesimal data on the manifold. It also applies to some interesting classes of noncompact or singular Hamiltonian spaces, such as cotangent bundles and complex affine varieties.


title: Witten deformation of Ray-Singer analytic torsion

abstract: Consider a flat vector bundle F over compact Riemannian manifold M and let f be a self-indexing Morse function on M. Let g be a smooth Euclidean metric on F. Set g_t=exp(-2tf)g and let \rho(t) be the Ray-Singer analytic torsion of F associated to the metric g_t. Assuming that the vector field $grad f$ satisfies the Morse-Smale transversality conditions, we provide an asymptotic expansion for log(\rho(t)) for t\to\infty of the form a_0+a_1t+b log(t)+o(1). We present explicit formulae for coefficients a_0,a_1 and b. In particular, we show that b is a half integer.


title: Modular operads

abstract: Modular operads are a special type of operad: in fact, they bear the same relationship to operads that graphs do to trees (i.e. simply connected graphs). One of the basic examples of a modular operad is the collection of Deligne-Mumford-Knudsen moduli spaces $\bar{M}_{g,n}$ of stable pointed algebraic curves; hence the word ``modular.'' In this paper, we introduce various constructions on differential graded modular operads, notably a duality which we call the Feynman transform, which extends Kontsevich's graph complexes. Our main result is the calculation of the Euler characteristic of the Feynman transform of a modular operad, using the theory of symmetric functions: the result is a generalization of Wick's theorem for Gaussian integrals.


title: The Moduli Space of Complete Embedded Constant Mean Curvature Surfaces

abstract: We examine the space of surfaces in $\RR^{3}$ which are complete, properly embedded and have nonzero constant mean curvature. These surfaces are noncompact provided we exclude the case of the round sphere. We prove that the space $\Mk$ of all such surfaces with $k$ ends (where surfaces are identified if they differ by an isometry of $\RR^{3}$) is locally a real analytic variety. When the linearization of the quasilinear elliptic equation specifying mean curvature equal to one has no $L^2-$nullspace we prove that $\Mk$ is locally the quotient of a real analytic manifold of dimension $3k-6$ by a finite group (i\.e\. a real analytic orbifold), for $k\geq 3$. This finite group is the isotropy subgroup of the surface in the group of Euclidean motions. It is of interest to note that the dimension of $\Mk$ is independent of the topology of the underlying punctured Riemann surface to which $\Sig$ is conformally equivalent. These results also apply to hypersurfaces of $\HH^{n+1}$ with nonzero constant mean curvature greater than that of a horosphere and whose ends are cylindrically bounded.


title: On the Dirichlet problem for harmonic maps with prescribed singularities

abstract: Let $\M$ be a classical Riemannian globally symmetric space of rank one and non-compact type. We prove the existence and uniqueness of solutions to the Dirichlet problem for harmonic maps into $\M$ with prescribed singularities along a closed submanifold of the domain. This generalizes our previous work where such maps into the hyperbolic plane were constructed. This problem, in the case where $\M$ is the complex-hyperbolic plane, has applications to equilibrium configurations of co-axially rotating charged black holes in General Relativity.