OpenRaiser/Intern-Atlas huggingface dataset:
BiopSym: a simulator for enhanced learning of ultrasound-guided prostate biopsy
Venue: arXiv cs.RO 2008
Year: 2008

This paper describes a simulator of ultrasound-guided prostate biopsies for cancer diagnosis. When performing biopsy series, the clinician has to move the ultrasound probe and to mentally integrate the real-time bi-dimensional images into a three-dimensional (3D) representation of the anatomical environment. Such a 3D representation is necessary to sample regularly the prostate in order to maximize the probability of detecting a cancer if any. To make the training of young physicians easier and faster we developed a simulator that combines images computed from three-dimensional ultrasound recorded data to haptic feedback. The paper presents the first version of this simulator.
The K-Receiver Broadcast Channel with Confidential Messages
Venue: arXiv cs.IT 2008
Year: 2008

The secrecy capacity region for the K-receiver degraded broadcast channel (BC) is given for confidential messages sent to the receivers and to be kept secret from an external wiretapper. Superposition coding and Wyner's random code partitioning are used to show the achievable rate tuples. Error probability analysis and equivocation calculation are also provided. In the converse proof, a new definition for the auxiliary random variables is used, which is different from either the case of the 2-receiver BC without common message or the K-receiver BC with common message, both with an external wiretapper; or the K-receiver BC without a wiretapper.
The Latent Relation Mapping Engine: Algorithm and Experiments
Venue: arXiv cs.CL 2008
Year: 2008

Many AI researchers and cognitive scientists have argued that analogy is the core of cognition. The most influential work on computational modeling of analogy-making is Structure Mapping Theory (SMT) and its implementation in the Structure Mapping Engine (SME). A limitation of SME is the requirement for complex hand-coded representations. We introduce the Latent Relation Mapping Engine (LRME), which combines ideas from SME and Latent Relational Analysis (LRA) in order to remove the requirement for hand-coded representations. LRME builds analogical mappings between lists of words, using a large corpus of raw text to automatically discover the semantic relations among the words. We evaluate LRME on a set of twenty analogical mapping problems, ten based on scientific analogies and ten based on common metaphors. LRME achieves human-level performance on the twenty problems. We compare LRME with a variety of alternative approaches and find that they are not able to reach the same level of performance.
System Theoretic Viewpoint on Modeling of Complex Systems: Design, Synthesis, Simulation, and Control
Venue: arXiv cs.CE 2008
Year: 2008

We consider the basic features of complex dynamic and control systems, including systems having hierarchical structure. Special attention is paid to the problems of design and synthesis of complex systems and control models, and to the development of simulation techniques and systems. A model of complex system is proposed and briefly analyzed.
Feature Markov Decision Processes
Venue: arXiv cs.AI 2008
Year: 2008

General purpose intelligent learning agents cycle through (complex,non-MDP) sequences of observations, actions, and rewards. On the other hand, reinforcement learning is well-developed for small finite state Markov Decision Processes (MDPs). So far it is an art performed by human designers to extract the right state representation out of the bare observations, i.e. to reduce the agent setup to the MDP framework. Before we can think of mechanizing this search for suitable MDPs, we need a formal objective criterion. The main contribution of this article is to develop such a criterion. I also integrate the various parts into one learning algorithm. Extensions to more realistic dynamic Bayesian networks are developed in a companion article.
On Wireless Link Scheduling and Flow Control
Venue: arXiv cs.NI 2008
Year: 2008

This thesis focuses on link scheduling in wireless mesh networks by taking into account physical layer characteristics. The assumption made throughout is that a packet is received successfully only if the Signal to Interference and Noise Ratio (SINR) at the receiver exceeds the communication threshold. The thesis also discusses the complementary problem of flow control. (1) We consider various problems on centralized link scheduling in Spatial Time Division Multiple Access (STDMA) wireless mesh networks. We motivate the use of spatial reuse as performance metric and provide an explicit characterization of spatial reuse. We propose link scheduling algorithms based on certain graph models (communication graph, SINR graph) of the network. Our algorithms achieve higher spatial reuse than that of existing algorithms, with only a slight increase in computational complexity. (2) We investigate random access algorithms in wireless networks. We assume that the receiver is capable of power-based capture and propose a splitting algorithm that varies transmission powers of users on the basis of quaternary channel feedback. We model the algorithm dynamics by a Discrete Time Markov Chain and consequently show that its maximum stable throughput is 0.5518. Our algorithm achieves higher maximum stable throughput and significantly lower delay than the First Come First Serve (FCFS) splitting algorithm with uniform transmission power. (3) We consider the problem of flow control in packet networks from an information-theoretic perspective. We derive the maximum entropy of a flow which conforms to traffic constraints imposed by a generalized token bucket regulator (GTBR), by taking into account the covert information present in randomness of packet lengths.
Almost stable matchings in constant time
Venue: arXiv cs.DS 2008
Year: 2008

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose--accept rounds executed by the Gale--Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. This holds even if ties are present in the preference lists. We apply our results to give a distributed $(2+ε)$-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
Obtaining a Planar Graph by Vertex Deletion
Venue: arXiv cs.DS 2008
Year: 2008

