title: AMIEDoT: An annotation model for document tracking and recommendation service

abstract: The primary objective of document annotation in whatever form, manual or electronic is to allow those who may not have control to original document to provide personal view on information source. Beyond providing personal assessment to original information sources, we are looking at a situation where annotation made can be used as additional source of information for document tracking and recommendation service. Most of the annotation tools existing today were conceived for their independent use with no reference to the creator of the annotation. We propose AMIEDoT (Annotation Model for Information Exchange and Document Tracking) an annotation model that can assist in document tracking and recommendation service. The model is based on three parameters in the acts of annotation. We believe that introducing document parameters, time and the parameters of the creator of annotation into an annotation process can be a dependable source to know, who used a document, when a document was used and for what a document was used for. Beyond document tracking, our model can be used in not only for selective dissemination of information but for recommendation services. AMIEDoT can also be used for information sharing and information reuse.


title: Orthogonal Codes for Robust Low-Cost Communication

abstract: Orthogonal coding schemes, known to asymptotically achieve the capacity per unit cost (CPUC) for single-user ergodic memoryless channels with a zero-cost input symbol, are investigated for single-user compound memoryless channels, which exhibit uncertainties in their input-output statistical relationships. A minimax formulation is adopted to attain robustness. First, a class of achievable rates per unit cost (ARPUC) is derived, and its utility is demonstrated through several representative case studies. Second, when the uncertainty set of channel transition statistics satisfies a convexity property, optimization is performed over the class of ARPUC through utilizing results of minimax robustness. The resulting CPUC lower bound indicates the ultimate performance of the orthogonal coding scheme, and coincides with the CPUC under certain restrictive conditions. Finally, still under the convexity property, it is shown that the CPUC can generally be achieved, through utilizing a so-called mixed strategy in which an orthogonal code contains an appropriate composition of different nonzero-cost input symbols.


title: AMIE: An annotation model for information research

abstract: The objective of most users for consulting any information database, information warehouse or the internet is to resolve one problem or the other. Available online or offline annotation tools were not conceived with the objective of assisting users in their bid to resolve a decisional problem. Apart from the objective and usage of annotation tools, how these tools are conceived and classified has implication on their usage. Several criteria have been used to categorize annotation concepts. Typically annotation are conceived based on how it affect the organization of document been considered for annotation or the organization of the resulting annotation. Our approach is annotation that will assist in information research for decision making. Annotation model for information exchange (AMIE) was conceived with the objective of information sharing and reuse.


title: Security Implications of Converged Networks and Protecting Them, without Compromising Efficiency

abstract: This dissertation has extensively looked into all aspects of VoIP commu-nications technology, and information presented in preceding chapters, which build up a solid framework to discuss the conceptual design model, and investigate features that could be incorporated for actual Pro-jects, with parameters that are tested on field values. The dissertation follows a five-course model, for answering different questions, both tech-nical and businesslike, around central issues, that have been crucial to explanation of the topic; starting with a general overview of VoIP tech-nology, analyzing current VoIP encryption methods, identifying security threats, designing a robust VoIP system based on particulars discussed in preceding chapters, and finally, a VoIP simulation.


title: Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes

abstract: Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Furthermore, the paper shows that informed scheduling solves some standard trapping set errors. Therefore, it also outperforms traditional scheduling for a large numbers of iterations. Complexity and implementability issues are also addressed.


title: The General Gaussian Multiple Access and Two-Way Wire-Tap Channels: Achievable Rates and Cooperative Jamming

abstract: The General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT) and the Gaussian Two-Way Wire-Tap Channel (GTW-WT) are considered. In the GGMAC-WT, multiple users communicate with an intended receiver in the presence of an eavesdropper who receives their signals through another GMAC. In the GTW-WT, two users communicate with each other over a common Gaussian channel, with an eavesdropper listening through a GMAC. A secrecy measure that is suitable for this multi-terminal environment is defined, and achievable secrecy rate regions are found for both channels. For both cases, the power allocations maximizing the achievable secrecy sum-rate are determined. It is seen that the optimum policy may prevent some terminals from transmission in order to preserve the secrecy of the system. Inspired by this construct, a new scheme, \ital{cooperative jamming}, is proposed, where users who are prevented from transmitting according to the secrecy sum-rate maximizing power allocation policy "jam" the eavesdropper, thereby helping the remaining users. This scheme is shown to increase the achievable secrecy sum-rate. Overall, our results show that in multiple-access scenarios, users can help each other to collectively achieve positive secrecy rates. In other words, cooperation among users can be invaluable for achieving secrecy for the system.


title: Fast Computation of Small Cuts via Cycle Space Sampling

abstract: We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G=(V, E) with O(log V)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by Diam, and the maximum degree by Delta. We obtain simple O(Diam)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal --- i.e. a Omega(Diam)-time lower bound holds on every graph. We obtain a O(Diam+Delta/log V)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Delta, Diam = O(sqrt(V)). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM our approach yields a simple algorithm with optimal time complexity O(log V) for finding cut pairs and 3-edge-connected components.


title: Nearest Neighbor Network Traversal

abstract: A mobile agent in a network wants to visit every node of an n-node network, using a small number of steps. We investigate the performance of the following ``nearest neighbor'' heuristic: always go to the nearest unvisited node. If the network graph never changes, then from (Rosenkrantz, Stearns and Lewis, 1977) and (Hurkens and Woeginger, 2004) it follows that Theta(n log n) steps are necessary and sufficient in the worst case. We give a simpler proof of the upper bound and an example that improves the best known lower bound. We investigate how the performance of this heuristic changes when it is distributively implemented in a network. Even if network edges are allow to fail over time, we show that the nearest neighbor strategy never runs for more than O(n^2) iterations. We also show that any strategy can be forced to take at least n(n-1)/2 steps before all nodes are visited, if the edges of the network are deleted in an adversarial way.


title: Guessing based on length functions

abstract: A guessing wiretapper's performance on a Shannon cipher system is analyzed for a source with memory. Close relationships between guessing functions and length functions are first established. Subsequently, asymptotically optimal encryption and attack strategies are identified and their performances analyzed for sources with memory. The performance metrics are exponents of guessing moments and probability of large deviations. The metrics are then characterized for unifilar sources. Universal asymptotically optimal encryption and attack strategies are also identified for unifilar sources. Guessing in the increasing order of Lempel-Ziv coding lengths is proposed for finite-state sources, and shown to be asymptotically optimal. Finally, competitive optimality properties of guessing in the increasing order of description lengths and Lempel-Ziv coding lengths are demonstrated.


title: The Bedwyr system for model checking over syntactic expressions

abstract: Bedwyr is a generalization of logic programming that allows model checking directly on syntactic expressions possibly containing bindings. This system, written in OCaml, is a direct implementation of two recent advances in the theory of proof search. The first is centered on the fact that both finite success and finite failure can be captured in the sequent calculus by incorporating inference rules for definitions that allow fixed points to be explored. As a result, proof search in such a sequent calculus can capture simple model checking problems as well as may and must behavior in operational semantics. The second is that higher-order abstract syntax is directly supported using term-level $\lambda$-binders and the $\nabla$ quantifier. These features allow reasoning directly on expressions containing bound variables.


title: On a family of strong geometric spanners that admit local routing strategies

abstract: We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $\lambda$ and $\theta$. For $0\leq \theta<\frac{\pi}{2}$ and ${1/2} < \lambda < 1$, the $\paz$ graph is a strong $t$-spanner, with $t=\frac{1}{(1-\lambda)\cos\theta}$. The out-degree of a node in the $\paz$ graph is at most $\lfloor2\pi/\min(\theta, \arccos\frac{1}{2\lambda})\rfloor$. Moreover, we show that routing can be achieved locally on $\paz$. Next, we show that all strong $t$-spanners are also $t$-spanners of the unit disk graph. Simulations for various values of the parameters $\lambda$ and $\theta$ indicate that for random point sets, the spanning ratio of $\paz$ is better than the proven theoretical bounds.


title: Interpolation-based Decoding of Alternant Codes

abstract: We formulate the classical decoding algorithm of alternant codes afresh based on interpolation as in Sudan's list decoding of Reed-Solomon codes, and thus get rid of the key equation and the linear recurring sequences in the theory. The result is a streamlined exposition of the decoding algorithm using a bit of the theory of Groebner bases of modules.


title: Ulam's Conjecture is True for Connected Graphs

abstract: This submission has been withdrawn at the request of the author.


title: On the decidability and complexity of Metric Temporal Logic over finite words

