OpenRaiser/Intern-Atlas huggingface dataset:
Algorithm Selection as a Bandit Problem with Unbounded Losses
Venue: arXiv cs.AI 2008
Year: 2008

Algorithm selection is typically based on models of algorithm performance, learned during a separate offline training sequence, which can be prohibitively expensive. In recent work, we adopted an online approach, in which a performance model is iteratively updated and used to guide selection on a sequence of problem instances. The resulting exploration-exploitation trade-off was represented as a bandit problem with expert advice, using an existing solver for this game, but this required the setting of an arbitrary bound on algorithm runtimes, thus invalidating the optimal regret of the solver. In this paper, we propose a simpler framework for representing algorithm selection as a bandit problem, with partial information, and an unknown bound on losses. We adapt an existing solver to this game, proving a bound on its expected regret, which holds also for the resulting algorithm selection technique. We present preliminary experiments with a set of SAT solvers on a mixed SAT-UNSAT benchmark.
Archer: A Community Distributed Computing Infrastructure for Computer Architecture Research and Education
Venue: arXiv cs.AR 2008
Year: 2008

This paper introduces Archer, a community-based computing resource for computer architecture research and education. The Archer infrastructure integrates virtualization and batch scheduling middleware to deliver high-throughput computing resources aggregated from resources distributed across wide-area networks and owned by different participating entities in a seamless manner. The paper discusses the motivations leading to the design of Archer, describes its core middleware components, and presents an analysis of the functionality and performance of a prototype wide-area deployment running a representative computer architecture simulation workload.
Intrusion Detection Using Cost-Sensitive Classification
Venue: arXiv cs.CR 2008
Year: 2008

Intrusion Detection is an invaluable part of computer networks defense. An important consideration is the fact that raising false alarms carries a significantly lower cost than not detecting at- tacks. For this reason, we examine how cost-sensitive classification methods can be used in Intrusion Detection systems. The performance of the approach is evaluated under different experimental conditions, cost matrices and different classification models, in terms of expected cost, as well as detection and false alarm rates. We find that even under unfavourable conditions, cost-sensitive classification can improve performance significantly, if only slightly.
Towards an Effective Intrusion Response Engine Combined with Intrusion Detection in Ad Hoc Networks
Venue: arXiv cs.CR 2008
Year: 2008

In this paper, we present an effective intrusion response engine combined with intrusion detection in ad hoc networks. The intrusion response engine is composed of a secure communication module, a local and a global response module. Its function is based on an innovative tree-based key agreement protocol while the intrusion detection engine is based on a class of neural networks called eSOM. The proposed intrusion response model and the tree-based protocol, it is based on, are analyzed concerning key secrecy while the intrusion detection engine is evaluated for MANET under different traffic conditions and mobility patterns. The results show a high detection rate for packet dropping attacks.
Hardware/Software Co-Design for Spike Based Recognition
Venue: arXiv cs.NE 2008
Year: 2008

The practical applications based on recurrent spiking neurons are limited due to their non-trivial learning algorithms. The temporal nature of spiking neurons is more favorable for hardware implementation where signals can be represented in binary form and communication can be done through the use of spikes. This work investigates the potential of recurrent spiking neurons implementations on reconfigurable platforms and their applicability in temporal based applications. A theoretical framework of reservoir computing is investigated for hardware/software implementation. In this framework, only readout neurons are trained which overcomes the burden of training at the network level. These recurrent neural networks are termed as microcircuits which are viewed as basic computational units in cortical computation. This paper investigates the potential of recurrent neural reservoirs and presents a novel hardware/software strategy for their implementation on FPGAs. The design is implemented and the functionality is tested in the context of speech recognition application.
Revisiting the upper bounding process in a safe Branch and Bound algorithm
Venue: arXiv cs.NA 2008
Year: 2008

Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. First experiments on the Coconuts benchmarks demonstrate that this approach is very effective.
Construction of Error-Correcting Codes for Random Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

In this work we present error-correcting codes for random network coding based on rank- metric codes, Ferrers diagrams, and puncturing. For most parameters, the constructed codes are larger than all previously known codes.
Opportunistic Collaborative Beamforming with One-Bit Feedback
Venue: arXiv cs.IT 2008
Year: 2008

