OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Capacity of Gaussian Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

We present an achievable rate for general Gaussian relay networks. We show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the topology of the network, but not the values of the channel gains. Therefore, we uniformly characterize the capacity of Gaussian relay networks within a constant number of bits, for all channel parameters.
Towards a formalization of budgets
Venue: arXiv cs.LO 2008
Year: 2008

We go into the need for, and the requirements on, a formal theory of budgets. We present a simple algebraic theory of rational budgets, i.e., budgets in which amounts of money are specified by functions on the rational numbers. This theory is based on the tuplix calculus. We go into the importance of using totalized models for the rational numbers. We present a case study on the educational budget of a university department offering master programs.
Dynamic data models: an application of MOP-based persistence in Common Lisp
Venue: arXiv cs.SE 2008
Year: 2008

The data model of an application, the nature and format of data stored across executions, is typically a very rigid part of its early specification, even when prototyping, and changing it after code that relies on it was written can prove quite expensive and error-prone. Code and data in a running Lisp image can be dynamically modified. A MOP-based persistence library can bring this dynamicity to the data model. This enables to extend the easy prototyping way of development to the storage of data and helps avoiding interruptions of service. This article presents the conditions to do this portably and transparently.
Outward Accessibility in Urban Street Networks: Characterization and Improvements
Venue: arXiv cs.CY 2008
Year: 2008

The dynamics of transportation through towns and cities is strongly affected by the topology of the connections and routes. The current work describes an approach combining complex networks and self-avoiding random walk dynamics in order to quantify in objective and accurate manner, along a range of spatial scales, the accessibility of places in towns and cities. The transition probabilities are estimated for several lengths of the walks and used to calculate the outward accessibility of each node. The potential of the methodology is illustrated with respect to the characterization and improvements of the accessibility of the town of Sao Carlos.
Syntax diagrams as a formalism for representation of syntactic relations of formal languages
Venue: arXiv cs.LO 2008
Year: 2008

The new approach to representation of syntax of formal languages-- a formalism of syntax diagrams is offered. Syntax diagrams look a convenient language for the description of syntactic relations in the languages having nonlinear representation of texts, for example, for representation of syntax lows of the language of structural chemical formulas. The formalism of neighbourhood grammar is used to describe the set of correct syntax constructs. The neighbourhood the grammar consists of a set of families of "neighbourhoods"-- the diagrams defined for each symbol of the language's alphabet. The syntax diagram is correct if each symbol is included into this diagram together with some neighbourhood. In other words, correct diagrams are needed to be covered by elements of the neighbourhood grammar. Thus, the grammar of formal language can be represented as system of the covers defined for each correct syntax diagram.
Sensing Danger: Innate Immunology for Intrusion Detection
Venue: arXiv cs.NE 2008
Year: 2008

The immune system provides an ideal metaphor for anomaly detection in general and computer security in particular. Based on this idea, artificial immune systems have been used for a number of years for intrusion detection, unfortunately so far with little success. However, these previous systems were largely based on immunological theory from the 1970s and 1980s and over the last decade our understanding of immunological processes has vastly improved. In this paper we present two new immune inspired algorithms based on the latest immunological discoveries, such as the behaviour of Dendritic Cells. The resultant algorithms are applied to real world intrusion problems and show encouraging results. Overall, we believe there is a bright future for these next generation artificial immune algorithms.
Families of LDPC Codes Derived from Nonprimitive BCH Codes and Cyclotomic Cosets
Venue: arXiv cs.IT 2008
Year: 2008

Low-density parity check (LDPC) codes are an important class of codes with many applications. Two algebraic methods for constructing regular LDPC codes are derived -- one based on nonprimitive narrow-sense BCH codes and the other directly based on cyclotomic cosets. The constructed codes have high rates and are free of cycles of length four; consequently, they can be decoded using standard iterative decoding algorithms. The exact dimension and bounds for the minimum distance and stopping distance are derived. These constructed codes can be used to derive quantum error-correcting codes.
An algorithmic complexity interpretation of Lin's third law of information theory
Venue: arXiv cs.CC 2008
Year: 2008

