Search

Large Language Models (LLMs) have demonstrated great performance in few-shot In-Context Learning (ICL) for a variety of generative and discriminative chemical design tasks. The newly expanded context windows of LLMs can further improve ICL capabilities for molecular inverse design and lead optimization. To take full advantage of these capabilities we developed a new semi-supervised learning method that overcomes the lack of experimental data available for many-shot ICL. Our approach involves iterative inclusion of LLM generated molecules with high predicted performance, along with experimental data. We further integrated our method in a multi-modal LLM which allows for the interactive modification of generated molecular structures using text instructions. As we show, the new method greatly improves upon existing ICL methods for molecular design while being accessible and easy to use for scientists.

Drilling, grinding, and setting anchors on vertical walls are fundamental processes in everyday construction work. Manually doing these works is error-prone, potentially dangerous, and elaborate at height. Today, heavy mobile ground robots can perform automatic power tool work. However, aerial vehicles could be deployed in untraversable environments and reach inaccessible places. Existing drone designs do not provide the large forces, payload, and high precision required for using power tools. This work presents the first aerial robot design to perform versatile manipulation tasks on vertical concrete walls with continuous forces of up to 150 N. The platform combines a quadrotor with active suction cups for perching on walls and a lightweight, tiltable linear tool table. This combination minimizes weight using the propulsion system for flying, surface alignment, and feed during manipulation and allows precise positioning of the power tool. We evaluate our design in a concrete drilling application - a challenging construction process that requires high forces, accuracy, and precision. In 30 trials, our design can accurately pinpoint a target position despite perching imprecision. Nine visually guided drilling experiments demonstrate a drilling precision of 6 mm without further automation. Aside from drilling, we also demonstrate the versatility of the design by setting an anchor into concrete., Comment: Will appear in IEEE International Conference on Intelligent Robots and Systems (IROS) 2023. Winner of IROS Best Paper Award on Mobile Manipulation sponsored by OMRON Sinic X Corp

With recent progress in the field of Explainable Artificial Intelligence (XAI) and increasing use in practice, the need for an evaluation of different XAI methods and their explanation quality in practical usage scenarios arises. For this purpose, we present VitrAI, which is a web-based service with the goal of uniformly demonstrating four different XAI algorithms in the context of three real life scenarios and evaluating their performance and comprehensibility for humans. This work reveals practical obstacles when adopting XAI methods and gives qualitative estimates on how well different approaches perform in said scenarios., Comment: Accepted for IntelliSys 2021

Advances in artificial intelligence have renewed interest in conversational agents. Additionally to software developers, today all kinds of employees show interest in new technologies and their possible applications for customers. German insurance companies generally are interested in improving their customer service and digitizing their business processes. In this work we investigate the potential use of conversational agents in insurance companies theoretically by determining which classes of agents exist which are of interest to insurance companies, finding relevant use cases and requirements. We add two practical parts: First we develop a showcase prototype for an exemplary insurance scenario in claim management. Additionally in a second step, we create a prototype focusing on customer service in a chatbot hackathon, fostering innovation in interdisciplinary teams. In this work, we describe the results of both prototypes in detail. We evaluate both chatbots defining criteria for both settings in detail and compare the results and draw conclusions for the maturity of chatbot technology for practical use, describing the opportunities and challenges companies, especially small and medium enterprises, face., Comment: 26 pages, 7 figures. ICAART 2019 extension. Extension of arXiv:1812.07339

Business success of companies heavily depends on the availability and performance of their client applications. Due to modern development paradigms such as DevOps and microservice architectural styles, applications are decoupled into services with complex interactions and dependencies. Although these paradigms enable individual development cycles with reduced delivery times, they cause several challenges to manage the services in distributed systems. One major challenge is to observe and monitor such distributed systems. This paper provides a qualitative study to understand the challenges and good practices in the field of observability and monitoring of distributed systems. In 28 semi-structured interviews with software professionals we discovered increasing complexity and dynamics in that field. Especially observability becomes an essential prerequisite to ensure stable services and further development of client applications. However, the participants mentioned a discrepancy in the awareness regarding the importance of the topic, both from the management as well as from the developer perspective. Besides technical challenges, we identified a strong need for an organizational concept including strategy, roles and responsibilities. Our results support practitioners in developing and implementing systematic observability and monitoring for distributed systems.