An energy-efficient opportunistic collaborative beamformer with one-bit feedback is proposed for ad hoc sensor networks over Rayleigh fading channels. In contrast to conventional collaborative beamforming schemes in which each source node uses channel state information to correct its local carrier offset and channel phase, the proposed beamforming scheme opportunistically selects a subset of source nodes whose received signals combine in a quasi-coherent manner at the intended receiver. No local phase-precompensation is performed by the nodes in the opportunistic collaborative beamformer. As a result, each node requires only one-bit of feedback from the destination in order to determine if it should or shouldn't participate in the collaborative beamformer. Theoretical analysis shows that the received signal power obtained with the proposed beamforming scheme scales linearly with the number of available source nodes. Since the the optimal node selection rule requires an exhaustive search over all possible subsets of source nodes, two low-complexity selection algorithms are developed. Simulation results confirm the effectiveness of opportunistic collaborative beamforming with the low-complexity selection algorithms.
Position Estimation via Ultra-Wideband Signals
Venue: arXiv cs.IT 2008
Year: 2008

The high time resolution of ultra-wideband (UWB) signals facilitates very precise position estimation in many scenarios, which makes a variety applications possible. This paper reviews the problem of position estimation in UWB systems, beginning with an overview of the basic structure of UWB signals and their positioning applications. This overview is followed by a discussion of various position estimation techniques, with an emphasis on time-based approaches, which are particularly suitable for UWB positioning systems. Practical issues arising in UWB signal design and hardware implementation are also discussed.
On the Performance of Selection Relaying
Venue: arXiv cs.IT 2008
Year: 2008

Interest in selection relaying is growing. The recent developments in this area have largely focused on information theoretic analyses such as outage performance. Some of these analyses are accurate only at high SNR regimes. In this paper error rate analyses that are sufficiently accurate over a wide range of SNR regimes are provided. The motivations for this work are that practical systems operate at far lower SNR values than those supported by the high SNR analysis. To enable designers to make informed decisions regarding network design and deployment, it is imperative that system performance is evaluated with a reasonable degree of accuracy over practical SNR regimes. Simulations have been used to corroborate the analytical results, as close agreement between the two is observed.
DescribeX: A Framework for Exploring and Querying XML Web Collections
Venue: arXiv cs.DB 2008
Year: 2008

This thesis introduces DescribeX, a powerful framework that is capable of describing arbitrarily complex XML summaries of web collections, providing support for more efficient evaluation of XPath workloads. DescribeX permits the declarative description of document structure using all axes and language constructs in XPath, and generalizes many of the XML indexing and summarization approaches in the literature. DescribeX supports the construction of heterogeneous summaries where different document elements sharing a common structure can be declaratively defined and refined by means of path regular expressions on axes, or axis path regular expression (AxPREs). DescribeX can significantly help in the understanding of both the structure of complex, heterogeneous XML collections and the behaviour of XPath queries evaluated on them. Experimental results demonstrate the scalability of DescribeX summary refinements and stabilizations (the key enablers for tailoring summaries) with multi-gigabyte web collections. A comparative study suggests that using a DescribeX summary created from a given workload can produce query evaluation times orders of magnitude better than using existing summaries. DescribeX's light-weight approach of combining summaries with a file-at-a-time XPath processor can be a very competitive alternative, in terms of performance, to conventional fully-fledged XML query engines that provide DB-like functionality such as security, transaction processing, and native storage.
Establishing and Measuring Standard Spreadsheet Practices for End-Users
Venue: arXiv cs.HC 2008
Year: 2008

This paper offers a brief review of cognitive verbs typically used in the literature to describe standard spreadsheet practices. The verbs identified are then categorised in terms of Bloom's Taxonomy of Hierarchical Levels, and then rated and arranged to distinguish some of their qualities and characteristics. Some measurement items are then evaluated to see how well computerised test question items validate or reinforce training or certification. The paper considers how establishing standard practices in spreadsheet training and certification can help reduce some of the risks associated with spreadsheets, and help promote productivity.
Finding paths of length k in O*(2^k) time
Venue: arXiv cs.DS 2008
Year: 2008

We give a randomized algorithm that determines if a given graph has a simple path of length at least k in O(2^k poly(n,k)) time.
Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
Venue: arXiv cs.IT 2008
Year: 2008

Consider communication over a binary-input memoryless output-symmetric channel with low density parity check (LDPC) codes and maximum a posteriori (MAP) decoding. The replica method of spin glass theory allows to conjecture an analytic formula for the average input-output conditional entropy per bit in the infinite block length limit. Montanari proved a lower bound for this entropy, in the case of LDPC ensembles with convex check degree polynomial, which matches the replica formula. Here we extend this lower bound to any irregular LDPC ensemble. The new feature of our work is an analysis of the second derivative of the conditional input-output entropy with respect to noise. A close relation arises between this second derivative and correlation or mutual information of codebits. This allows us to extend the realm of the interpolation method, in particular we show how channel symmetry allows to control the fluctuations of the overlap parameters.
Accuracy in Spreadsheet Modelling Systems
Venue: arXiv cs.HC 2008
Year: 2008

