OpenRaiser/Intern-Atlas huggingface dataset:
The heterogeneity of inter-contact time distributions: its importance for routing in delay tolerant networks
Venue: arXiv cs.NI 2007
Year: 2007

Prior work on routing in delay tolerant networks (DTNs) has commonly made the assumption that each pair of nodes shares the same inter-contact time distribution as every other pair. The main argument in this paper is that researchers should also be looking at heterogeneous inter-contact time distributions. We demonstrate the presence of such heterogeneity in the often-used Dartmouth Wi-Fi data set. We also show that DTN routing can benefit from knowing these distributions. We first introduce a new stochastic model focusing on the inter-contact time distributions between all pairs of nodes, which we validate on real connectivity patterns. We then analytically derive the mean delivery time for a bundle of information traversing the network for simple single copy routing schemes. The purpose is to examine the theoretic impact of heterogeneous inter-contact time distributions. Finally, we show that we can exploit this user diversity to improve routing performance.
A Continuum Theory for Unstructured Mesh Generation in Two Dimensions
Venue: arXiv cs.CG 2007
Year: 2007

A continuum description of unstructured meshes in two dimensions, both for planar and curved surface domains, is proposed. The meshes described are those which, in the limit of an increasingly finer mesh (smaller cells), and away from irregular vertices, have ideally-shaped cells (squares or equilateral triangles), and can therefore be completely described by two local properties: local cell size and local edge directions. The connection between the two properties is derived by defining a Riemannian manifold whose geodesics trace the edges of the mesh. A function $ϕ$, proportional to the logarithm of the cell size, is shown to obey the Poisson equation, with localized charges corresponding to irregular vertices. The problem of finding a suitable manifold for a given domain is thus shown to exactly reduce to an Inverse Poisson problem on $ϕ$, of finding a distribution of localized charges adhering to the conditions derived for boundary alignment. Possible applications to mesh generation are discussed.
Minimum-weight Cycle Covers and Their Approximability
Venue: arXiv cs.DS 2007
Year: 2007

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L. On the other hand, we prove that the problem cannot be approximated within a factor of 2-eps for certain sets L. For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O(n), where $n$ is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o(n). To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.
Multi-Antenna Cooperative Wireless Systems: A Diversity-Multiplexing Tradeoff Perspective
Venue: arXiv cs.IT 2007
Year: 2007

We consider a general multiple antenna network with multiple sources, multiple destinations and multiple relays in terms of the diversity-multiplexing tradeoff (DMT). We examine several subcases of this most general problem taking into account the processing capability of the relays (half-duplex or full-duplex), and the network geometry (clustered or non-clustered). We first study the multiple antenna relay channel with a full-duplex relay to understand the effect of increased degrees of freedom in the direct link. We find DMT upper bounds and investigate the achievable performance of decode-and-forward (DF), and compress-and-forward (CF) protocols. Our results suggest that while DF is DMT optimal when all terminals have one antenna each, it may not maintain its good performance when the degrees of freedom in the direct link is increased, whereas CF continues to perform optimally. We also study the multiple antenna relay channel with a half-duplex relay. We show that the half-duplex DMT behavior can significantly be different from the full-duplex case. We find that CF is DMT optimal for half-duplex relaying as well, and is the first protocol known to achieve the half-duplex relay DMT. We next study the multiple-access relay channel (MARC) DMT. Finally, we investigate a system with a single source-destination pair and multiple relays, each node with a single antenna, and show that even under the idealistic assumption of full-duplex relays and a clustered network, this virtual multi-input multi-output (MIMO) system can never fully mimic a real MIMO DMT. For cooperative systems with multiple sources and multiple destinations the same limitation remains to be in effect.
Computable Closed Euclidean Subsets with and without Computable Points
Venue: arXiv cs.LO 2007
Year: 2007