abstract: Metric Temporal Logic (MTL) is a prominent specification formalism for real-time systems. In this paper, we show that the satisfiability problem for MTL over finite timed words is decidable, with non-primitive recursive complexity. We also consider the model-checking problem for MTL: whether all words accepted by a given Alur-Dill timed automaton satisfy a given MTL formula. We show that this problem is decidable over finite words. Over infinite words, we show that model checking the safety fragment of MTL--which includes invariance and time-bounded response properties--is also decidable. These results are quite surprising in that they contradict various claims to the contrary that have appeared in the literature.


title: Induced Hilbert Space, Markov Chain, Diffusion Map and Fock Space in Thermophysics

abstract: In this article, we continue to explore Probability Bracket Notation (PBN), proposed in our previous article. Using both Dirac vector bracket notation (VBN) and PBN, we define induced Hilbert space and induced sample space, and propose that there exists an equivalence relation between a Hilbert space and a sample space constructed from the same base observable(s). Then we investigate Markov transition matrices and their eigenvectors to make diffusion maps with two examples: a simple graph theory example, to serve as a prototype of bidirectional transition operator; a famous text document example in IR literature, to serve as a tutorial of diffusion map in text document space. We show that the sample space of the Markov chain and the Hilbert space spanned by the eigenvectors of the transition matrix are not equivalent. At the end, we apply our PBN and equivalence proposal to Thermophysics by associating sample (phase) space with the Hilbert space of a single particle and the Fock space of many-particle systems.


title: Transmitter and Precoding Order Optimization for Nonlinear Downlink Beamforming

abstract: The downlink of a multiple-input multiple output (MIMO) broadcast channel (BC) is considered, where each receiver is equipped with a single antenna and the transmitter performs nonlinear Dirty-Paper Coding (DPC). We present an efficient algorithm that finds the optimum transmit filters and power allocation as well as the optimum precoding order(s) possibly affording time-sharing between individual DPC orders. Subsequently necessary and sufficient conditions for the optimality of an arbitrary precoding order are derived. Based on these we propose a suboptimal algorithm showing excellent performance and having low complexity.


title: Tree automata and separable sets of input variables

abstract: We consider the computational complexity of tree transducers, depending on their separable sets of input variables.


title: A Sequential Algorithm for Generating Random Graphs

abstract: We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-\tau})$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m\,d_{\max})$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in the graph and $\tau$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2d_{\max}^2)$. Our method also gives an independent proof of McKay's estimate McKay (1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of $d_{\max}=O(m^{1/4-\tau})$. Moreover, we show that for $d = O(n^{1/2-\tau})$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d = O(n^{1/3-\tau})$ due to Kim and Vu (2004) for regular graphs.


title: Bayesian Network Tomography and Inference

abstract: The aim of this technical report is to give a short overview of known techniques for network tomography (introduced in the paper of Vardi (1996)), extended by a Bayesian approach originating Tebaldi and West (1998). Since the studies of A.K. Erlang (1878-1929) on telephone networks in the last millennium, lots of needs are seen in todays applications of networks and network tomography, so for instance networks are a critical component of the information structure supporting finance, commerce and even civil and national defence. An attack on a network can be performed as an intrusion in the network or as sending a lot of fault information and disturbing the network flow. Such attacks can be detected by modelling the traffic flows in a network, by counting the source destination packets and even by measuring counts over time and by drawing a comparison with this 'time series' for instance.


title: Efficient Searching and Retrieval of Documents in PROSA

abstract: Retrieving resources in a distributed environment is more difficult than finding data in centralised databases. In the last decade P2P system arise as new and effective distributed architectures for resource sharing, but searching in such environments could be difficult and time-consuming. In this paper we discuss efficiency of resource discovery in PROSA, a self-organising P2P system heavily inspired by social networks. All routing choices in PROSA are made locally, looking only at the relevance of the next peer to each query. We show that PROSA is able to effectively answer queries for rare documents, forwarding them through the most convenient path to nodes that much probably share matching resources. This result is heavily related to the small-world structure that naturally emerges in PROSA.


title: Exploiting social networks dynamics for P2P resource organisation

abstract: In this paper we present a formal description of PROSA, a P2P resource management system heavily inspired by social networks. Social networks have been deeply studied in the last two decades in order to understand how communities of people arise and grow. It is a widely known result that networks of social relationships usually evolves to small-worlds, i.e. networks where nodes are strongly connected to neighbours and separated from all other nodes by a small amount of hops. This work shows that algorithms implemented into PROSA allow to obtain an efficient small-world P2P network.


title: Reconstructing the Nonlinear Filter Function of LILI-128 Stream Cipher Based on Complexity

abstract: In this letter we assert that we have reconstructed the nonlinear filter function of LILI-128 stream cipher on IBM notebook PC using MATLAB. Our reconstruction need approximately 2^12~2^13 and the attack consumes 5825.016 sec (using tic and toc sentences of MATLAB) or 5825.016/3600=1.6181hours. We got the expression of the nonlinear filter function fd of Lili-128 which has 46 items from liner items to nonlinear items based on complexity, the phase space reconstruction, Clustering and nonlinear prediction. We have verified our reconstruction result correctness by simulating the overview of Lili-128 keystream generators using our getting fd and implement designers reference module of the Lili-128 stream cipher, and two methods produce the same synchronous keystream sequence on same initial state, so that our research work proves that the nonlinear filter function of LILI-128 stream cipher is successfully reconstructed.


title: Tree Automata and Essential Input Variables

abstract: We introduce and study the essential inputs (variables) for terms (trees) and tree automata.


title: Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance based on Shift-Register Synthesis

abstract: In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond half the minimum distance is considered and analyzed. Unlike the Sudan algorithm published in 1997, this new approach is based on multi-sequence shift-register synthesis, which makes it easy to understand and simple to implement. The computational complexity of this shift-register based algorithm is of the same order as the complexity of the well-known Berlekamp-Massey algorithm. Moreover, the error correcting radius coincides with the error correcting radius of the original Sudan algorithm, and the practical decoding performance observed on a q-ary symmetric channel (QSC) is virtually identical to the decoding performance of the Sudan algorithm. Bounds for the failure and error probability as well as for the QSC decoding performance of the new algorithm are derived, and the performance is illustrated by means of examples.


title: AICA: a New Pair Force Evaluation Method for Parallel Molecular Dynamics in Arbitrary Geometries

abstract: A new algorithm for calculating intermolecular pair forces in Molecular Dynamics (MD) simulations on a distributed parallel computer is presented. The Arbitrary Interacting Cells Algorithm (AICA) is designed to operate on geometrical domains defined by an unstructured, arbitrary polyhedral mesh, which has been spatially decomposed into irregular portions for parallelisation. It is intended for nano scale fluid mechanics simulation by MD in complex geometries, and to provide the MD component of a hybrid MD/continuum simulation. AICA has been implemented in the open-source computational toolbox OpenFOAM, and verified against a published MD code.


title: Uplink Capacity and Interference Avoidance for Two-Tier Femtocell Networks

abstract: Two-tier femtocell networks-- comprising a conventional macrocellular network plus embedded femtocell hotspots-- offer an economically viable solution to achieving high cellular user capacity and improved coverage. With universal frequency reuse and DS-CDMA transmission however, the ensuing cross-tier cochannel interference (CCI) causes unacceptable outage probability. This paper develops an uplink capacity analysis and interference avoidance strategy in such a two-tier CDMA network. We evaluate a network-wide area spectral efficiency metric called the \emph{operating contour (OC)} defined as the feasible combinations of the average number of active macrocell users and femtocell base stations (BS) per cell-site that satisfy a target outage constraint. The capacity analysis provides an accurate characterization of the uplink outage probability, accounting for power control, path-loss and shadowing effects. Considering worst case CCI at a corner femtocell, results reveal that interference avoidance through a time-hopped CDMA physical layer and sectorized antennas allows about a 7x higher femtocell density, relative to a split spectrum two-tier network with omnidirectional femtocell antennas. A femtocell exclusion region and a tier selection based handoff policy offers modest improvements in the OCs. These results provide guidelines for the design of robust shared spectrum two-tier networks.


title: Fast Exact Method for Solving the Travelling Salesman Problem

abstract: This paper describes TSP exact solution of polynomial complexity. It is considered properties of proposed method. Effectiveness of proposed solution is illustrated by outcomes of computer modeling.


title: Patterns of technological progress: A Predictability-Based Perspective

abstract: The paper tries to identify new emerging patterns in the context of technological progress. Just as industrialization is associated with rationalization, mechanization, and automation, the Internet age is associated with computer models, embedded knowledge, and collaboration. Comparison among patterns is highlighted and analysis is done from predictability-based perspective.


title: High Performance Direct Gravitational N-body Simulations on Graphics Processing Units