Advances in artificial intelligence have renewed interest in conversational agents. So-called chatbots have reached maturity for industrial applications. German insurance companies are interested in improving their customer service and digitizing their business processes. In this work we investigate the potential use of conversational agents in insurance companies by determining which classes of agents are of interest to insurance companies, finding relevant use cases and requirements, and developing a prototype for an exemplary insurance scenario. Based on this approach, we derive key findings for conversational agent implementation in insurance companies., Comment: 12 pages, 6 figure, accepted for presentation at The International Conference on Agents and Artificial Intelligence 2019 (ICAART 2019)

The Scalable Brain Atlas (SBA) is a collection of web services that provide unified access to a large collection of brain atlas templates for different species. Its main component is an atlas viewer that displays brain atlas data as a stack of slices in which stereotaxic coordinates and brain regions can be selected. These are subsequently used to launch web queries to resources that require coordinates or region names as input. It supports plugins which run inside the viewer and respond when a new slice, coordinate or region is selected. It contains 20 atlas templates in six species, and plugins to compute coordinate transformations, display anatomical connectivity and fiducial points, and retrieve properties, descriptions, definitions and 3d reconstructions of brain regions. The ambition of SBA is to provide a unified representation of all publicly available brain atlases directly in the web browser, while remaining a responsive and light weight resource that specializes in atlas comparisons, searches, coordinate transformations and interactive displays., Comment: Rolf K\"otter sadly passed away on June 9th, 2010. He co-initiated this project and played a crucial role in the design and quality assurance of the Scalable Brain Atlas

Some types of medical and topographic imaging device produce images in which the pixel values are "phase-wrapped", i.e. measured modulus a known scalar. Phase unwrapping can be viewed as the problem of inferring the number of shifts between each and every pair of neighboring pixels, subject to an a priori preference for smooth surfaces, and subject to a zero curl constraint, which requires that the shifts must sum to 0 around every loop. We formulate phase unwrapping as a mean field inference problem in a Markov network, where the prior favors the zero curl constraint. We compare our mean field technique with the least squares method on a synthetic 100x100 image, and give results on a 512x512 synthetic aperture radar image from Sandia National Laboratories., Comment: Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

A family of equivalence tools for bounding network capacities is introduced. Part I treats networks of point-to-point channels. The main result is roughly as follows. Given a network of noisy, independent, memoryless point-to-point channels, a collection of communication demands can be met on the given network if and only if it can be met on another network where each noisy channel is replaced by a noiseless bit pipe with throughput equal to the noisy channel capacity. This result was known previously for the case of a single-source multicast demand. The result given here treats general demands -- including, for example, multiple unicast demands -- and applies even when the achievable rate region for the corresponding demands is unknown in the noiseless network. In part II, definitions of upper and lower bounding channel models for general channels are introduced. By these definitions, a collection of communication demands can be met on a network of independent channels if it can be met on a network where each channel is replaced by its lower bounding model andonly if it can be met on a network where each channel is replaced by its upper bounding model. This work derives general conditions under which a network of noiseless bit pipes is an upper or lower bounding model for a multiterminal channel. Example upper and lower bounding models for broadcast, multiple access, and interference channels are given. It is then shown that bounding the difference between the upper and lower bounding models for a given channel yields bounds on the accuracy of network capacity bounds derived using those models. By bounding the capacity of a network of independent noisy channels by the network coding capacity of a network of noiseless bit pipes, this approach represents one step towards the goal of building computational tools for bounding network capacities., Comment: 91 pages, 18 figures. Submitted to the IEEE Transactions on Information Theory on April 14, 2010. Draft 2

The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given., Comment: 15 pages, 3 tables

Consider a relay cascade, i.e. a network where a source node, a sink node and a certain number of intermediate source/relay nodes are arranged on a line and where adjacent node pairs are connected by error-free (q+1)-ary pipes. Suppose the source and a subset of the relays wish to communicate independent information to the sink under the condition that each relay in the cascade is half-duplex constrained. A coding scheme is developed which transfers information by an information-dependent allocation of the transmission and reception slots of the relays. The coding scheme requires synchronization on the symbol level through a shared clock. The coding strategy achieves capacity for a single source. Numerical values for the capacity of cascades of various lengths are provided, and the capacities are significantly higher than the rates which are achievable with a predetermined time-sharing approach. If the cascade includes a source and a certain number of relays with their own information, the strategy achieves the cut-set bound when the rates of the relay sources fall below certain thresholds. For cascades composed of an infinite number of half-duplex constrained relays and a single source, we derive an explicit capacity expression. Remarkably, the capacity in bits/use for q=1 is equal to the logarithm of the golden ratio, and the capacity for q=2 is 1 bit/use., Comment: accepted for publication in IEEE Transactions on Information Theory