Accuracy in spreadsheet modelling systems can be reduced due to difficulties with the inputs, the model itself, or the spreadsheet implementation of the model. When the "true" outputs from the system are unknowable, accuracy is evaluated subjectively. Less than perfect accuracy can be acceptable depending on the purpose of the model, problems with inputs, or resource constraints. Users build modelling systems iteratively, and choose to allocate limited resources to the inputs, the model, the spreadsheet implementation, and to employing the system for business analysis. When making these choices, users can suffer from expectation bias and diagnosis bias. Existing research results tend to focus on errors in the spreadsheet implementation. Because industry has tolerance for system inaccuracy, errors in spreadsheet implementations may not be a serious concern. Spreadsheet productivity may be of more interest.
Construction of Large Constant Dimension Codes With a Prescribed Minimum Distance
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we construct constant dimension space codes with prescribed minimum distance. There is an increased interest in space codes since a paper by Koetter and Kschischang were they gave an application in network coding. There is also a connection to the theory of designs over finite fields. We will modify a method of Braun, Kerber and Laue which they used for the construction of designs over finite fields to do the construction of space codes. Using this approach we found many new constant dimension spaces codes with a larger number of codewords than previously known codes. We will finally give a table of the best found constant dimension space codes.
Energy-efficient Scheduling of Delay Constrained Traffic over Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

A delay-constrained scheduling problem for point-to-point communication is considered: a packet of $B$ bits must be transmitted by a hard deadline of $T$ slots over a time-varying channel. The transmitter/scheduler must determine how many bits to transmit, or equivalently how much energy to transmit with, during each time slot based on the current channel quality and the number of unserved bits, with the objective of minimizing expected total energy. In order to focus on the fundamental scheduling problem, it is assumed that no other packets are scheduled during this time period and no outage is allowed. Assuming transmission at capacity of the underlying Gaussian noise channel, a closed-form expression for the optimal scheduling policy is obtained for the case T=2 via dynamic programming; for $T>2$, the optimal policy can only be numerically determined. Thus, the focus of the work is on derivation of simple, near-optimal policies based on intuition from the T=2 solution and the structure of the general problem. The proposed bit-allocation policies consist of a linear combination of a delay-associated term and an opportunistic (channel-aware) term. In addition, a variation of the problem in which the entire packet must be transmitted in a single slot is studied, and a channel-threshold policy is shown to be optimal.
A new probabilistic transformation of belief mass assignment
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, we propose in Dezert-Smarandache Theory (DSmT) framework, a new probabilistic transformation, called DSmP, in order to build a subjective probability measure from any basic belief assignment defined on any model of the frame of discernment. Several examples are given to show how the DSmP transformation works and we compare it to main existing transformations proposed in the literature so far. We show the advantages of DSmP over classical transformations in term of Probabilistic Information Content (PIC). The direct extension of this transformation for dealing with qualitative belief assignments is also presented.
Approximating Document Frequency with Term Count Values
Venue: arXiv cs.IR 2008
Year: 2008

For bounded datasets such as the TREC Web Track (WT10g) the computation of term frequency (TF) and inverse document frequency (IDF) is not difficult. However, when the corpus is the entire web, direct IDF calculation is impossible and values must instead be estimated. Most available datasets provide values for term count (TC) meaning the number of times a certain term occurs in the entire corpus. Intuitively this value is different from document frequency (DF), the number of documents (e.g., web pages) a certain term occurs in. We conduct a comparison study between TC and DF values within the Web as Corpus (WaC). We found a very strong correlation with Spearman's rho >0.8 (p<0.005) which makes us confident in claiming that for such recently created corpora the TC and DF values can be used interchangeably to compute IDF values. These results are useful for the generation of accurate lexical signatures based on the TF-IDF scheme.
Unfolding in CHR
Venue: arXiv cs.PL 2008
Year: 2008

Program transformation is an appealing technique which allows to improve run-time efficiency, space-consumption and more generally to optimize a given program. Essentially it consists of a sequence of syntactic program manipulations which preserves some kind of semantic equivalence. One of the basic operations which is used by most program transformation systems is unfolding which consists in the replacement of a procedure call by its definition. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages and, to the best of our knowledge, no other has considered unfolding of CHR programs. This paper defines a correct unfolding system for CHR programs. We define an unfolding rule, show its correctness and discuss some conditions which can be used to delete an unfolded rule while preserving the program meaning. We prove that confluence and termination properties are preserved by the above transformations.
Compound Multiple Access Channels with Partial Cooperation
Venue: arXiv cs.IT 2008
Year: 2008