abstract: We present the results of gravitational direct $N$-body simulations using the commercial graphics processing units (GPU) NVIDIA Quadro FX1400 and GeForce 8800GTX, and compare the results with GRAPE-6Af special purpose hardware. The force evaluation of the $N$-body problem was implemented in Cg using the GPU directly to speed-up the calculations. The integration of the equations of motions were, running on the host computer, implemented in C using the 4th order predictor-corrector Hermite integrator with block time steps. We find that for a large number of particles ($N \apgt 10^4$) modern graphics processing units offer an attractive low cost alternative to GRAPE special purpose hardware. A modern GPU continues to give a relatively flat scaling with the number of particles, comparable to that of the GRAPE. Using the same time step criterion the total energy of the $N$-body system was conserved better than to one in $10^6$ on the GPU, which is only about an order of magnitude worse than obtained with GRAPE. For $N\apgt 10^6$ the GeForce 8800GTX was about 20 times faster than the host computer. Though still about an order of magnitude slower than GRAPE, modern GPU's outperform GRAPE in their low cost, long mean time between failure and the much larger onboard memory; the GRAPE-6Af holds at most 256k particles whereas the GeForce 8800GTF can hold 9 million particles in memory.


title: Essential Inputs and Minimal Tree Automata

abstract: We continue studying essential inputs of trees and automata. Strongly essential inputs of trees are introduced and studied. Various examples for application in Computer Science are shown.


title: Tree Automata and Essential Subtrees

abstract: We introduce essential subtrees for terms (trees) and tree automata . There are some results concerning independent sets of subtrees and separable sets for a tree and an automaton.


title: On the Maximal Diversity Order of Spatial Multiplexing with Transmit Antenna Selection

abstract: Zhang et. al. recently derived upper and lower bounds on the achievable diversity of an N_R x N_T i.i.d. Rayleigh fading multiple antenna system using transmit antenna selection, spatial multiplexing and a linear receiver structure. For the case of L = 2 transmitting (out of N_T available) antennas the bounds are tight and therefore specify the maximal diversity order. For the general case with L <= min(N_R,N_T) transmitting antennas it was conjectured that the maximal diversity is (N_T-L+1)(N_R-L+1) which coincides with the lower bound. Herein, we prove this conjecture for the zero forcing and zero forcing decision feedback (with optimal detection ordering) receiver structures.


title: Characterization of $m$-Sequences of Lengths $2^{2k}-1$ and $2^k-1$ with Three-Valued Crosscorrelation

abstract: Considered is the distribution of the crosscorrelation between $m$-sequences of length $2^m-1$, where $m=2k$, and $m$-sequences of shorter length $2^k-1$. New pairs of $m$-sequences with three-valued crosscorrelation are found and the complete correlation distribution is determined. Finally, we conjecture that there are no more cases with a three-valued crosscorrelation apart from the ones proven here.


title: Assessing the Value of Coooperation in Wikipedia

abstract: Since its inception six years ago, the online encyclopedia Wikipedia has accumulated 6.40 million articles and 250 million edits, contributed in a predominantly undirected and haphazard fashion by 5.77 million unvetted volunteers. Despite the apparent lack of order, the 50 million edits by 4.8 million contributors to the 1.5 million articles in the English-language Wikipedia follow strong certain overall regularities. We show that the accretion of edits to an article is described by a simple stochastic mechanism, resulting in a heavy tail of highly visible articles with a large number of edits. We also demonstrate a crucial correlation between article quality and number of edits, which validates Wikipedia as a successful collaborative effort.


title: Recruitment, Preparation, Retention: A case study of computing culture at the University of Illinois at Urbana-Champaign

abstract: Computer science is seeing a decline in enrollment at all levels of education, including undergraduate and graduate study. This paper reports on the results of a study conducted at the University of Illinois at Urbana-Champaign which evaluated students attitudes regarding three areas which can contribute to improved enrollment in the Department of Computer Science: Recruitment, preparation and retention. The results of our study saw two themes. First, the department's tight research focus appears to draw significant attention from other activities -- such as teaching, service, and other community-building activities -- that are necessary for a department's excellence. Yet, as demonstrated by our second theme, one partial solution is to better promote such activities already employed by the department to its students and faculty. Based on our results, we make recommendations for improvements and enhancements based on the current state of practice at peer institutions.


title: An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

abstract: Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.


title: Attribute Value Reordering For Efficient Hybrid OLAP

abstract: The normalization of a data cube is the ordering of the attribute values. For large multidimensional arrays where dense and sparse chunks are stored differently, proper normalization can lead to improved storage efficiency. We show that it is NP-hard to compute an optimal normalization even for 1x3 chunks, although we find an exact algorithm for 1x2 chunks. When dimensions are nearly statistically independent, we show that dimension-wise attribute frequency sorting is an optimal normalization and takes time O(d n log(n)) for data cubes of size n^d. When dimensions are not independent, we propose and evaluate several heuristics. The hybrid OLAP (HOLAP) storage mechanism is already 19%-30% more efficient than ROLAP, but normalization can improve it further by 9%-13% for a total gain of 29%-44% over ROLAP.


title: Slope One Predictors for Online Rating-Based Collaborative Filtering

abstract: Rating-based collaborative filtering is the process of predicting how a user would rate a given item from other user ratings. We propose three related slope one schemes with predictors of the form f(x) = x + b, which precompute the average difference between the ratings of one item and another for users who rated both. Slope one algorithms are easy to implement, efficient to query, reasonably accurate, and they support both online queries and dynamic updates, which makes them good candidates for real-world systems. The basic slope one scheme is suggested as a new reference scheme for collaborative filtering. By factoring in items that a user liked separately from items that a user disliked, we achieve results competitive with slower memory-based schemes over the standard benchmark EachMovie and Movielens data sets while better fulfilling the desiderata of CF applications.


title: Designing a Resource Broker for Heterogeneous Grids

abstract: Grids provide uniform access to aggregations of heterogeneous resources and services such as computers, networks and storage owned by multiple organizations. However, such a dynamic environment poses many challenges for application composition and deployment. In this paper, we present the design of the Gridbus Grid resource broker that allows users to create applications and specify different objectives through different interfaces without having to deal with the complexity of Grid infrastructure. We present the unique requirements that motivated our design and discuss how these provide flexibility in extending the functionality of the broker to support different low-level middlewares and user interfaces. We evaluate the broker with different job profiles and Grid middleware and conclude with the lessons learnt from our development experience.


title: A Local Tree Structure is NOT Sufficient for the Local Optimality of Message-Passing Decoding in Low Density Parity Check Codes

abstract: We address the problem,`Is a local tree structure sufficient for the local optimality of message passing algorithm in low density parity check codes?'.It is shown that the answer is negative. Using this observation, we pinpoint a flaw in the proof of Theorem 1 in the paper `The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding' by Thomas J. Richardson and R\"udiger L.Urbanke\cite{RUCapacity}. We further provide a new proof of that theorem based on a different argument.


title: On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes

abstract: Since the classical work of Berlekamp, McEliece and van Tilborg, it is well known that the problem of exact maximum-likelihood (ML) decoding of general linear codes is NP-hard. In this paper, we show that exact ML decoding of a classs of asymptotically good error correcting codes--expander codes, a special case of low density parity check (LDPC) codes--over binary symmetric channels (BSCs) is possible with an expected polynomial complexity. More precisely, for any bit-flipping probability, $p$, in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes, whose error probability decays exponentially in coding length $n$, for which ML decoding is feasible in expected polynomial time. Furthermore, as $p$ approaches zero, this rate region approaches the channel capacity region. The result is based on the existence of polynomial-time suboptimal decoding algorithms that provide an ML certificate and the ability to compute the probability that the suboptimal decoder yields the ML solution. One such ML certificate decoder is the LP decoder of Feldman; we also propose a more efficient $O(n^2)$ algorithm based on the work of Sipser and Spielman and the Ford-Fulkerson algorithm. The results can be extended to AWGN channels and suggest that it may be feasible to eliminate the error floor phenomenon associated with message-passage decoding of LDPC codes in the high SNR regime. Finally, we observe that the argument of Berlekamp, McEliece and van Tilborg can be used to show that ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and expected complexities.


title: Linking Microscopic and Macroscopic Models for Evolution: Markov Chain Network Training and Conservation Law Approximations

abstract: In this paper, a general framework for the analysis of a connection between the training of artificial neural networks via the dynamics of Markov chains and the approximation of conservation law equations is proposed. This framework allows us to demonstrate an intrinsic link between microscopic and macroscopic models for evolution via the concept of perturbed generalized dynamic systems. The main result is exemplified with a number of illustrative examples where efficient numerical approximations follow directly from network-based computational models, viewed here as Markov chain approximations. Finally, stability and consistency conditions of such computational models are discussed.


title: Coupling Control and Human-Centered Automation in Mathematical Models of Complex Systems