Random linear network coding can be used in peer-to-peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient., Comment: 26 pages, 9 figures, Submitted to IEEE Journal on Selected Areas in Communications (JSAC) "Mission Critical Networking"

In this paper, we propose a scheme, called the "algebraic watchdog" for wireless network coding, in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages, and, thus, provide a secure global "self-checking network". Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. This work is inspired by Marti et. al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. As the first building block of a such system, we focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. In addition, we present an algebraic analysis of the performance using an hypothesis testing framework, that provides exact formulae for probabilities of false detection and misdetection., Comment: 5 pages, 4 figures, submitted to IEEE International Symposium on Information Theory (ISIT) 2009. This is the final version. The content has been changed to incorporate reviewer comments and recent results

The problem of serving multicast flows in a crossbar switch is considered. Intra-flow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph. When applied to KxN switches with unicasts and broadcasts only, this gives a bound of min{(2K-1)/K,2N/(N+1)} on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region., Comment: 26 pages, 27 figures, submitted to IEEE Transactions on Information Theory

This paper is motivated by the problem of error control in network coding when errors are introduced in a random fashion (rather than chosen by an adversary). An additive-multiplicative matrix channel is considered as a model for random network coding. The model assumes that n packets of length m are transmitted over the network, and up to t erroneous packets are randomly chosen and injected into the network. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of large field or matrix size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has decoding complexity O(n^2 m) and a probability of error that decreases exponentially both in the packet length and in the field size in bits. Extensions of these results for coherent network coding are also presented., Comment: 24 pages, to be published at the IEEE Transactions on Information Theory

Two types of noise-free relay cascades are investigated. Networks where a source communicates with a distant receiver via a cascade of half-duplex constrained relays, and networks where not only the source but also a single relay node intends to transmit information to the same destination. We introduce two relay channel models, capturing the half-duplex constraint, and within the framework of these models capacity is determined for the first network type. It turns out that capacity is significantly higher than the rates which are achievable with a straightforward time-sharing approach. A capacity achieving coding strategy is presented based on allocating the transmit and receive time slots of a node in dependence of the node's previously received data. For the networks of the second type, an upper bound to the rate region is derived from the cut-set bound. Further, achievability of the cut-set bound in the single relay case is shown given that the source rate exceeds a certain minimum value., Comment: Proceedings of the 2008 IEEE International Symposium on Information Theory, Toronto, ON, Canada, July 6 - 11, 2008

The problem of error control in random linear network coding is addressed from a matrix perspective that is closely related to the subspace perspective of K\"otter and Kschischang. A large class of constant-dimension subspace codes is investigated. It is shown that codes in this class can be easily constructed from rank-metric codes, while preserving their distance properties. Moreover, it is shown that minimum distance decoding of such subspace codes can be reformulated as a generalized decoding problem for rank-metric codes where partial information about the error is available. This partial information may be in the form of erasures (knowledge of an error location but not its value) and deviations (knowledge of an error value but not its location). Taking erasures and deviations into account (when they occur) strictly increases the error correction capability of a code: if $\mu$ erasures and $\delta$ deviations occur, then errors of rank $t$ can always be corrected provided that $2t \leq d - 1 + \mu + \delta$, where $d$ is the minimum rank distance of the code. For Gabidulin codes, an important family of maximum rank distance codes, an efficient decoding algorithm is proposed that can properly exploit erasures and deviations. In a network coding application where $n$ packets of length $M$ over $F_q$ are transmitted, the complexity of the decoding algorithm is given by $O(dM)$ operations in an extension field $F_{q^n}$., Comment: Minor corrections; 42 pages, to be published at the IEEE Transactions on Information Theory

We present an algorithm for systematic encoding of Hermitian codes. For a Hermitian code defined over GF(q^2), the proposed algorithm achieves a run time complexity of O(q^2) and is suitable for VLSI implementation. The encoder architecture uses as main blocks q varying-rate Reed-Solomon encoders and achieves a space complexity of O(q^2) in terms of finite field multipliers and memory elements., Comment: 5 Pages, Accepted in IEEE International Symposium on Information Theory ISIT 2007