In the k-Apex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour, there is an O(n^3) time algorithm for every fixed value of k. However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.
A Simple, Linear-Time Algorithm for x86 Jump Encoding
Venue: arXiv cs.PL 2008
Year: 2008

The problem of space-optimal jump encoding in the x86 instruction set, also known as branch displacement optimization, is described, and a linear-time algorithm is given that uses no complicated data structures, no recursion, and no randomization. The only assumption is that there are no array declarations whose size depends on the negative of the size of a section of code (Hyde 2006), which is reasonable for real code.
A New Clustering Algorithm Based Upon Flocking On Complex Network
Venue: arXiv cs.LG 2008
Year: 2008

We have proposed a model based upon flocking on a complex network, and then developed two clustering algorithms on the basis of it. In the algorithms, firstly a \textit{k}-nearest neighbor (knn) graph as a weighted and directed graph is produced among all data points in a dataset each of which is regarded as an agent who can move in space, and then a time-varying complex network is created by adding long-range links for each data point. Furthermore, each data point is not only acted by its \textit{k} nearest neighbors but also \textit{r} long-range neighbors through fields established in space by them together, so it will take a step along the direction of the vector sum of all fields. It is more important that these long-range links provides some hidden information for each data point when it moves and at the same time accelerate its speed converging to a center. As they move in space according to the proposed model, data points that belong to the same class are located at a same position gradually, whereas those that belong to different classes are away from one another. Consequently, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the rates of convergence of clustering algorithms are fast enough. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.
On Synchronous and Asynchronous Interaction in Distributed Systems
Venue: arXiv cs.LO 2008
Year: 2008