abstract: In this paper we analyze mathematically how human factors can be effectively incorporated into the analysis and control of complex systems. As an example, we focus our discussion around one of the key problems in the Intelligent Transportation Systems (ITS) theory and practice, the problem of speed control, considered here as a decision making process with limited information available. The problem is cast mathematically in the general framework of control problems and is treated in the context of dynamically changing environments where control is coupled to human-centered automation. Since in this case control might not be limited to a small number of control settings, as it is often assumed in the control literature, serious difficulties arise in the solution of this problem. We demonstrate that the problem can be reduced to a set of Hamilton-Jacobi-Bellman equations where human factors are incorporated via estimations of the system Hamiltonian. In the ITS context, these estimations can be obtained with the use of on-board equipment like sensors/receivers/actuators, in-vehicle communication devices, etc. The proposed methodology provides a way to integrate human factor into the solving process of the models for other complex dynamic systems.


title: A note on rate-distortion functions for nonstationary Gaussian autoregressive processes

abstract: Source coding theorems and Shannon rate-distortion functions were studied for the discrete-time Wiener process by Berger and generalized to nonstationary Gaussian autoregressive processes by Gray and by Hashimoto and Arimoto. Hashimoto and Arimoto provided an example apparently contradicting the methods used in Gray, implied that Gray's rate-distortion evaluation was not correct in the nonstationary case, and derived a new formula that agreed with previous results for the stationary case and held in the nonstationary case. In this correspondence it is shown that the rate-distortion formulas of Gray and Hashimoto and Arimoto are in fact consistent and that the example of of Hashimoto and Arimoto does not form a counter example to the methods or results of the earlier paper. Their results do provide an alternative, but equivalent, formula for the rate-distortion function in the nonstationary case and they provide a concrete example that the classic Kolmogorov formula differs from the autoregressive formula when the autoregressive source is not stationary. Some observations are offered on the different versions of the Toeplitz asymptotic eigenvalue distribution theorem used in the two papers to emphasize how a slight modification of the classic theorem avoids the problems with certain singularities.


title: Succinct Sampling on Streams

abstract: A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding window of some fixed time-horizon. What makes the streaming model interesting is that as the time progresses, old items expire and new ones arrive. One of the simplest and central tasks in this model is sampling. That is, the task of maintaining up to $k$ uniformly distributed items from a current time-window as old items expire and new ones arrive. We call sampling algorithms {\bf succinct} if they use provably optimal (up to constant factors) {\bf worst-case} memory to maintain $k$ items (either with or without replacement). We stress that in many applications structures that have {\em expected} succinct representation as the time progresses are not sufficient, as small probability events eventually happen with probability 1. Thus, in this paper we ask the following question: are Succinct Sampling on Streams (or $S^3$-algorithms)possible, and if so for what models? Perhaps somewhat surprisingly, we show that $S^3$-algorithms are possible for {\em all} variants of the problem mentioned above, i.e. both with and without replacement and both for one-at-a-time and bursty arrival models. Finally, we use $S^3$ algorithms to solve various problems in sliding windows model, including frequency moments, counting triangles, entropy and density estimations. For these problems we present \emph{first} solutions with provable worst-case memory guarantees.


title: A Simplified Suspension Calculus and its Relationship to Other Explicit Substitution Calculi

abstract: This paper concerns the explicit treatment of substitutions in the lambda calculus. One of its contributions is the simplification and rationalization of the suspension calculus that embodies such a treatment. The earlier version of this calculus provides a cumbersome encoding of substitution composition, an operation that is important to the efficient realization of reduction. This encoding is simplified here, resulting in a treatment that is easy to use directly in applications. The rationalization consists of the elimination of a practically inconsequential flexibility in the unravelling of substitutions that has the inadvertent side effect of losing contextual information in terms; the modified calculus now has a structure that naturally supports logical analyses, such as ones related to the assignment of types, over lambda terms. The overall calculus is shown to have pleasing theoretical properties such as a strongly terminating sub-calculus for substitution and confluence even in the presence of term meta variables that are accorded a grafting interpretation. Another contribution of the paper is the identification of a broad set of properties that are desirable for explicit substitution calculi to support and a classification of a variety of proposed systems based on these. The suspension calculus is used as a tool in this study. In particular, mappings are described between it and the other calculi towards understanding the characteristics of the latter.


title: Games on the Sperner Triangle

abstract: We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based version of the game, playable at: http://cs-people.bu.edu/paithan/spernerGame/ . In addition we propose other games, also based on fixed-point theorems.


title: On the Capacity of the Single Source Multiple Relay Single Destination Mesh Network

abstract: In this paper, we derive the information theoretic capacity of a special class of mesh networks. A mesh network is a heterogeneous wireless network in which the transmission among power limited nodes is assisted by powerful relays, which use the same wireless medium. We investigate the mesh network when there is one source, one destination, and multiple relays, which we call the single source multiple relay single destination (SSMRSD) mesh network. We derive the asymptotic capacity of the SSMRSD mesh network when the relay powers grow to infinity. Our approach is as follows. We first look at an upper bound on the information theoretic capacity of these networks in a Gaussian setting. We then show that this bound is achievable asymptotically using the compress-and-forward strategy for the multiple relay channel. We also perform numerical computations for the case when the relays have finite powers. We observe that even when the relay power is only a few times larger than the source power, the compress-and-forward rate gets close to the capacity. The results indicate the value of cooperation in wireless mesh networks. The capacity characterization quantifies how the relays can cooperate, using the compress-and-forward strategy, to either conserve node energy or to increase transmission rate.


title: On a characterization of cellular automata in tilings of the hyperbolic plane

abstract: In this paper, we look at the extention of Hedlund's characterization of cellular automata to the case of cellular automata in the hyperbolic plane. This requires an additionnal condition. The new theorem is proved with full details in the case of the pentagrid and in the case of the ternary heptagrid and enough indications to show that it holds also on the grids $\{p,q\}$ of the hyperbolic plane.


title: Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms

abstract: We consider in this paper the problem of discovering, via a traceroute algorithm, the topology of a network, whose graph is spanned by an infinite branching process. A subset of nodes is selected according to some criterion. As a measure of efficiency of the algorithm, the Steiner distance of the selected nodes, i.e. the size of the spanning sub-tree of these nodes, is investigated. For the selection of nodes, two criteria are considered: A node is randomly selected with a probability, which is either independent of the depth of the node (uniform model) or else in the depth biased model, is exponentially decaying with respect to its depth. The limiting behavior the size of the discovered subtree is investigated for both models.


title: In Search of Simplicity: A Self-Organizing Multi-Source Multicast Overlay

abstract: Multicast communication primitives have broad utility as building blocks for distributed applications. The challenge is to create and maintain the distributed structures that support these primitives while accounting for volatile end nodes and variable network characteristics. Most solutions proposed to date rely on complex algorithms or global information, thus limiting the scale of deployments and acceptance outside the academic realm. This article introduces a low-complexity, self organizing solution for maintaining multicast trees, that we refer to as UMM (Unstructured Multi-source Multicast). UMM uses traditional distributed systems techniques: layering, soft-state, and passive data collection to adapt to the dynamics of the physical network and maintain data dissemination trees. The result is a simple, adaptive system with lower overheads than more complex alternatives. We have implemented UMM and evaluated it on a 100-node PlanetLab testbed and on up to 1024-node emulated ModelNet networks Extensive experimental evaluations demonstrate UMM's low overhead, efficient network usage compared to alternative solutions, and ability to quickly adapt to network changes and to recover from failures.


title: Joint Design and Separation Principle for Opportunistic Spectrum Access in the Presence of Sensing Errors

abstract: We address the design of opportunistic spectrum access (OSA) strategies that allow secondary users to independently search for and exploit instantaneous spectrum availability. Integrated in the joint design are three basic components: a spectrum sensor that identifies spectrum opportunities, a sensing strategy that determines which channels in the spectrum to sense, and an access strategy that decides whether to access based on imperfect sensing outcomes. We formulate the joint PHY-MAC design of OSA as a constrained partially observable Markov decision process (POMDP). Constrained POMDPs generally require randomized policies to achieve optimality, which are often intractable. By exploiting the rich structure of the underlying problem, we establish a separation principle for the joint design of OSA. This separation principle reveals the optimality of myopic policies for the design of the spectrum sensor and the access strategy, leading to closed-form optimal solutions. Furthermore, decoupling the design of the sensing strategy from that of the spectrum sensor and the access strategy, the separation principle reduces the constrained POMDP to an unconstrained one, which admits deterministic optimal policies. Numerical examples are provided to study the design tradeoffs, the interaction between the spectrum sensor and the sensing and access strategies, and the robustness of the ensuing design to model mismatch.


title: Perfect Hashing for Data Management Applications