The problem of error-control in random linear network coding is considered. A ``noncoherent'' or ``channel oblivious'' model is assumed where neither transmitter nor receiver is assumed to have knowledge of the channel transfer characteristic. Motivated by the property that linear network coding is vector-space preserving, information transmission is modelled as the injection into the network of a basis for a vector space $V$ and the collection by the receiver of a basis for a vector space $U$. A metric on the projective geometry associated with the packet space is introduced, and it is shown that a minimum distance decoder for this metric achieves correct decoding if the dimension of the space $V \cap U$ is sufficiently large. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or, equivalently, a subset of the vertices of the corresponding Grassmann graph. Sphere-packing and sphere-covering bounds as well as a generalization of the Singleton bound are provided for such codes. Finally, a Reed-Solomon-like code construction, related to Gabidulin's construction of maximum rank-distance codes, is described and a Sudan-style ``list-1'' minimum distance decoding algorithm is provided., Comment: This revised paper contains some minor changes and clarifications

In recent years, network coding has been investigated as a method to obtain improvements in wireless networks. A typical assumption of previous work is that relay nodes performing network coding can decode the messages from sources perfectly. On a simple relay network, we design a scheme to obtain network coding gain even when the relay node cannot perfectly decode its received messages. In our scheme, the operation at the relay node resembles message passing in belief propagation, sending the logarithm likelihood ratio (LLR) of the network coded message to the destination. Simulation results demonstrate the gain obtained over different channel conditions. The goal of this paper is not to give a theoretical result, but to point to possible interaction of network coding with user cooperation in noisy scenario. The extrinsic information transfer (EXIT) chart is shown to be a useful engineering tool to analyze the performance of joint channel coding and network coding in the network.

We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if network coding were not allowed. Thus, network coding leads to a larger rate region in a multicast crossbar switch. We demonstrate a traffic pattern which requires a switch speedup if coding is not allowed, whereas, with coding the speedup requirement is eliminated completely. In addition to throughput benefits, coding simplifies the characterization of the rate region. We give a graph-theoretic characterization of the rate region with fanout splitting and intra-flow coding, in terms of the stable set polytope of the 'enhanced conflict graph' of the traffic pattern. Such a formulation is not known in the case of fanout splitting without coding. We show that computing the offline schedule (i.e. using prior knowledge of the flow arrival rates) can be reduced to certain graph coloring problems. Finally, we propose online algorithms (i.e. using only the current queue occupancy information) for multicast scheduling based on our graph-theoretic formulation. In particular, we show that a maximum weighted stable set algorithm stabilizes the queues for all rates within the rate region., Comment: 9 pages, submitted to IEEE INFOCOM 2007

We examine the issue of separation and code design for networks that operate over finite fields. We demonstrate that source-channel (or source-network) separation holds for several canonical network examples like the noisy multiple access channel and the erasure degraded broadcast channel, when the whole network operates over a common finite field. This robustness of separation is predicated on the fact that noise and inputs are independent, and we examine the failure of separation when noise is dependent on inputs in multiple access channels. Our approach is based on the sufficiency of linear codes. Using a simple and unifying framework, we not only re-establish with economy the optimality of linear codes for single-transmitter, single-receiver channels and for Slepian-Wolf source coding, but also establish the optimality of linear codes for multiple access and for erasure degraded broadcast channels. The linearity allows us to obtain simple optimal code constructions and to study capacity regions of the noisy multiple access and the degraded broadcast channel. The linearity of both source and network coding blurs the delineation between source and network codes. While our results point to the fact that separation of source coding and channel coding is optimal in some canonical networks, we show that decomposing networks into canonical subnetworks may not be effective. Thus, we argue that it may be the lack of decomposability of a network into canonical network modules, rather than the lack of separation between source and channel coding, that presents major challenges for coding over networks.

Whereas many results are known about thresholds for ensembles of low-density parity-check codes under message-passing iterative decoding, this is not the case for linear programming decoding. Towards closing this knowledge gap, this paper presents some bounds on the thresholds of low-density parity-check code ensembles under linear programming decoding.