Instead of static entropy we assert that the Kolmogorov complexity of a static structure such as a solid is the proper measure of disorder (or chaoticity). A static structure in a surrounding perfectly-random universe acts as an interfering entity which introduces local disruption in randomness. This is modeled by a selection rule $R$ which selects a subsequence of the random input sequence that hits the structure. Through the inequality that relates stochasticity and chaoticity of random binary sequences we maintain that Lin's notion of stability corresponds to the stability of the frequency of 1s in the selected subsequence. This explains why more complex static structures are less stable. Lin's third law is represented as the inevitable change that static structure undergo towards conforming to the universe's perfect randomness.
Distributed Opportunistic Scheduling For Ad-Hoc Communications Under Noisy Channel Estimation
Venue: arXiv cs.IT 2008
Year: 2008

Distributed opportunistic scheduling is studied for wireless ad-hoc networks, where many links contend for one channel using random access. In such networks, distributed opportunistic scheduling (DOS) involves a process of joint channel probing and distributed scheduling. It has been shown that under perfect channel estimation, the optimal DOS for maximizing the network throughput is a pure threshold policy. In this paper, this formalism is generalized to explore DOS under noisy channel estimation, where the transmission rate needs to be backed off from the estimated rate to reduce the outage. It is shown that the optimal scheduling policy remains to be threshold-based, and that the rate threshold turns out to be a function of the variance of the estimation error and be a functional of the backoff rate function. Since the optimal backoff rate is intractable, a suboptimal linear backoff scheme that backs off the estimated signal-to-noise ratio (SNR) and hence the rate is proposed. The corresponding optimal backoff ratio and rate threshold can be obtained via an iterative algorithm. Finally, simulation results are provided to illustrate the tradeoff caused by increasing training time to improve channel estimation at the cost of probing efficiency.
Low Complexity Sphere Decoding for Spatial Multiplexing MIMO
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we present a novel method for decoding multiple input - multiple output (MIMO) transmission, which combines sphere decoding (SD) and zero forcing (ZF) techniques to provide near optimal low complexity and high performance constant time modified sphere decoding algorithm. This algorithm was designed especially for large number of transmit antennas, and allows efficient implementation in hardware. We do this by limiting the number of overall SD iterations. Moreover, we make sure that matrices with high condition number are more likely to undergo SD.
A Study On Distributed Model Predictive Consensus
Venue: arXiv cs.MA 2008
Year: 2008

We investigate convergence properties of a proposed distributed model predictive control (DMPC) scheme, where agents negotiate to compute an optimal consensus point using an incremental subgradient method based on primal decomposition as described in Johansson et al. [2006, 2007]. The objective of the distributed control strategy is to agree upon and achieve an optimal common output value for a group of agents in the presence of constraints on the agent dynamics using local predictive controllers. Stability analysis using a receding horizon implementation of the distributed optimal consensus scheme is performed. Conditions are given under which convergence can be obtained even if the negotiations do not reach full consensus.
Qtier-Rapor: Managing Spreadsheet Systems & Improving Corporate Performance, Compliance and Governance
Venue: arXiv cs.OH 2008
Year: 2008

Much of what EuSpRIG discusses is concerned with the integrity of individual spreadsheets. In businesses, interlocking spreadsheets are regularly used to fill functional gaps in core administrative systems. The growth and deployment of such integrated spreadsheet SYSTEMS raises the scale of issues to a whole new level. The correct management of spreadsheet systems is necessary to ensure that the business achieves its goals of improved performance and good corporate governance, within the constraints of legislative compliance - poor management will deliver the opposite. This paper is an anatomy of the real-life issues of the commercial use of spreadsheets in business, and demonstrates how Qtier-Rapor has been used to instil best practice in the use of integrated commercial spreadsheet systems.
Another approach to decide on real root existence for univariate Polynomials, and a multivariate extension for 3-SAT
Venue: arXiv cs.NA 2008
Year: 2008

We present six Theorems on the univariate real Polynomial, using which we develop a new algorithm for deciding the existence of atleast one real root for univariate integer Polynomials. Our algorithm outputs that no positive real root exists, if and only if, the given Polynomial is a factor of a real Polynomial with positive coefficients. Next, we define a transformation that transforms any instance of 3-SAT into a multivariate real Polynomial with positive coefficients, if and only if, the instance is not satisfiable.
Spreadsheet Validation and Analysis through Content Visualization
Venue: arXiv cs.HC 2008
Year: 2008

Visualizing spreadsheet content provides analytic insight and visual validation of large amounts of spreadsheet data. Oculus Excel Visualizer is a point and click data visualization experiment which directly visualizes Excel data and re-uses the layout and formatting already present in the spreadsheet.
An Investigation of the Incidence and Effect of Spreadsheet Errors Caused by the Hard Coding of Input Data Values into Formulas
Venue: arXiv cs.HC 2008
Year: 2008