abstract: Perfect hash functions can potentially be used to compress data in connection with a variety of data management tasks. Though there has been considerable work on how to construct good perfect hash functions, there is a gap between theory and practice among all previous methods on minimal perfect hashing. On one side, there are good theoretical results without experimentally proven practicality for large key sets. On the other side, there are the theoretically analyzed time and space usage algorithms that assume that truly random hash functions are available for free, which is an unrealistic assumption. In this paper we attempt to bridge this gap between theory and practice, using a number of techniques from the literature to obtain a novel scheme that is theoretically well-understood and at the same time achieves an order-of-magnitude increase in performance compared to previous ``practical'' methods. This improvement comes from a combination of a novel, theoretically optimal perfect hashing scheme that greatly simplifies previous methods, and the fact that our algorithm is designed to make good use of the memory hierarchy. We demonstrate the scalability of our algorithm by considering a set of over one billion URLs from the World Wide Web of average length 64, for which we construct a minimal perfect hash function on a commodity PC in a little more than 1 hour. Our scheme produces minimal perfect hash functions using slightly more than 3 bits per key. For perfect hash functions in the range $\{0,...,2n-1\}$ the space usage drops to just over 2 bits per key (i.e., one bit more than optimal for representing the key). This is significantly below of what has been achieved previously for very large values of $n$.


title: A Quantifier-Free String Theory for ALOGTIME Reasoning

abstract: The main contribution of this work is the definition of a quantifier-free string theory T_1 suitable for formalizing ALOGTIME reasoning. After describing L_1 -- a new, simple, algebraic characterization of the complexity class ALOGTIME based on strings instead of numbers -- the theory T_1 is defined (based on L_1), and a detailed formal development of T_1 is given. Then, theorems of T_1 are shown to translate into families of propositional tautologies that have uniform polysize Frege proofs, T_1 is shown to prove the soundness of a particular Frege system F, and F is shown to provably p-simulate any proof system whose soundness can be proved in T_1. Finally, T_1 is compared with other theories for ALOGTIME reasoning in the literature. To our knowledge, this is the first formal theory for ALOGTIME reasoning whose basic objects are strings instead of numbers, and the first quantifier-free theory formalizing ALOGTIME reasoning in which a direct proof of the soundness of some Frege system has been given (in the case of first-order theories, such a proof was first given by Arai for his theory AID). Also, the polysize Frege proofs we give for the propositional translations of theorems of T_1 are considerably simpler than those for other theories, and so is our proof of the soundness of a particular F-system in T_1. Together with the simplicity of T_1's recursion schemes, axioms, and rules these facts suggest that T_1 is one of the most natural theories available for ALOGTIME reasoning.


title: Perfectly Secure Steganography: Capacity, Error Exponents, and Code Constructions

abstract: An analysis of steganographic systems subject to the following perfect undetectability condition is presented in this paper. Following embedding of the message into the covertext, the resulting stegotext is required to have exactly the same probability distribution as the covertext. Then no statistical test can reliably detect the presence of the hidden message. We refer to such steganographic schemes as perfectly secure. A few such schemes have been proposed in recent literature, but they have vanishing rate. We prove that communication performance can potentially be vastly improved; specifically, our basic setup assumes independently and identically distributed (i.i.d.) covertext, and we construct perfectly secure steganographic codes from public watermarking codes using binning methods and randomized permutations of the code. The permutation is a secret key shared between encoder and decoder. We derive (positive) capacity and random-coding exponents for perfectly-secure steganographic systems. The error exponents provide estimates of the code length required to achieve a target low error probability. We address the potential loss in communication performance due to the perfect-security requirement. This loss is the same as the loss obtained under a weaker order-1 steganographic requirement that would just require matching of first-order marginals of the covertext and stegotext distributions. Furthermore, no loss occurs if the covertext distribution is uniform and the distortion metric is cyclically symmetric; steganographic capacity is then achieved by randomized linear codes. Our framework may also be useful for developing computationally secure steganographic systems that have near-optimal communication performance.


title: Distributed Power Allocation with Rate Constraints in Gaussian Parallel Interference Channels

abstract: This paper considers the minimization of transmit power in Gaussian parallel interference channels, subject to a rate constraint for each user. To derive decentralized solutions that do not require any cooperation among the users, we formulate this power control problem as a (generalized) Nash equilibrium game. We obtain sufficient conditions that guarantee the existence and nonemptiness of the solution set to our problem. Then, to compute the solutions of the game, we propose two distributed algorithms based on the single user waterfilling solution: The \emph{sequential} and the \emph{simultaneous} iterative waterfilling algorithms, wherein the users update their own strategies sequentially and simultaneously, respectively. We derive a unified set of sufficient conditions that guarantee the uniqueness of the solution and global convergence of both algorithms. Our results are applicable to all practical distributed multipoint-to-multipoint interference systems, either wired or wireless, where a quality of service in terms of information rate must be guaranteed for each link.


title: First Passage Time for Multivariate Jump-diffusion Stochastic Models With Applications in Finance

abstract: The ``first passage-time'' (FPT) problem is an important problem with a wide range of applications in mathematics, physics, biology and finance. Mathematically, such a problem can be reduced to estimating the probability of a (stochastic) process first to reach a critical level or threshold. While in other areas of applications the FPT problem can often be solved analytically, in finance we usually have to resort to the application of numerical procedures, in particular when we deal with jump-diffusion stochastic processes (JDP). In this paper, we develop a Monte-Carlo-based methodology for the solution of the FPT problem in the context of a multivariate jump-diffusion stochastic process. The developed methodology is tested by using different parameters, the simulation results indicate that the developed methodology is much more efficient than the conventional Monte Carlo method. It is an efficient tool for further practical applications, such as the analysis of default correlation and predicting barrier options in finance.


title: Monte-Carlo Simulations of the First Passage Time for Multivariate Jump-Diffusion Processes in Financial Applications

abstract: Many problems in finance require the information on the first passage time (FPT) of a stochastic process. Mathematically, such problems are often reduced to the evaluation of the probability density of the time for such a process to cross a certain level, a boundary, or to enter a certain region. While in other areas of applications the FPT problem can often be solved analytically, in finance we usually have to resort to the application of numerical procedures, in particular when we deal with jump-diffusion stochastic processes (JDP). In this paper, we propose a Monte-Carlo-based methodology for the solution of the first passage time problem in the context of multivariate (and correlated) jump-diffusion processes. The developed technique provide an efficient tool for a number of applications, including credit risk and option pricing. We demonstrate its applicability to the analysis of the default rates and default correlations of several different, but correlated firms via a set of empirical data.


title: Efficient estimation of default correlation for multivariate jump-diffusion processes

abstract: Evaluation of default correlation is an important task in credit risk analysis. In many practical situations, it concerns the joint defaults of several correlated firms, the task that is reducible to a first passage time (FPT) problem. This task represents a great challenge for jump-diffusion processes (JDP), where except for very basic cases, there are no analytical solutions for such problems. In this contribution, we generalize our previous fast Monte-Carlo method (non-correlated jump-diffusion cases) for multivariate (and correlated) jump-diffusion processes. This generalization allows us, among other things, to evaluate the default events of several correlated assets based on a set of empirical data. The developed technique is an efficient tool for a number of other applications, including credit risk and option pricing.


title: Solving Stochastic Differential Equations with Jump-Diffusion Efficiently: Applications to FPT Problems in Credit Risk

abstract: The first passage time (FPT) problem is ubiquitous in many applications. In finance, we often have to deal with stochastic processes with jump-diffusion, so that the FTP problem is reducible to a stochastic differential equation with jump-diffusion. While the application of the conventional Monte-Carlo procedure is possible for the solution of the resulting model, it becomes computationally inefficient which severely restricts its applicability in many practically interesting cases. In this contribution, we focus on the development of efficient Monte-Carlo-based computational procedures for solving the FPT problem under the multivariate (and correlated) jump-diffusion processes. We also discuss the implementation of the developed Monte-Carlo-based technique for multivariate jump-diffusion processes driving by several compound Poisson shocks. Finally, we demonstrate the application of the developed methodologies for analyzing the default rates and default correlations of differently rated firms via historical data.


title: Finite Volume Analysis of Nonlinear Thermo-mechanical Dynamics of Shape Memory Alloys

abstract: In this paper, the finite volume method is developed to analyze coupled dynamic problems of nonlinear thermoelasticity. The major focus is given to the description of martensitic phase transformations essential in the modelling of shape memory alloys. Computational experiments are carried out to study the thermo-mechanical wave interactions in a shape memory alloy rod, and a patch. Both mechanically and thermally induced phase transformations, as well as hysteresis effects, in a one-dimensional structure are successfully simulated with the developed methodology. In the two-dimensional case, the main focus is given to square-to-rectangular transformations and examples of martensitic combinations under different mechanical loadings are provided.


title: Simulation of Phase Combinations in Shape Memory Alloys Patches by Hybrid Optimization Methods