When considering distributed systems, it is a central issue how to deal with interactions between components. In this paper, we investigate the paradigms of synchronous and asynchronous interaction in the context of distributed systems. We investigate to what extent or under which conditions synchronous interaction is a valid concept for specification and implementation of such systems. We choose Petri nets as our system model and consider different notions of distribution by associating locations to elements of nets. First, we investigate the concept of simultaneity which is inherent in the semantics of Petri nets when transitions have multiple input places. We assume that tokens may only be taken instantaneously by transitions on the same location. We exhibit a hierarchy of `asynchronous' Petri net classes by different assumptions on possible distributions. Alternatively, we assume that the synchronisations specified in a Petri net are crucial system properties. Hence transitions and their preplaces may no longer placed on separate locations. We then answer the question which systems may be implemented in a distributed way without restricting concurrency, assuming that locations are inherently sequential. It turns out that in both settings we find semi-structural properties of Petri nets describing exactly the problematic situations for interactions in distributed systems.
Minimum-weight triangulation is NP-hard
Venue: arXiv cs.CG 2008
Year: 2008

A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard. We use a reduction from PLANAR-1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using dynamic programming on polygonal faces, as well as the beta-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation.
Gaussian Fading is the Worst Fading
Venue: arXiv cs.IT 2008
Year: 2008

The capacity of peak-power limited, single-antenna, non-coherent, flat-fading channels with memory is considered. The emphasis is on the capacity pre-log, i.e., on the limiting ratio of channel capacity to the logarithm of the signal-to-noise ratio (SNR), as the SNR tends to infinity. It is shown that, among all stationary and ergodic fading processes of a given spectral distribution function whose law has no mass point at zero, the Gaussian process gives rise to the smallest pre-log.
Parallel Evaluation of Mathematica Programs in Remote Computers Available in Network
Venue: arXiv cs.MS 2008
Year: 2008

Mathematica is a powerful application package for doing mathematics and is used almost in all branches of science. It has widespread applications ranging from quantum computation, statistical analysis, number theory, zoology, astronomy, and many more. Mathematica gives a rich set of programming extensions to its end-user language, and it permits us to write programs in procedural, functional, or logic (rule-based) style, or a mixture of all three. For tasks requiring interfaces to the external environment, mathematica provides mathlink, which allows us to communicate mathematica programs with external programs written in C, C++, F77, F90, F95, Java, or other languages. It has also extensive capabilities for editing graphics, equations, text, etc. In this article, we explore the basic mechanisms of parallelization of a mathematica program by sharing different parts of the program into all other computers available in the network. Doing the parallelization, we can perform large computational operations within a very short period of time, and therefore, the efficiency of the numerical works can be achieved. Parallel computation supports any version of mathematica and it also works as well even if different versions of mathematica are installed in different computers. The whole operation can run under any supported operating system like Unix, Windows, Macintosh, etc. Here we focus our study only for the Unix based operating system, but this method works as well for all other cases.
Representing graphs as the intersection of axis-parallel cubes
Venue: arXiv cs.DM 2008
Year: 2008

A unit cube in $k$ dimensional space (or \emph{$k$-cube} in short) is defined as the Cartesian product $R_1\times R_2\times...\times R_k$ where $R_i$(for $1\leq i\leq k$) is a closed interval of the form $[a_i,a_i+1]$ on the real line. A $k$-cube representation of a graph $G$ is a mapping of the vertices of $G$ to $k$-cubes such that two vertices in $G$ are adjacent if and only if their corresponding $k$-cubes have a non-empty intersection. The \emph{cubicity} of $G$, denoted as $\cubi(G)$, is the minimum $k$ such that $G$ has a $k$-cube representation. Roberts \cite{Roberts} showed that for any graph $G$ on $n$ vertices, $\cubi(G)\leq 2n/3$. Many NP-complete graph problems have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We present an efficient algorithm to compute the $k$-cube representation of $G$ with maximum degree $Δ$ in $O(Δ\ln b)$ dimensions where $b$ is the bandwidth of $G$. Bandwidth of $G$ is at most $n$ and can be much lower. The algorithm takes as input a bandwidth ordering of the vertices in $G$. Though computing the bandwidth ordering of vertices for a graph is NP-hard, there are heuristics that perform very well in practice. Even theoretically, there is an $O(\log^4 n)$ approximation algorithm for computing the bandwidth ordering of a graph using which our algorithm can produce a $k$-cube representation of any given graph in $k=O(Δ(\ln b + \ln\ln n))$ dimensions. Both the bounds on cubicity are shown to be tight upto a factor of $O(\log\log n)$.
A Polynomial Time Algorithm for The Traveling Salesman Problem
Venue: arXiv cs.DM 2008
Year: 2008

The ATSP polytope can be expressed by asymmetric polynomial size linear program.
Algebraic Soft-Decision Decoding of Reed-Solomon Codes Using Bit-level Soft Information
Venue: arXiv cs.IT 2008
Year: 2008

The performance of algebraic soft-decision decoding of Reed-Solomon codes using bit-level soft information is investigated. Optimal multiplicity assignment strategies of algebraic soft-decision decoding with infinite cost are first studied over erasure channels and the binary symmetric channel. The corresponding decoding radii are calculated in closed forms and tight bounds on the error probability are derived. The multiplicity assignment strategy and the corresponding performance analysis are then generalized to characterize the decoding region of algebraic softdecision decoding over a mixed error and bit-level erasure channel. The bit-level decoding region of the proposed multiplicity assignment strategy is shown to be significantly larger than that of conventional Berlekamp-Massey decoding. As an application, a bit-level generalized minimum distance decoding algorithm is proposed. The proposed decoding compares favorably with many other Reed-Solomon soft-decision decoding algorithms over various channels. Moreover, owing to the simplicity of the proposed bit-level generalized minimum distance decoding, its performance can be tightly bounded using order statistics.
An algebraic approach to complexity of data stream computations
Venue: arXiv cs.CC 2008
Year: 2008

We consider a basic problem in the general data streaming model, namely, to estimate a vector $f \in \Z^n$ that is arbitrarily updated (i.e., incremented or decremented) coordinate-wise. The estimate $\hat{f} \in \Z^n$ must satisfy $\norm{\hat{f}-f}_{\infty}\le ε\norm{f}_1 $, that is, $\forall i ~(\abs{\hat{f}_i - f_i} \le ε\norm{f}_1)$. It is known to have $\tilde{O}(ε^{-1})$ randomized space upper bound \cite{cm:jalgo}, $Ω(ε^{-1} \log (εn))$ space lower bound \cite{bkmt:sirocco03} and deterministic space upper bound of $\tildeΩ(ε^{-2})$ bits.\footnote{The $\tilde{O}$ and $\tildeΩ$ notations suppress poly-logarithmic factors in $n, \log ε^{-1}, \norm{f}_{\infty}$ and $\log δ^{-1}$, where, $δ$ is the error probability (for randomized algorithm).} We show that any deterministic algorithm for this problem requires space $Ω(ε^{-2} (\log \norm{f}_1))$ bits.
Adaptive Alternating Minimization Algorithms
Venue: arXiv cs.IT 2008
Year: 2008

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.
Ergodic Capacity of Discrete- and Continuous-Time, Frequency-Selective Rayleigh Fading Channels with Correlated Scattering
Venue: arXiv cs.IT 2008
Year: 2008

We study the ergodic capacity of a frequency-selective Rayleigh fading channel with correlated scattering, which finds application in the area of UWB. Under an average power constraint, we consider a single-user, single-antenna transmission. Coherent reception is assumed with full CSI at the receiver and no CSI at the transmitter. We distinguish between a continuous- and a discrete-time channel, modeled either as random process or random vector with generic covariance. As a practically relevant example, we examine an exponentially attenuated Ornstein-Uhlenbeck process in detail. Finally, we give numerical results, discuss the relation between the continuous- and the discrete-time channel model and show the significant impact of correlated scattering.
The Impact of CSI and Power Allocation on Relay Channel Capacity and Cooperation Strategies
Venue: arXiv cs.IT 2008
Year: 2008

Capacity gains from transmitter and receiver cooperation are compared in a relay network where the cooperating nodes are close together. Under quasi-static phase fading, when all nodes have equal average transmit power along with full channel state information (CSI), it is shown that transmitter cooperation outperforms receiver cooperation, whereas the opposite is true when power is optimally allocated among the cooperating nodes but only CSI at the receiver (CSIR) is available. When the nodes have equal power with CSIR only, cooperative schemes are shown to offer no capacity improvement over non-cooperation under the same network power constraint. When the system is under optimal power allocation with full CSI, the decode-and-forward transmitter cooperation rate is close to its cut-set capacity upper bound, and outperforms compress-and-forward receiver cooperation. Under fast Rayleigh fading in the high SNR regime, similar conclusions follow. Cooperative systems provide resilience to fading in channel magnitudes; however, capacity becomes more sensitive to power allocation, and the cooperating nodes need to be closer together for the decode-and-forward scheme to be capacity-achieving. Moreover, to realize capacity improvement, full CSI is necessary in transmitter cooperation, while in receiver cooperation optimal power allocation is essential.
On Delayed Sequential Coding of Correlated Sources
Venue: arXiv cs.IT 2008
Year: 2008

Motivated by video coding applications, the problem of sequential coding of correlated sources with encoding and/or decoding frame-delays is studied. The fundamental tradeoffs between individual frame rates, individual frame distortions, and encoding/decoding frame-delays are derived in terms of a single-letter information-theoretic characterization of the rate-distortion region for general inter-frame source correlations and certain types of potentially frame specific and coupled single-letter fidelity criteria. The sum-rate-distortion region is characterized in terms of generalized directed information measures highlighting their role in delayed sequential source coding problems. For video sources which are spatially stationary memoryless and temporally Gauss-Markov, MSE frame distortions, and a sum-rate constraint, our results expose the optimality of idealized differential predictive coding among all causal sequential coders, when the encoder uses a positive rate to describe each frame. Somewhat surprisingly, causal sequential encoding with one-frame-delayed noncausal sequential decoding can exactly match the sum-rate-MSE performance of joint coding for all nontrivial MSE-tuples satisfying certain positive semi-definiteness conditions. Thus, even a single frame-delay holds potential for yielding significant performance improvements. Generalizations to higher order Markov sources are also presented and discussed. A rate-distortion performance equivalence between, causal sequential encoding with delayed noncausal sequential decoding, and, delayed noncausal sequential encoding with causal sequential decoding, is also established.