The hard coding of input data or constants into spreadsheet formulas is widely recognised as poor spreadsheet model design. However, the importance of avoiding such practice appears to be underestimated perhaps in light of the lack of quantitative error at the time of occurrence and the recognition that this design defect may never result in a bottom-line error. The paper examines both the academic and practitioner view of such hard coding design flaws. The practitioner or industry viewpoint is gained indirectly through a review of commercial spreadsheet auditing software. The development of an automated (electronic) means for detecting such hard coding is described together with a discussion of some results obtained through analysis of a number of student and practitioner spreadsheet models.
Random hypergraphs and algorithmics
Venue: arXiv cs.DM 2008
Year: 2008

Hypergraphs are structures that can be decomposed or described; in other words they are recursively countable. Here, we get exact and asymptotic enumeration results on hypergraphs by means of exponential generating functions. The number of hypergraph component is bounded, as a generalisation of Wright inequalities for graphs: the proof is a combinatorial understanding of the structure by inclusion exclusion. Asymptotic results are obtained, thanks to generating functions proofs are at the end very easy to read, through complex analysis by saddle point method. By this way, we characterized: - the components with a given number of vertices and of hyperedges by the expected size of a random hypermatching in these structures. - the random hypergraphs (evolving hyperedge by hyperedge) according to the expected number of hyperedges when the first cycle appears in the evolving structure. This work is an open road to further works on random hypergraphs such as threshold phenomenon, tools used here seem to be sufficient at first sight.
Blind Fingerprinting
Venue: arXiv cs.IT 2008
Year: 2008

We study blind fingerprinting, where the host sequence into which fingerprints are embedded is partially or completely unknown to the decoder. This problem relates to a multiuser version of the Gel'fand-Pinsker problem. The number of colluders and the collusion channel are unknown, and the colluders and the fingerprint embedder are subject to distortion constraints. We propose a conditionally constant-composition random binning scheme and a universal decoding rule and derive the corresponding false-positive and false-negative error exponents. The encoder is a stacked binning scheme and makes use of an auxiliary random sequence. The decoder is a {\em maximum doubly-penalized mutual information decoder}, where the significance of each candidate coalition is assessed relative to a threshold that trades off false-positive and false-negative error exponents. The penalty is proportional to coalition size and is a function of the conditional type of host sequence. Positive exponents are obtained at all rates below a certain value, which is therefore a lower bound on public fingerprinting capacity. We conjecture that this value is the public fingerprinting capacity. A simpler threshold decoder is also given, which has similar universality properties but also lower achievable rates. An upper bound on public fingerprinting capacity is also derived.
Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues
Venue: arXiv cs.CG 2008
Year: 2008

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered, as each new glue type requires significant biochemical research and experiments. Under this assumption, traditional tile self-assembly cannot even manufacture an n*n square; in contrast, we show how staged assembly enables manufacture of arbitrary orthogonal shapes in a variety of precise formulations of the model.
Optimizing polynomials for floating-point implementation
Venue: arXiv cs.NA 2008
Year: 2008

The floating-point implementation of a function on an interval often reduces to polynomial approximation, the polynomial being typically provided by Remez algorithm. However, the floating-point evaluation of a Remez polynomial sometimes leads to catastrophic cancellations. This happens when some of the polynomial coefficients are very small in magnitude with respects to others. In this case, it is better to force these coefficients to zero, which also reduces the operation count. This technique, classically used for odd or even functions, may be generalized to a much larger class of functions. An algorithm is presented that forces to zero the smaller coefficients of the initial polynomial thanks to a modified Remez algorithm targeting an incomplete monomial basis. One advantage of this technique is that it is purely numerical, the function being used as a numerical black box. This algorithm is implemented within a larger polynomial implementation tool that is demonstrated on a range of examples, resulting in polynomials with less coefficients than those obtained the usual way.
Une approche modulaire probabiliste pour le routage à Qualité de Service intégrée
Venue: arXiv cs.NI 2008
Year: 2008

Due to emerging real-time and multimedia applications, efficient routing of information packets in dynamically changing communication network requires that as the load levels, traffic patterns and topology of the network change, the routing policy also adapts. We focused in this paper on QoS based routing by developing a neuro-dynamic programming to construct dynamic state dependent routing policies. We propose an approach based on adaptive algorithm for packet routing using reinforcement learning which optimizes two criteria: cumulative cost path and end-to-end delay. Numerical results obtained with OPNET simulator for different packet interarrival times statistical distributions with different levels of traffic's load show that the proposed approach gives better results compared to standard optimal path routing algorithms.
Spanning directed trees with many leaves
Venue: arXiv cs.DS 2008
Year: 2008