abstract: In this paper, phase combinations among martensitic variants in shape memory alloys patches and bars are simulated by a hybrid optimization methodology. The mathematical model is based on the Landau theory of phase transformations. Each stable phase is associated with a local minimum of the free energy function, and the phase combinations are simulated by minimizing the bulk energy. At low temperature, the free energy function has double potential wells leading to non-convexity of the optimization problem. The methodology proposed in the present paper is based on an initial estimate of the global solution by a genetic algorithm, followed by a refined quasi-Newton procedure to locally refine the optimum. By combining the local and global search algorithms, the phase combinations are successfully simulated. Numerical experiments are presented for the phase combinations in a SMA patch under several typical mechanical loadings.


title: Bistable Biorders: A Sequential Domain Theory

abstract: We give a simple order-theoretic construction of a Cartesian closed category of sequential functions. It is based on bistable biorders, which are sets with a partial order -- the extensional order -- and a bistable coherence, which captures equivalence of program behaviour, up to permutation of top (error) and bottom (divergence). We show that monotone and bistable functions (which are required to preserve bistably bounded meets and joins) are strongly sequential, and use this fact to prove universality results for the bistable biorder semantics of the simply-typed lambda-calculus (with atomic constants), and an extension with arithmetic and recursion. We also construct a bistable model of SPCF, a higher-order functional programming language with non-local control. We use our universality result for the lambda-calculus to show that the semantics of SPCF is fully abstract. We then establish a direct correspondence between bistable functions and sequential algorithms by showing that sequential data structures give rise to bistable biorders, and that each bistable function between such biorders is computed by a sequential algorithm.


title: Generic Global Constraints based on MDDs

abstract: Constraint Programming (CP) has been successfully applied to both constraint satisfaction and constraint optimization problems. A wide variety of specialized global constraints provide critical assistance in achieving a good model that can take advantage of the structure of the problem in the search for a solution. However, a key outstanding issue is the representation of 'ad-hoc' constraints that do not have an inherent combinatorial nature, and hence are not modeled well using narrowly specialized global constraints. We attempt to address this issue by considering a hybrid of search and compilation. Specifically we suggest the use of Reduced Ordered Multi-Valued Decision Diagrams (ROMDDs) as the supporting data structure for a generic global constraint. We give an algorithm for maintaining generalized arc consistency (GAC) on this constraint that amortizes the cost of the GAC computation over a root-to-leaf path in the search tree without requiring asymptotically more space than used for the MDD. Furthermore we present an approach for incrementally maintaining the reduced property of the MDD during the search, and show how this can be used for providing domain entailment detection. Finally we discuss how to apply our approach to other similar data structures such as AOMDDs and Case DAGs. The technique used can be seen as an extension of the GAC algorithm for the regular language constraint on finite length input.


title: How Overlap Determines the Macronuclear Genes in Ciliates

abstract: Formal models for gene assembly in ciliates have been developed, in particular the string pointer reduction system (SPRS) and the graph pointer reduction system (GPRS). The reduction graph is a valuable tool within the SPRS, revealing much information about how gene assembly is performed for a given gene. The GPRS is more abstract than the SPRS and not all information present in the SPRS is retained in the GPRS. As a consequence the reduction graph cannot be defined for the GPRS in general, but we show that it can be defined (in an equivalent manner as defined for the SPRS) if we restrict ourselves to so-called realistic overlap graphs. Fortunately, only these graphs correspond to genes occurring in nature. Defining the reduction graph within the GPRS allows one to carry over several results within the SPRS that rely on the reduction graph.


title: Numerical Model For Vibration Damping Resulting From the First Order Phase Transformations

abstract: A numerical model is constructed for modelling macroscale damping effects induced by the first order martensite phase transformations in a shape memory alloy rod. The model is constructed on the basis of the modified Landau-Ginzburg theory that couples nonlinear mechanical and thermal fields. The free energy function for the model is constructed as a double well function at low temperature, such that the external energy can be absorbed during the phase transformation and converted into thermal form. The Chebyshev spectral methods are employed together with backward differentiation for the numerical analysis of the problem. Computational experiments performed for different vibration energies demonstrate the importance of taking into account damping effects induced by phase transformations.


title: Embedding Graphs into the Extended Grid

abstract: Let $G=(V,E)$ be an arbitrary undirected source graph to be embedded in a target graph $EM$, the extended grid with vertices on integer grid points and edges to nearest and next-nearest neighbours. We present an algorithm showing how to embed $G$ into $EM$ in both time and space $O(|V|^2)$ using the new notions of islands and bridges. An island is a connected subgraph in the target graph which is mapped from exactly one vertex in the source graph while a bridge is an edge between two islands which is mapped from exactly one edge in the source graph. This work is motivated by real industrial applications in the field of quantum computing and a need to efficiently embed source graphs in the extended grid.


title: Integral Biomathics: A Post-Newtonian View into the Logos of Bios (On the New Meaning, Relations and Principles of Life in Science)

abstract: This work is an attempt for a state-of-the-art survey of natural and life sciences with the goal to define the scope and address the central questions of an original research program. It is focused on the phenomena of emergence, adaptive dynamics and evolution of self-assembling, self-organizing, self-maintaining and self-replicating biosynthetic systems viewed from a newly-arranged perspective and understanding of computation and communication in the living nature.


title: Functions to Support Input and Output of Intervals

abstract: Interval arithmetic is hardly feasible without directed rounding as provided, for example, by the IEEE floating-point standard. Equally essential for interval methods is directed rounding for conversion between the external decimal and internal binary numerals. This is not provided by the standard I/O libraries. Conversion algorithms exist that guarantee identity upon conversion followed by its inverse. Although it may be possible to adapt these algorithms for use in decimal interval I/O, we argue that outward rounding in radix conversion is computationally a simpler problem than guaranteeing identity. Hence it is preferable to develop decimal interval I/O ab initio, which is what we do in this paper.


title: Accelerating Socio-Technological Evolution: from ephemeralization and stigmergy to the global brain

abstract: Evolution is presented as a trial-and-error process that produces a progressive accumulation of knowledge. At the level of technology, this leads to ephemeralization, i.e. ever increasing productivity, or decreasing of the friction that normally dissipates resources. As a result, flows of matter, energy and information circulate ever more easily across the planet. This global connectivity increases the interactions between agents, and thus the possibilities for conflict. However, evolutionary progress also reduces social friction, via the creation of institutions. The emergence of such "mediators" is facilitated by stigmergy: the unintended collaboration between agents resulting from their actions on a shared environment. The Internet is a near ideal medium for stigmergic interaction. Quantitative stigmergy allows the web to learn from the activities of its users, thus becoming ever better at helping them to answer their queries. Qualitative stigmergy stimulates agents to collectively develop novel knowledge. Both mechanisms have direct analogues in the functioning of the human brain. This leads us to envision the future, super-intelligent web as a "global brain" for humanity. The feedback between social and technological advances leads to an extreme acceleration of innovation. An extrapolation of the corresponding hyperbolic growth model would forecast a singularity around 2040. This can be interpreted as the evolutionary transition to the Global Brain regime.


title: State Amplification

abstract: We consider the problem of transmitting data at rate R over a state dependent channel p(y|x,s) with the state information available at the sender and at the same time conveying the information about the channel state itself to the receiver. The amount of state information that can be learned at the receiver is captured by the mutual information I(S^n; Y^n) between the state sequence S^n and the channel output Y^n. The optimal tradeoff is characterized between the information transmission rate R and the state uncertainty reduction rate \Delta, when the state information is either causally or noncausally available at the sender. This result is closely related and in a sense dual to a recent study by Merhav and Shamai, which solves the problem of masking the state information from the receiver rather than conveying it.


title: XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem

abstract: The DIMACS 32-bit parity problem is a satisfiability (SAT) problem hard to solve. So far, EqSatz by Li is the only solver which can solve this problem. However, This solver is very slow. It is reported that it spent 11855 seconds to solve a par32-5 instance on a Maxintosh G3 300 MHz. The paper introduces a new solver, XORSAT, which splits the original problem into two parts: structured part and random part, and then solves separately them with WalkSAT and an XOR equation solver. Based our empirical observation, XORSAT is surprisingly fast, which is approximately 1000 times faster than EqSatz. For a par32-5 instance, XORSAT took 2.9 seconds, while EqSatz took 2844 seconds on Intel Pentium IV 2.66GHz CPU. We believe that this method significantly different from traditional methods is also useful beyond this domain.


title: Intensional properties of polygraphs

abstract: We present polygraphic programs, a subclass of Albert Burroni's polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.


title: Strategies in object-oriented design