We consider linear-programming (LP) decoding of low-density parity-check (LDPC) codes. While it is clear that one can use any general-purpose LP solver to solve the LP that appears in the decoding problem, we argue in this paper that the LP at hand is equipped with a lot of structure that one should take advantage of. Towards this goal, we study the dual LP and show how coordinate-ascent methods lead to very simple update rules that are tightly connected to the min-sum algorithm. Moreover, replacing minima in the formula of the dual LP with soft-minima one obtains update rules that are tightly connected to the sum-product algorithm. This shows that LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible. Finally, we also discuss some sub-gradient-based methods.

In his thesis, Wiberg showed the existence of thresholds for families of regular low-density parity-check codes under min-sum algorithm decoding. He also derived analytic bounds on these thresholds. In this paper, we formulate similar results for linear programming decoding of regular low-density parity-check codes.

The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes., Comment: Submitted to IEEE Transactions on Information Theory, December 2005

We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a block of packets before sending out coded packets. Rather, whenever they have a transmission opportunity, they send out coded packets formed from random linear combinations of previously received packets. All coding and decoding operations have polynomial complexity. We show that the scheme is capacity-achieving as long as packets received on a link arrive according to a process that has an average rate. Thus, packet losses on a link may exhibit correlation in time or with losses on other links. In the special case of Poisson traffic with i.i.d. losses, we give error exponents that quantify the rate of decay of the probability of error with coding delay. Our analysis of the scheme shows that it is not only capacity-achieving, but that the propagation of packets carrying "innovative" information follows the propagation of jobs through a queueing network, and therefore fluid flow models yield good approximations. We consider networks with both lossy point-to-point and broadcast links, allowing us to model both wireline and wireless packet networks., Comment: 33 pages, 6 figures; revised appendix

An important property of high-performance, low complexity codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message passing algorithms and decoding based on linear programming, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so called fundamental cone in Euclidean space which is a function of a given parity check matrix of a code, rather than of the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental polytope as the Newton polytope of the Hashimoto edge zeta function of the underlying graph., Comment: Submitted, August 2005

In "On Coding for Reliable Communication over Packet Networks" (Lun, Medard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding scheme for unicast or multicast over lossy wireline or wireless packet networks is presented. We extend that paper's results in two ways: First, we extend the network model to allow packets received on a link to arrive according to any process with an average rate, as opposed to the assumption of Poisson traffic with i.i.d. losses that was previously made. Second, in the case of Poisson traffic with i.i.d. losses, we derive error exponents that quantify the rate at which the probability of error decays with coding delay., Comment: 5 pages; to appear in Proc. 2005 IEEE International Symposium on Information Theory (ISIT 2005)

Consider data transmission over a binary-input additive white Gaussian noise channel using a binary low-density parity-check code. We ask the following question: Given a decoder that takes log-likelihood ratios as input, does it help to modify the log-likelihood ratios before decoding? If we use an optimal decoder then it is clear that modifying the log-likelihoods cannot possibly help the decoder's performance, and so the answer is "no." However, for a suboptimal decoder like the linear programming decoder, the answer might be "yes": In this paper we prove that for certain interesting classes of low-density parity-check codes and large enough SNRs, it is advantageous to truncate the log-likelihood ratios before passing them to the linear programming decoder., Comment: To appear in Proc. 2005 IEEE International Symposium on Information Theory, Adelaide, Australia, September 4-9, 2005

We give an information flow interpretation for multicasting using network coding. This generalizes the fluid model used to represent flows to a single receiver. Using the generalized model, we present a decentralized algorithm to minimize the number of packets that undergo network coding. We also propose a decentralized algorithm to construct capacity achieving multicast codes when the processing at some nodes is restricted to routing. The proposed algorithms can be coupled with existing decentralized schemes to achieve minimum cost muticast., Comment: accepted for publication at ISIT 2005

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e. packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved., Comment: 17 pages, 6 figures; to appear in IEEE Transactions on Information Theory (special issue on Networking and Information Theory); revised version, with major changes

Cycle codes are a special case of low-density parity-check (LDPC) codes and as such can be decoded using an iterative message-passing decoding algorithm on the associated Tanner graph. The existence of pseudo-codewords is known to cause the decoding algorithm to fail in certain instances. In this paper, we draw a connection between pseudo-codewords of cycle codes and the so-called edge zeta function of the associated normal graph and show how the Newton polyhedron of the zeta function equals the fundamental cone of the code, which plays a crucial role in characterizing the performance of iterative decoding algorithms., Comment: Presented at Information Theory Workshop (ITW), San Antonio, TX, 2004