The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that - every strongly connected $n$-vertex digraph $D$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; - if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph UG($D$) is $O(k\log k)$. Moreover, if the digraph is acyclic, the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(k\log^2 k)}\cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. On acyclic digraphs the running time of our algorithm is $2^{O(k\log k)}\cdot n^{O(1)}$.
Incremental Topological Ordering and Strong Component Maintenance
Venue: arXiv cs.DS 2008
Year: 2008

We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes O(m^{1/2}) amortized time per arc, where m is the total number of arcs. For sparse graphs, this bound improves the best previous bound by a logarithmic factor and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the bidirectional search method of previous algorithms does not require an ordered search, but can be more general. This allows us to avoid the use of heaps (priority queues) entirely. Instead, the deterministic version of our algorithm uses (approximate) median-finding. The randomized version of our algorithm avoids this complication, making it very simple. We extend our topological ordering algorithm to give the first detailed algorithm for maintaining the strong components of a directed graph, and a topological order of these components, as arcs are added. This extension also has an amortized time bound of O(m^{1/2}) per arc.
Website Optimization through Mining User Navigational Pattern
Venue: arXiv cs.IR 2008
Year: 2008

With the World Wide Web's ubiquity increase and the rapid development of various online businesses, the complexity of web sites grow. The analysis of web user's navigational pattern within a web site can provide useful information for server performance enhancements, restructuring a website and direct marketing in e-commerce etc. In this paper, an algorithm is proposed for mining such navigation patterns. The key insight is that users access information of interest and follow a certain path while navigating a web site. If they don't find it, they would backtrack and choose among the alternate paths till they reach the destination. The point they backtrack is the Intermediate Reference Location. Identifying such Intermediate locations and destinations out of the pattern will be the main endeavor in the rest of this report.
Vandermonde Frequency Division Multiplexing for Cognitive Radio
Venue: arXiv cs.IT 2008
Year: 2008

We consider a cognitive radio scenario where a primary and a secondary user wish to communicate with their corresponding receivers simultaneously over frequency selective channels. Under realistic assumptions that the secondary transmitter has no side information about the primary's message and each transmitter knows only its local channels, we propose a Vandermonde precoder that cancels the interference from the secondary user by exploiting the redundancy of a cyclic prefix. Our numerical examples show that VFDM, with an appropriate design of the input covariance, enables the secondary user to achieve a considerable rate while generating zero interference to the primary user.
Selective association rule generation
Venue: arXiv cs.DB 2008
Year: 2008

Mining association rules is a popular and well researched method for discovering interesting relations between variables in large databases. A practical problem is that at medium to low support values often a large number of frequent itemsets and an even larger number of association rules are found in a database. A widely used approach is to gradually increase minimum support and minimum confidence or to filter the found rules using increasingly strict constraints on additional measures of interestingness until the set of rules found is reduced to a manageable size. In this paper we describe a different approach which is based on the idea to first define a set of ``interesting'' itemsets (e.g., by a mixture of mining and expert knowledge) and then, in a second step to selectively generate rules for only these itemsets. The main advantage of this approach over increasing thresholds or filtering rules is that the number of rules found is significantly reduced while at the same time it is not necessary to increase the support and confidence thresholds which might lead to missing important information in the database.
Asymptotic Concentration Behaviors of Linear Combinations of Weight Distributions on Random Linear Code Ensemble
Venue: arXiv cs.IT 2008
Year: 2008

Asymptotic concentration behaviors of linear combinations of weight distributions on the random linear code ensemble are presented. Many important properties of a binary linear code can be expressed as the form of a linear combination of weight distributions such as number of codewords, undetected error probability and upper bound on the maximum likelihood error probability. The key in this analysis is the covariance formula of weight distributions of the random linear code ensemble, which reveals the second-order statistics of a linear function of the weight distributions. Based on the covariance formula, several expressions of the asymptotic concentration rate, which indicate the speed of convergence to the average, are derived.
On the need for a global academic internet platform
Venue: arXiv cs.CY 2008
Year: 2008

The article collects arguments for the necessity of a global academic internet platform, which is organized as a kind of ``global scientific parliament''. With such a constitution educational and research institutions will have direct means for communicating scientific results, as well as a platform for representing academia and scientific life in the public.