abstract: This paper presents a study aiming to analyse the design strategies of experts in object-oriented programming. We report an experiment conducted with four experts. Each subject solved three problems. Our results show that three strategies may be used in program design according to the solution structure. An object-centred strategy and a function-centred strategy are used when the solution has a hierarchical structure with vertical communication between objects. In this case, the plan which guides the design activity is declarative. A procedure-centred strategy is used when the solution has a flat structure with horizontal communication between objects. In this case, the plan which guides the design activity is procedural. These results are discussed in relation with results on design strategies in procedural design. Furthermore, our results provide insight into the knowledge structures of experts in object-oriented design. To conclude, we point out limitations of this study and discuss implications of our results for Human-Computer Interaction systems, in particular for systems assisting experts in their design activity.


title: A Methodological Framework for Socio-Cognitive Analyses of Collaborative Design of Open Source Software

abstract: Open Source Software (OSS) development challenges traditional software engineering practices. In particular, OSS projects are managed by a large number of volunteers, working freely on the tasks they choose to undertake. OSS projects also rarely rely on explicit system-level design, or on project plans or schedules. Moreover, OSS developers work in arbitrary locations and collaborate almost exclusively over the Internet, using simple tools such as email and software code tracking databases (e.g. CVS). All the characteristics above make OSS development akin to weaving a tapestry of heterogeneous components. The OSS design process relies on various types of actors: people with prescribed roles, but also elements coming from a variety of information spaces (such as email and software code). The objective of our research is to understand the specific hybrid weaving accomplished by the actors of this distributed, collective design process. This, in turn, challenges traditional methodologies used to understand distributed software engineering: OSS development is simply too "fibrous" to lend itself well to analysis under a single methodological lens. In this paper, we describe the methodological framework we articulated to analyze collaborative design in the Open Source world. Our framework focuses on the links between the heterogeneous components of a project's hybrid network. We combine ethnography, text mining, and socio-technical network analysis and visualization to understand OSS development in its totality. This way, we are able to simultaneously consider the social, technical, and cognitive aspects of OSS development. We describe our methodology in detail, and discuss its implications for future research on distributed collective practices.


title: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

abstract: We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location problem (UFL), which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang. Note, that the approximability lower bound by Guha and Khuller is 1.463. An algorithm is a {\em ($\lambda_f$,$\lambda_c$)-approximation algorithm} if the solution it produces has total cost at most $\lambda_f \cdot F^* + \lambda_c \cdot C^*$, where $F^*$ and $C^*$ are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the $(1+2/e)$-approximation algorithm of Chudak and Shmoys, is a (1.6774,1.3738)-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve $(\gamma_f, 1+2e^{-\gamma_f})$ established by Jain, Mahdian and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a (1.11,1.7764)-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL.


title: Can we Compute the Similarity Between Surfaces?

abstract: A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fr\'echet distance. Whereas efficient algorithms are known for computing the Fr\'echet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Here, using a discrete approximation we show that it is {\em upper semi-computable}, i.e., there is a non-halting Turing machine which produces a monotone decreasing sequence of rationals converging to the result. It follows that the decision problem, whether the Fr\'echet distance of two given surfaces lies below some specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the problem, the computation of the {\em weak Fr\'echet distance} can be solved in polynomial time. For this, we give a computable characterization of the weak Fr\'echet distance in a geometric data structure called the {\em free space diagram}.


title: Pre-Requirement Specification Traceability: Bridging the Complexity Gap through Capabilities

abstract: Pre-Requirement Specification traceability is the activity of capturing relations between requirements and their sources, in particular user needs. Requirements are formal technical specifications in the solution space; needs are natural language expressions codifying user expectations in the problem space. Current traceability techniques are challenged by the complexity gap that results from the disparity between the spaces, and thereby, often neglect traceability to and from requirements. We identify the existence of an intermediary region -- the transition space -- which structures the progression from needs to requirements. More specifically, our approach to developing change-tolerant systems, termed Capabilities Engineering, identifies highly cohesive, minimally coupled, optimized functional abstractions called Capabilities in the transition space. These Capabilities link the problem and solution spaces through directives (entities derived from user needs). Directives connect the problem and transition spaces; Capabilities link the transition and solution spaces. Furthermore, the process of Capabilities Engineering addresses specific traceability challenges. It supports the evolution of traces, provides semantic and structural information about dependencies, incorporates human factors, generates traceability relations with negligible overhead, and thereby, fosters pre-Requirement Specification traceability.


title: NLC-2 graph recognition and isomorphism

abstract: NLC-width is a variant of clique-width with many application in graph algorithmic. This paper is devoted to graphs of NLC-width two. After giving new structural properties of the class, we propose a $O(n^2 m)$-time algorithm, improving Johansson's algorithm \cite{Johansson00}. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust $O(n^2 m)$-time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm.


title: Asymptotic Capacity Bounds for Wireless Networks with Non-Uniform Traffic

abstract: We develop bounds on the capacity of wireless networks when the traffic is non-uniform, i.e., not all nodes are required to receive and send similar volumes of traffic. Our results are asymptotic, i.e., they hold with probability going to unity as the number of nodes goes to infinity. We study \emph{(i)} asymmetric networks, where the numbers of sources and destinations of traffic are unequal, \emph{(ii)} multicast networks, in which each created packet has multiple destinations, \emph{(iii)} cluster networks, that consist of clients and a limited number of cluster heads, and each client wants to communicate with any of the cluster heads, and \emph{(iv)} hybrid networks, in which the nodes are supported by a limited infrastructure. Our findings quantify the fundamental capabilities of these wireless networks to handle traffic bottlenecks, and point to correct design principles that achieve the capacity without resorting to overly complicated protocols.


title: Graph representation of context-free grammars

abstract: In modern mathematics, graphs figure as one of the better-investigated class of mathematical objects. Various properties of graphs, as well as graph-processing algorithms, can be useful if graphs of a certain kind are used as denotations for CF-grammars. Furthermore, graph are well adapted to various extensions (one kind of such extensions being attributes).


title: Outage Probability of Multiple-Input Single-Output (MISO) Systems with Delayed Feedback

abstract: We investigate the effect of feedback delay on the outage probability of multiple-input single-output (MISO) fading channels. Channel state information at the transmitter (CSIT) is a delayed version of the channel state information available at the receiver (CSIR). We consider two cases of CSIR: (a) perfect CSIR and (b) CSI estimated at the receiver using training symbols. With perfect CSIR, under a short-term power constraint, we determine: (a) the outage probability for beamforming with imperfect CSIT (BF-IC) analytically, and (b) the optimal spatial power allocation (OSPA) scheme that minimizes outage numerically. Results show that, for delayed CSIT, BF-IC is close to optimal for low SNR and uniform spatial power allocation (USPA) is close to optimal at high SNR. Similarly, under a long-term power constraint, we show that BF-IC is close to optimal for low SNR and USPA is close to optimal at high SNR. With imperfect CSIR, we obtain an upper bound on the outage probability with USPA and BF-IC. Results show that the loss in performance due to imperfection in CSIR is not significant, if the training power is chosen appropriately.


title: Performance Bounds for Bi-Directional Coded Cooperation Protocols

abstract: In coded bi-directional cooperation, two nodes wish to exchange messages over a shared half-duplex channel with the help of a relay. In this paper, we derive performance bounds for this problem for each of three protocols. The first protocol is a two phase protocol were both users simultaneously transmit during the first phase and the relay alone transmits during the second. In this protocol, our bounds are tight and a multiple-access channel transmission from the two users to the relay followed by a coded broadcast-type transmission from the relay to the users achieves all points in the two-phase capacity region. The second protocol considers sequential transmissions from the two users followed by a transmission from the relay while the third protocol is a hybrid of the first two protocols and has four phases. In the latter two protocols the inner and outer bounds are not identical, and differ in a manner similar to the inner and outer bounds of Cover's relay channel. Numerical evaluation shows that at least in some cases of interest our bounds do not differ significantly. Finally, in the Gaussian case with path loss, we derive achievable rates and compare the relative merits of each protocol in various regimes. This case is of interest in cellular systems. Surprisingly, we find that in some cases, the achievable rate region of the four phase protocol sometimes contains points that are outside the outer bounds of the other protocols.


title: A Coding Theoretic Study on MLL proof nets

abstract: Coding theory is very useful for real world applications. A notable example is digital television. Basically, coding theory is to study a way of detecting and/or correcting data that may be true or false. Moreover coding theory is an area of mathematics, in which there is an interplay between many branches of mathematics, e.g., abstract algebra, combinatorics, discrete geometry, information theory, etc. In this paper we propose a novel approach for analyzing proof nets of Multiplicative Linear Logic (MLL) by coding theory. We define families of proof structures and introduce a metric space for each family. In each family, 1. an MLL proof net is a true code element; 2. a proof structure that is not an MLL proof net is a false (or corrupted) code element. The definition of our metrics reflects the duality of the multiplicative connectives elegantly. In this paper we show that in the framework one error-detecting is possible but one error-correcting not. Our proof of the impossibility of one error-correcting is interesting in the sense that a proof theoretical property is proved using a graph theoretical argument. In addition, we show that affine logic and MLL + MIX are not appropriate for this framework. That explains why MLL is better than such similar logics.