The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskii, Tseitin, Kreisel, and Lacombe assert the existence of NON-empty co-r.e. closed sets devoid of computable points: sets which are `large' in the sense of positive Lebesgue measure. We observe that a certain size is in fact necessary: every non-empty co-r.e. closed real set without computable points has continuum cardinality. This leads us to investigate for various classes of computable real subsets whether they necessarily contain a (not necessarily effectively findable) computable point.
Construction algorithm for network error-correcting codes attaining the Singleton bound
Venue: arXiv cs.IT 2007
Year: 2007

We give a centralized deterministic algorithm for constructing linear network error-correcting codes that attain the Singleton bound of network error-correcting codes. The proposed algorithm is based on the algorithm by Jaggi et al. We give estimates on the time complexity and the required symbol size of the proposed algorithm. We also estimate the probability of a random choice of local encoding vectors by all intermediate nodes giving a network error-correcting codes attaining the Singleton bound. We also clarify the relationship between the robust network coding and the network error-correcting codes with known locations of errors.
Boolean Functions, Projection Operators and Quantum Error Correcting Codes
Venue: arXiv cs.IT 2007
Year: 2007

This paper describes a fundamental correspondence between Boolean functions and projection operators in Hilbert space. The correspondence is widely applicable, and it is used in this paper to provide a common mathematical framework for the design of both additive and non-additive quantum error correcting codes. The new framework leads to the construction of a variety of codes including an infinite class of codes that extend the original ((5,6,2)) code found by Rains [21]. It also extends to operator quantum error correcting codes.
A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth
Venue: arXiv cs.DS 2007
Year: 2007

We present an efficient fixed-parameter algorithm for #SAT parameterized by the incidence treewidth, i.e., the treewidth of the bipartite graph whose vertices are the variables and clauses of the given CNF formula; a variable and a clause are joined by an edge if and only if the variable occurs in the clause. Our algorithm runs in time O(4^k k l N), where k denotes the incidence treewidth, l denotes the size of a largest clause, and N denotes the number of nodes of the tree-decomposition.
Dense-Timed Petri Nets: Checking Zenoness, Token liveness and Boundedness
Venue: arXiv cs.LO 2007
Year: 2007

We consider Dense-Timed Petri Nets (TPN), an extension of Petri nets in which each token is equipped with a real-valued clock and where the semantics is lazy (i.e., enabled transitions need not fire; time can pass and disable transitions). We consider the following verification problems for TPNs. (i) Zenoness: whether there exists a zeno-computation from a given marking, i.e., an infinite computation which takes only a finite amount of time. We show decidability of zenoness for TPNs, thus solving an open problem from [Escrig et al.]. Furthermore, the related question if there exist arbitrarily fast computations from a given marking is also decidable. On the other hand, universal zenoness, i.e., the question if all infinite computations from a given marking are zeno, is undecidable. (ii) Token liveness: whether a token is alive in a marking, i.e., whether there is a computation from the marking which eventually consumes the token. We show decidability of the problem by reducing it to the coverability problem, which is decidable for TPNs. (iii) Boundedness: whether the size of the reachable markings is bounded. We consider two versions of the problem; namely semantic boundedness where only live tokens are taken into consideration in the markings, and syntactic boundedness where also dead tokens are considered. We show undecidability of semantic boundedness, while we prove that syntactic boundedness is decidable through an extension of the Karp-Miller algorithm.
Zig-zag and Replacement Product Graphs and LDPC Codes
Venue: arXiv cs.IT 2007
Year: 2007

The performance of codes defined from graphs depends on the expansion property of the underlying graph in a crucial way. Graph products, such as the zig-zag product and replacement product provide new infinite families of constant degree expander graphs. The paper investigates the use of zig-zag and replacement product graphs for the construction of codes on graphs. A modification of the zig-zag product is also introduced, which can operate on two unbalanced biregular bipartite graphs.
On the Peak-to-Mean Envelope Power Ratio of Phase-Shifted Binary Codes
Venue: arXiv cs.IT 2007
Year: 2007

The peak-to-mean envelope power ratio (PMEPR) of a code employed in orthogonal frequency-division multiplexing (OFDM) systems can be reduced by permuting its coordinates and by rotating each coordinate by a fixed phase shift. Motivated by some previous designs of phase shifts using suboptimal methods, the following question is considered in this paper. For a given binary code, how much PMEPR reduction can be achieved when the phase shifts are taken from a 2^h-ary phase-shift keying (2^h-PSK) constellation? A lower bound on the achievable PMEPR is established, which is related to the covering radius of the binary code. Generally speaking, the achievable region of the PMEPR shrinks as the covering radius of the binary code decreases. The bound is then applied to some well understood codes, including nonredundant BPSK signaling, BCH codes and their duals, Reed-Muller codes, and convolutional codes. It is demonstrated that most (presumably not optimal) phase-shift designs from the literature attain or approach our bound.
Articulation entre composantes verbale et graphico-gestuelle de l'interaction dans des réunions de conception architecturale
Venue: arXiv cs.HC 2007
Year: 2007

This study is focused on the role of external representations, e.g., skteches, in collaborative architectural design. In particular, we analyse (1) the use of graphico-gestural modalities and, (2) the articulation modes between graphico-gestural and verbal modalities in design interaction. We have elaborated a first classification which distinguishes between two modes of articulation, articulation in integrated activities versus articulation in parallel activities.
Memory of past designs: distinctive roles in individual and collective design
Venue: arXiv cs.HC 2007
Year: 2007

Empirical studies on design have emphasised the role of memory of past solutions. Design involves the use of generic knowledge as well as episodic knowledge about past designs for analogous problems : in this way, it involves the reuse of past designs. We analyse this mechanism of reuse from a socio-cognitive viewpoint. According to a purely cognitive approach, reuse involves cognitive mechanisms linked to the problem solving activity itself. Our socio-cognitive approach accounts for these phenomena as well as reuse mechanisms linked to cooperation, in particular coordination, and confrontation/integration of viewpoints.
The Dichotomy of Conjunctive Queries on Probabilistic Structures
Venue: arXiv cs.DB 2007
Year: 2007

We show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either \PTIME or #¶-complete, and we give an algorithm for deciding whether a given conjunctive query is \PTIME or #¶-complete. The dichotomy property is a fundamental result on query evaluation on probabilistic databases and it gives a complete classification of the complexity of conjunctive queries.
On simulating nondeterministic stochastic activity networks
Venue: arXiv cs.DM 2007
Year: 2007

In this work we deal with a mechanism for process simulation called a NonDeterministic Stochastic Activity Network (NDSAN). An NDSAN consists basically of a set of activities along with precedence relations involving these activities, which determine their order of execution. Activity durations are stochastic, given by continuous, nonnegative random variables. The nondeterministic behavior of an NDSAN is based on two additional possibilities: (i) by associating choice probabilities with groups of activities, some branches of execution may not be taken; (ii) by allowing iterated executions of groups of activities according to predetermined probabilities, the number of times an activity must be executed is not determined a priori. These properties lead to a rich variety of activity networks, capable of modeling many real situations in process engineering, project design, and troubleshooting. We describe a recursive simulation algorithm for NDSANs, whose repeated execution produces a close approximation to the probability distribution of the completion time of the entire network. We also report on real-world case studies.
Energy-Efficient Power Control in Impulse Radio UWB Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a game-theoretic model for studying power control for wireless data networks in frequency-selective multipath environments is analyzed. The uplink of an impulse-radio ultrawideband system is considered. The effects of self-interference and multiple-access interference on the performance of generic Rake receivers are investigated for synchronous systems. Focusing on energy efficiency, a noncooperative game is proposed in which users in the network are allowed to choose their transmit powers to maximize their own utilities, and the Nash equilibrium for the proposed game is derived. It is shown that, due to the frequency selective multipath, the noncooperative solution is achieved at different signal-to-interference-plus-noise ratios, depending on the channel realization and the type of Rake receiver employed. A large-system analysis is performed to derive explicit expressions for the achieved utilities. The Pareto-optimal (cooperative) solution is also discussed and compared with the noncooperative approach.
A Counterexample to a Proposed Proof of P=NP by S. Gubin
Venue: arXiv cs.CC 2007
Year: 2007

In a recent paper by S. Gubin [cs/0701023v1], a polynomial-time solution to the 3SAT problem was presented as proof that P=NP. The proposed algorithm cannot be made to work, which I shall demonstrate.
Space-Time-Frequency Degrees of Freedom: Fundamental Limits for Spatial Information
Venue: arXiv cs.IT 2007
Year: 2007

We bound the number of electromagnetic signals which may be observed over a frequency range $[F-W,F+W]$ a time interval $[0,T]$ within a sphere of radius $R$. We show that the such constrained signals may be represented by a series expansion whose terms are bounded exponentially to zero beyond a threshold. Our result implies there is a finite amount of information which may be extracted from a region of space via electromagnetic radiation.
Cooperative Optimization for Energy Minimization: A Case Study of Stereo Matching
Venue: arXiv cs.CV 2007
Year: 2007

Often times, individuals working together as a team can solve hard problems beyond the capability of any individual in the team. Cooperative optimization is a newly proposed general method for attacking hard optimization problems inspired by cooperation principles in team playing. It has an established theoretical foundation and has demonstrated outstanding performances in solving real-world optimization problems. With some general settings, a cooperative optimization algorithm has a unique equilibrium and converges to it with an exponential rate regardless initial conditions and insensitive to perturbations. It also possesses a number of global optimality conditions for identifying global optima so that it can terminate its search process efficiently. This paper offers a general description of cooperative optimization, addresses a number of design issues, and presents a case study to demonstrate its power.
Enhancing Sensor Network Lifetime Using Interactive Communication
Venue: arXiv cs.IT 2007
Year: 2007

We are concerned with maximizing the lifetime of a data-gathering wireless sensor network consisting of set of nodes directly communicating with a base-station. We model this scenario as the m-message interactive communication between multiple correlated informants (sensor nodes) and a recipient (base-station). With this framework, we show that m-message interactive communication can indeed enhance network lifetime. Both worst-case and average-case performances are considered.
Hierarchical Decoupling Principle of a MIMO-CDMA Channel in Asymptotic Limits
Venue: arXiv cs.IT 2007
Year: 2007

We analyze an uplink of a fast flat fading MIMO-CDMA channel in the case where the data symbol vector for each user follows an arbitrary distribution. The spectral efficiency of the channel with CSI at the receiver is evaluated analytically with the replica method. The main result is that the hierarchical decoupling principle holds in the MIMO-CDMA channel, i.e., the MIMO-CDMA channel is decoupled into a bank of single-user MIMO channels in the many-user limit, and each single-user MIMO channel is further decoupled into a bank of scalar Gaussian channels in the many-antenna limit for a fading model with a limited number of scatterers.
Open-architecture Implementation of Fragment Molecular Orbital Method for Peta-scale Computing
Venue: arXiv cs.DC 2007
Year: 2007

We present our perspective and goals on highperformance computing for nanoscience in accordance with the global trend toward "peta-scale computing." After reviewing our results obtained through the grid-enabled version of the fragment molecular orbital method (FMO) on the grid testbed by the Japanese Grid Project, National Research Grid Initiative (NAREGI), we show that FMO is one of the best candidates for peta-scale applications by predicting its effective performance in peta-scale computers. Finally, we introduce our new project constructing a peta-scale application in an open-architecture implementation of FMO in order to realize both goals of highperformance in peta-scale computers and extendibility to multiphysics simulations.
Analysis of the Sufficient Path Elimination Window for the Maximum-Likelihood Sequential-Search Decoding Algorithm for Binary Convolutional Codes
Venue: arXiv cs.IT 2007
Year: 2007

A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cutoff rate, the average decoding complexity per information bit and the required stack size grow rapidly with the information length. In order to alleviate the problem in the maximum-likelihood sequential decoding algorithm (MLSDA), we propose to directly eliminate the top path whose end node is $Δ$-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search. Following random coding argument, we analyze the early-elimination window $Δ$ that results in negligible performance degradation for the MLSDA. Our analytical results indicate that the required early elimination window for negligible performance degradation is just twice of the constraint length for rate one-half convolutional codes. For rate one-third convolutional codes, the required early-elimination window even reduces to the constraint length. The suggestive theoretical level thresholds almost coincide with the simulation results. As a consequence of the small early-elimination window required for near maximum-likelihood performance, the MLSDA with early-elimination modification rules out considerable computational burdens, as well as memory requirement, by directly eliminating a big number of the top paths, which makes the MLSDA with early elimination very suitable for applications that dictate a low-complexity software implementation with near maximum-likelihood performance.
MacWilliams Identity for the Rank Metric
Venue: arXiv cs.IT 2007
Year: 2007

This paper investigates the relationship between the rank weight distribution of a linear code and that of its dual code. The main result of this paper is that, similar to the MacWilliams identity for the Hamming metric, the rank weight distribution of any linear code can be expressed as an analytical expression of that of its dual code. Remarkably, our new identity has a similar form to the MacWilliams identity for the Hamming metric. Our new identity provides a significant analytical tool to the rank weight distribution analysis of linear codes. We use a linear space based approach in the proof for our new identity, and adapt this approach to provide an alternative proof of the MacWilliams identity for the Hamming metric. Finally, we determine the relationship between moments of the rank distribution of a linear code and those of its dual code, and provide an alternative derivation of the rank weight distribution of maximum rank distance codes.
Maximum Entropy in the framework of Algebraic Statistics: A First Step
Venue: arXiv cs.IT 2007
Year: 2007

Algebraic statistics is a recently evolving field, where one would treat statistical models as algebraic objects and thereby use tools from computational commutative algebra and algebraic geometry in the analysis and computation of statistical models. In this approach, calculation of parameters of statistical models amounts to solving set of polynomial equations in several variables, for which one can use celebrated Grobner bases theory. Owing to the important role of information theory in statistics, this paper as a first step, explores the possibility of describing maximum and minimum entropy (ME) models in the framework of algebraic statistics. We show that ME-models are toric models (a class of algebraic statistical models) when the constraint functions (that provide the information about the underlying random variable) are integer valued functions, and the set of statistical models that results from ME-methods are indeed an affine variety.
The framework for simulation of dynamics of mechanical aggregates
Venue: arXiv cs.CE 2007
Year: 2007

A framework for simulation of dynamics of mechanical aggregates has been developed. This framework enables us to build model of aggregate from models of its parts. Framework is a part of universal framework for science and engineering.