A two-user discrete memoryless compound multiple access channel with a common message and conferencing decoders is considered. The capacity region is characterized in the special cases of physically degraded channels and unidirectional cooperation, and achievable rate regions are provided for the general case. The results are then extended to the corresponding Gaussian model. In the Gaussian setup, the provided achievable rates are shown to lie within some constant number of bits from the boundary of the capacity region in several special cases. An alternative model, in which the encoders are connected by conferencing links rather than having a common message, is studied as well, and the capacity region for this model is also determined for the cases of physically degraded channels and unidirectional cooperation. Numerical results are also provided to obtain insights about the potential gains of conferencing at the decoders and encoders.
Energy-delay bounds analysis in wireless multi-hop networks with unreliable radio links
Venue: arXiv cs.NI 2008
Year: 2008

Energy efficiency and transmission delay are very important parameters for wireless multi-hop networks. Previous works that study energy efficiency and delay are based on the assumption of reliable links. However, the unreliability of the channel is inevitable in wireless multi-hop networks. This paper investigates the trade-off between the energy consumption and the end-to-end delay of multi-hop communications in a wireless network using an unreliable link model. It provides a closed form expression of the lower bound on the energy-delay trade-off for different channel models (AWGN, Raleigh flat fading and Nakagami block-fading) in a linear network. These analytical results are also verified in 2-dimensional Poisson networks using simulations. The main contribution of this work is the use of a probabilistic link model to define the energy efficiency of the system and capture the energy-delay trade-offs. Hence, it provides a more realistic lower bound on both the energy efficiency and the energy-delay trade-off since it does not restrict the study to the set of perfect links as proposed in earlier works.
Algebraic Soft-Decision Decoding of Hermitian Codes
Venue: arXiv cs.IT 2008
Year: 2008

An algebraic soft-decision decoder for Hermitian codes is presented. We apply Koetter and Vardy's soft-decision decoding framework, now well established for Reed-Solomon codes, to Hermitian codes. First we provide an algebraic foundation for soft-decision decoding. Then we present an interpolation algorithm finding the Q-polynomial that plays a key role in the decoding. With some simulation results, we compare performances of the algebraic soft-decision decoders for Hermitian codes and Reed-Solomon codes, favorable to the former.
Finding Dense Subgraphs in G(n,1/2)
Venue: arXiv cs.DS 2008
Year: 2008

Finding the largest clique is a notoriously hard problem, even on random graphs. It is known that the clique number of a random graph G(n,1/2) is almost surely either k or k+1, where k = 2log n - 2log(log n) - 1. However, a simple greedy algorithm finds a clique of size only (1+o(1))log n, with high probability, and finding larger cliques -- that of size even (1+ epsilon)log n -- in randomized polynomial time has been a long-standing open problem. In this paper, we study the following generalization: given a random graph G(n,1/2), find the largest subgraph with edge density at least (1-delta). We show that a simple modification of the greedy algorithm finds a subset of 2log n vertices whose induced subgraph has edge density at least 0.951, with high probability. To complement this, we show that almost surely there is no subset of 2.784log n vertices whose induced subgraph has edge density 0.951 or more.
The Degree Distribution of Random k-Trees
Venue: arXiv cs.DM 2008
Year: 2008

A power law degree distribution is established for a graph evolution model based on the graph class of k-trees. This k-tree-based graph process can be viewed as an idealized model that captures some characteristics of the preferential attachment and copying mechanisms that existing evolving graph processes fail to model due to technical obstacles. The result also serves as a further cautionary note reinforcing the point of view that a power law degree distribution should not be regarded as the only important characteristic of a complex network, as has been previously argued.
DMT of Multi-hop Cooperative Networks - Part I: Basic Results
Venue: arXiv cs.IT 2008
Year: 2008

In this two-part paper, the DMT of cooperative multi-hop networks is examined. The focus is on single-source single-sink (ss-ss) multi-hop relay networks having slow-fading links and relays that potentially possess multiple antennas. The present paper examines the two end-points of the DMT of full-duplex networks. In particular, the maximum achievable diversity of arbitrary multi-terminal wireless networks is shown to be equal to the min-cut. The maximum multiplexing gain of arbitrary full-duplex ss-ss networks is shown to be equal to the min-cut rank, using a new connection to a deterministic network. We also prove some basic results including a proof that the colored noise encountered in AF protocols for cooperative networks can be treated as white noise for DMT computations. The DMT of a parallel channel with independent MIMO links is also computed here. As an application of these basic results, we prove that a linear tradeoff between maximum diversity and maximum multiplexing gain is achievable for full-duplex networks with single antenna nodes. All protocols in this paper are explicit and rely only upon amplify-and-forward (AF) relaying. Half duplex networks are studied, and explicit codes for all protocols proposed in both parts, are provided in the companion paper.