title: The Stackelberg Minimum Spanning Tree Game

abstract: We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most $\min \{k,1+\ln b,1+\ln W\}$, where $k$ is the number of distinct red costs, $b$ is the number of blue edges, and $W$ is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm.


title: Counting preimages of TCP reordering patterns

abstract: Packet reordering is an important property of network traffic that should be captured by analytical models of the Transmission Control Protocol (TCP). We study a combinatorial problem motivated by RESTORED, a TCP modeling methodology that incorporates information about packet dynamics. A significant component of this model is a many-to-one mapping B that transforms sequences of packet IDs into buffer sequences, in a manner that is compatible with TCP semantics. We show that the following hold: 1. There exists a linear time algorithm that, given a buffer sequence W of length n, decides whether there exists a permutation A of 1,2,..., n such that $A\in B^{-1}(W)$ (and constructs such a permutation, when it exists). 2. The problem of counting the number of permutations in $B^{-1}(W)$ has a polynomial time algorithm. We also show how to extend these results to sequences of IDs that contain repeated packets.


title: Addressing Components' Evolvement and Execution Behavior to Measure Component-Based Software Reliability

abstract: Software reliability is an important quality attrib-ute, often evaluated as either a function of time or of system structures. The goal of this study is to have this metric cover both for component-based software, be-cause its reliability strongly depends on the quality of constituent components and their interactions. To achieve this, we apply a convolution modeling ap-proach, based on components' execution behavior, to integrate their individual reliability evolvement and simultaneously address failure fixes in the time do-main. Modeling at the component level can be more economical to accommodate software evolution, be-cause the reliability metric can be evaluated by reus-ing the quality measures of unaffected components and adapting only to the affected ones to save cost. The adaptation capability also supports the incremental software development processes that constantly add in new components over time. Experiments were con-ducted to discuss the usefulness of this approach.


title: Rate of Channel Hardening of Antenna Selection Diversity Schemes and Its Implication on Scheduling

abstract: For a multiple antenna system, we compute the asymptotic distribution of antenna selection gain when the transmitter selects the transmit antenna with the strongest channel. We use this to asymptotically estimate the underlying channel capacity distributions, and demonstrate that unlike multiple-input/multiple-output (MIMO) systems, the channel for antenna selection systems hardens at a slower rate, and thus a significant multiuser scheduling gain can exist - O(1/ log m) for channel selection as opposed to O(1/ sqrt{m}) for MIMO, where m is the number of transmit antennas. Additionally, even without this scheduling gain, it is demonstrated that transmit antenna selection systems outperform open loop MIMO systems in low signal-to-interference-plus-noise ratio (SINR) regimes, particularly for a small number of receive antennas. This may have some implications on wireless system design, because most of the users in modern wireless systems have low SINRs


title: Computing a Minimum-Dilation Spanning Tree is NP-hard

abstract: In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.


title: Algorithmic Information Theory: a brief non-technical guide to the field

abstract: This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.


title: LIBOPT - An environment for testing solvers on heterogeneous collections of problems - Version 1.0

abstract: The Libopt environment is both a methodology and a set of tools that can be used for testing, comparing, and profiling solvers on problems belonging to various collections. These collections can be heterogeneous in the sense that their problems can have common features that differ from one collection to the other. Libopt brings a unified view on this composite world by offering, for example, the possibility to run any solver on any problem compatible with it, using the same Unix/Linux command. The environment also provides tools for comparing the results obtained by solvers on a specified set of problems. Most of the scripts going with the Libopt environment have been written in Perl.


title: Formal proof for delayed finite field arithmetic using floating point operators

abstract: Formal proof checkers such as Coq are capable of validating proofs of correction of algorithms for finite field arithmetics but they require extensive training from potential users. The delayed solution of a triangular system over a finite field mixes operations on integers and operations on floating point numbers. We focus in this report on verifying proof obligations that state that no round off error occurred on any of the floating point operations. We use a tool named Gappa that can be learned in a matter of minutes to generate proofs related to floating point arithmetic and hide technicalities of formal proof checkers. We found that three facilities are missing from existing tools. The first one is the ability to use in Gappa new lemmas that cannot be easily expressed as rewriting rules. We coined the second one ``variable interchange'' as it would be required to validate loop interchanges. The third facility handles massive loop unrolling and argument instantiation by generating traces of execution for a large number of cases. We hope that these facilities may sometime in the future be integrated into mainstream code validation.


title: Interroger un corpus par le sens

abstract: In textual knowledge management, statistical methods prevail. Nonetheless, some difficulties cannot be overcome by these methodologies. I propose a symbolic approach using a complete textual analysis to identify which analysis level can improve the the answers provided by a system. The approach identifies word senses and relation between words and generates as many rephrasings as possible. Using synonyms and derivative, the system provides new utterances without changing the original meaning of the sentences. Such a way, an information can be retrieved whatever the question or answer's wording may be.


title: Graphic processors to speed-up simulations for the design of high performance solar receptors

abstract: Graphics Processing Units (GPUs) are now powerful and flexible systems adapted and used for other purposes than graphics calculations (General Purpose computation on GPU -- GPGPU). We present here a prototype to be integrated into simulation codes that estimate temperature, velocity and pressure to design next generations of solar receptors. Such codes will delegate to our contribution on GPUs the computation of heat transfers due to radiations. We use Monte-Carlo line-by-line ray-tracing through finite volumes. This means data-parallel arithmetic transformations on large data structures. Our prototype is inspired on the source code of GPUBench. Our performances on two recent graphics cards (Nvidia 7800GTX and ATI RX1800XL) show some speed-up higher than 400 compared to CPU implementations leaving most of CPU computing resources available. As there were some questions pending about the accuracy of the operators implemented in GPUs, we start this report with a survey and some contributed tests on the various floating point units available on GPUs.


title: FPRAS for computing a lower bound for weighted matching polynomial of graphs

abstract: We give a fully polynomial randomized approximation scheme to compute a lower bound for the matching polynomial of any weighted graph at a positive argument. For the matching polynomial of complete bipartite graphs with bounded weights these lower bounds are asymptotically optimal.


title: An Efficient Local Approach to Convexity Testing of Piecewise-Linear Hypersurfaces

abstract: We show that a closed piecewise-linear hypersurface immersed in $R^n$ ($n\ge 3$) is the boundary of a convex body if and only if every point in the interior of each $(n-3)$-face has a neighborhood that lies on the boundary of some convex body; no assumptions about the hypersurface's topology are needed. We derive this criterion from our generalization of Van Heijenoort's (1952) theorem on locally convex hypersurfaces in $R^n$ to spherical spaces. We also give an easy-to-implement convexity testing algorithm, which is based on our criterion. For $R^3$ the number of arithmetic operations used by the algorithm is at most linear in the number of vertices, while in general it is at most linear in the number of incidences between the $(n-2)$-faces and $(n-3)$-faces. When the dimension $n$ is not fixed and only ring arithmetic is allowed, the algorithm still remains polynomial. Our method works in more general situations than the convexity verification algorithms developed by Mehlhorn et al. (1996) and Devillers et al. (1998) -- for example, our method does not require the input surface to be orientable, nor it requires the input data to include normal vectors to the facets that are oriented "in a coherent way". For $R^3$ the complexity of our algorithm is the same as that of previous algorithms; for higher dimensions there seems to be no clear winner, but our approach is the only one that easily handles inputs in which the facet normals are not known to be coherently oriented or are not given at all. Furthermore, our method can be extended to piecewise-polynomial surfaces of small degree.


title: Sampling Eulerian orientations of triangular lattice graphs

abstract: We consider the problem of sampling from the uniform distribution on the set of Eulerian orientations of subgraphs of the triangular lattice. Although it is known that this can be achieved in polynomial time for any graph, the algorithm studied here is more natural in the context of planar Eulerian graphs. We analyse the mixing time of a Markov chain on the Eulerian orientations of a planar graph which moves between orientations by reversing the edges of directed faces. Using path coupling and the comparison method we obtain a polynomial upper bound on the mixing time of this chain for any solid subgraph of the triangular lattice. By considering the conductance of the chain we show that there exist subgraphs with holes for which the chain will always take an exponential amount of time to converge. Finally, as an additional justification for studying a Markov chain on the set of Eulerian orientations of planar graphs, we show that the problem of counting Eulerian orientations remains #P-complete when restricted to planar graphs. A preliminary version of this work appeared as an extended abstract in the 2nd Algorithms and Complexity in Durham workshop.