OpenRaiser/Intern-Atlas huggingface dataset:
Bounds on the Threshold of Linear Programming Decoding
Venue: arXiv cs.IT 2006
Year: 2006

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.
Effect of CSMA/CD on Self-Similarity of Network Traffic
Venue: arXiv cs.NI 2006
Year: 2006

It is now well known that Internet traffic exhibits self-similarity, which cannot be described by traditional Markovian models such as the Poisson process. The causes of self-similarity of network traffic must be identified because understanding the nature of network traffic is critical in order to properly design and implement computer networks and network services like the World Wide Web. While some researchers have argued self similarity is generated by the typical applications or caused by Transport layer Protocols, it is also possible that the CSMA/CD protocol may cause or at least contribute to this phenomenon. In this paper, we use NS simulator to study the effect of CSMA/CD Exponential Backoff retransmission algorithm on Traffic Self similarity.
On comparing sums of square roots of small integers
Venue: arXiv cs.CG 2006
Year: 2006

Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the minimum positive value of $$ |\sqrt{a_1} + ... + \sqrt{a_k} - \sqrt{b_1} - >... -\sqrt{b_k} | $$ where $ a_1, a_2, ..., a_k, b_1, b_2, ..., b_k $ are positive integers no larger than $n$. It is an important problem in computational geometry to determine a good upper bound of $-\log r(n,k)$. In this paper we prove an upper bound of $ 2^{O(n/\log n)} \log n$, which is better than the best known result $O(2^{2k} \log n)$ whenever $ n \leq ck\log k$ for some constant $c$. In particular, our result implies a {\em subexponential} algorithm to compare two sums of square roots of integers of size $o(k\log k)$.
Linear Secret Sharing from Algebraic-Geometric Codes
Venue: arXiv cs.CR 2006
Year: 2006

It is well-known that the linear secret-sharing scheme (LSSS) can be constructed from linear error-correcting codes (Brickell [1], R.J. McEliece and D.V.Sarwate [2],Cramer, el.,[3]). The theory of linear codes from algebraic-geometric curves (algebraic-geometric (AG) codes or geometric Goppa code) has been well-developed since the work of V.Goppa and Tsfasman, Vladut, and Zink(see [17], [18] and [19]). In this paper the linear secret-sharing scheme from algebraic-geometric codes, which are non-threshold scheme for curves of genus greater than 0, are presented . We analysis the minimal access structure, $d_{min}$ and $d_{cheat}$([8]), (strongly) multiplicativity and the applications in verifiable secret-sharing (VSS) scheme and secure multi-party computation (MPC) of this construction([3] and [10-11]). Our construction also offers many examples of the self-dually $GF(q)$-representable matroids and many examples of new ideal linear secret-sharing schemes addressing to the problem of the characterization of the access structures for ideal secret-sharing schemes([3] and [9]). The access structures of the linear secret-sharing schemes from the codes on elliptic curves are given explicitly. From the work in this paper we can see that the algebraic-geometric structure of the underlying algebraic curves is an important resource for secret-sharing, matroid theory, verifiable secret-sharing and secure multi-party computation.
Near orders and codes
Venue: arXiv cs.IT 2006
Year: 2006

Hoholdt, van Lint and Pellikaan used order functions to construct codes by means of Linear Algebra and Semigroup Theory only. However, Geometric Goppa codes that can be represented by this method are mainly those based on just one point. In this paper we introduce the concept of near order function with the aim of generalize this approach in such a way that a of wider family of Geometric Goppa codes can be studied on a more elementary setting.
Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
Venue: arXiv cs.LO 2006
Year: 2006

There has been a great of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the validity problem for all logics between K, T, and S4 is {\sl PSPACE}-complete, while for S5 it is {\sl NP}-complete. We show that, in a precise sense, it is \emph{negative introspection}, the axiom $\neg K p \rimp K \neg K p$, that causes the gap. In a precise sense, if we require this axiom, then the satisfiability problem is {\sl NP}-complete; without it, it is {\sl PSPACE}-complete.
Language Support for Optional Functionality
Venue: arXiv cs.PL 2006
Year: 2006

We recommend a programming construct - availability check - for programs that need to automatically adjust to presence or absence of segments of code. The idea is to check the existence of a valid definition before a function call is invoked. The syntax is that of a simple 'if' statement. The vision is to enable customization of application functionality through addition or removal of optional components, but without requiring complete re-building. Focus is on C-like compiled procedural languages and UNIX-based systems. Essentially, our approach attempts to combine the flexibility of dynamic libraries with the usability of utility (dependency) libraries. We outline the benefits over prevalent strategies mainly in terms of development complexity, crudely measured as lesser lines of code. We also allude to performance and flexibility facets. A Preliminary implementation and figures from early experimental evaluation are presented.
Metric State Space Reinforcement Learning for a Vision-Capable Mobile Robot
Venue: arXiv cs.RO 2006
Year: 2006

We address the problem of autonomously learning controllers for vision-capable mobile robots. We extend McCallum's (1995) Nearest-Sequence Memory algorithm to allow for general metrics over state-action trajectories. We demonstrate the feasibility of our approach by successfully running our algorithm on a real mobile robot. The algorithm is novel and unique in that it (a) explores the environment and learns directly on a mobile robot without using a hand-made computer model as an intermediate step, (b) does not require manual discretization of the sensor input space, (c) works in piecewise continuous perceptual spaces, and (d) copes with partial observability. Together this allows learning from much less experience compared to previous methods.
Representing Contextualized Information in the NSDL
Venue: arXiv cs.DL 2006
Year: 2006

The NSDL (National Science Digital Library) is funded by the National Science Foundation to advance science and match education. The inital product was a metadata-based digital library providing search and access to distributed resources. Our recent work recognizes the importance of context - relations, metadata, annotations - for the pedagogical value of a digital library. This new architecture uses Fedora, a tool for representing complex content, data, metadata, web-based services, and semantic relationships, as the basis of an information network overlay (INO). The INO provides an extensible knowl-edge base for an expanding suite of digital library services.
A d-Sequence based Recursive Random Number Generator
Venue: arXiv cs.CR 2006
Year: 2006

This paper proposes a new recursive technique using d-sequences to generate random numbers.
Metatheory of actions: beyond consistency
Venue: arXiv cs.AI 2006
Year: 2006

Consistency check has been the only criterion for theory evaluation in logic-based approaches to reasoning about actions. This work goes beyond that and contributes to the metatheory of actions by investigating what other properties a good domain description in reasoning about actions should have. We state some metatheoretical postulates concerning this sore spot. When all postulates are satisfied together we have a modular action theory. Besides being easier to understand and more elaboration tolerant in McCarthy's sense, modular theories have interesting properties. We point out the problems that arise when the postulates about modularity are violated and propose algorithmic checks that can help the designer of an action theory to overcome them.
On the Information Rate of MIMO Systems with Finite Rate Channel State Feedback Using Beamforming and Power On/Off Strategy
Venue: arXiv cs.IT 2006
Year: 2006

It is well known that Multiple-Input Multiple-Output (MIMO) systems have high spectral efficiency, especially when channel state information at the transmitter (CSIT) is available. When CSIT is obtained by feedback, it is practical to assume that the channel state feedback rate is finite and the CSIT is not perfect. For such a system, we consider beamforming and power on/off strategy for its simplicity and near optimality, where power on/off means that a beamforming vector (beam) is either turned on with a constant power or turned off. The main contribution of this paper is to accurately evaluate the information rate as a function of the channel state feedback rate. Name a beam turned on as an on-beam and the minimum number of the transmit and receive antennas as the dimension of a MIMO system. We prove that the ratio of the optimal number of on-beams and the system dimension converges to a constant for a given signal-to-noise ratio (SNR) when the numbers of transmit and receive antennas approach infinity simultaneously and when beamforming is perfect. Asymptotic formulas are derived to evaluate this ratio and the corresponding information rate per dimension. The asymptotic results can be accurately applied to finite dimensional systems and suggest a power on/off strategy with a constant number of on-beams. For this suboptimal strategy, we take a novel approach to introduce power efficiency factor, which is a function of the feedback rate, to quantify the effect of imperfect beamforming. By combining power efficiency factor and the asymptotic formulas for perfect beamforming case, the information rate of the power on/off strategy with a constant number of on-beams is accurately characterized.
Locally Adaptive Block Thresholding Method with Continuity Constraint
Venue: arXiv cs.CV 2006
Year: 2006

We present an algorithm that enables one to perform locally adaptive block thresholding, while maintaining image continuity. Images are divided into sub-images based some standard image attributes and thresholding technique is employed over the sub-images. The present algorithm makes use of the thresholds of neighboring sub-images to calculate a range of values. The image continuity is taken care by choosing the threshold of the sub-image under consideration to lie within the above range. After examining the average range values for various sub-image sizes of a variety of images, it was found that the range of acceptable threshold values is substantially high, justifying our assumption of exploiting the freedom of range for bringing out local details.
Time-Space Trade-Offs for Predecessor Search
Venue: arXiv cs.CC 2006
Year: 2006

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity. Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find predecessor(x) = max{y in Y | y <= x}, by representing Y on a RAM using space S. In external memory, it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of l = c*lg n, for c>1 (i.e. polynomial universes), and near linear space (such as S = n*poly(lg n)), the optimal search time is Theta(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n^{1+eps}, a running time of O(lg l / lglg l) was given by Beame and Fich [STOC'99].
First Steps in Relational Lattice
Venue: arXiv cs.DB 2006
Year: 2006

Relational lattice reduces the set of six classic relational algebra operators to two binary lattice operations: natural join and inner union. We give an introduction to this theory with emphasis on formal algebraic laws. New results include Spight distributivity criteria and its applications to query transformations.
VXA: A Virtual Architecture for Durable Compressed Archives
Venue: arXiv cs.DL 2006
Year: 2006

Data compression algorithms change frequently, and obsolete decoders do not always run on new hardware and operating systems, threatening the long-term usability of content archived using those algorithms. Re-encoding content into new formats is cumbersome, and highly undesirable when lossy compression is involved. Processor architectures, in contrast, have remained comparatively stable over recent decades. VXA, an archival storage system designed around this observation, archives executable decoders along with the encoded content it stores. VXA decoders run in a specialized virtual machine that implements an OS-independent execution environment based on the standard x86 architecture. The VXA virtual machine strictly limits access to host system services, making decoders safe to run even if an archive contains malicious code. VXA's adoption of a "native" processor architecture instead of type-safe language technology allows reuse of existing "hand-optimized" decoders in C and assembly language, and permits decoders access to performance-enhancing architecture features such as vector processing instructions. The performance cost of VXA's virtualization is typically less than 15% compared with the same decoders running natively. The storage cost of archived decoders, typically 30-130KB each, can be amortized across many archived files sharing the same compression method.
Packrat Parsing: Simple, Powerful, Lazy, Linear Time
Venue: arXiv cs.DS 2006
Year: 2006

Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.
Solving Sparse Integer Linear Systems
Venue: arXiv cs.SC 2006
Year: 2006

We propose a new algorithm to solve sparse linear systems of equations over the integers. This algorithm is based on a $p$-adic lifting technique combined with the use of block matrices with structured blocks. It achieves a sub-cubic complexity in terms of machine operations subject to a conjecture on the effectiveness of certain sparse projections. A LinBox-based implementation of this algorithm is demonstrated, and emphasizes the practical benefits of this new method over the previous state of the art.
On Pinsker's Type Inequalities and Csiszar's f-divergences. Part I: Second and Fourth-Order Inequalities
Venue: arXiv cs.IT 2006
Year: 2006

We study conditions on $f$ under which an $f$-divergence $D_f$ will satisfy $D_f \geq c_f V^2$ or $D_f \geq c_{2,f} V^2 + c_{4,f} V^4$, where $V$ denotes variational distance and the coefficients $c_f$, $c_{2,f}$ and $c_{4,f}$ are {\em best possible}. As a consequence, we obtain lower bounds in terms of $V$ for many well known distance and divergence measures. For instance, let $D_{(α)} (P,Q) = [α(α-1)]^{-1} [\int q^α p^{1-α} d μ-1]$ and ${\cal I}_α(P,Q) = (α-1)^{-1} \log [\int p^αq^{1-α} d μ]$ be respectively the {\em relative information of type} ($1-α$) and {\em Rényi's information gain of order} $α$. We show that $D_{(α)} \geq {1/2} V^2 + {1/72} (α+1)(2-α) V^4$ whenever $-1 \leq α\leq 2$, $α\not= 0,1$ and that ${\cal I}_α = \fracα{2} V^2 + {1/36} α(1 + 5 α- 5 α^2) V^4$ for $0 < α< 1$. Pinsker's inequality $D \geq {1/2} V^2$ and its extension $D \geq {1/2} V^2 + {1/36} V^4$ are special cases of each one of these.
Benchmark Problems for Constraint Solving
Venue: arXiv cs.PF 2006
Year: 2006

Constraint Programming is roughly a new software technology introduced by Jaffar and Lassez in 1987 for description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling. In the following we define three problems for constraint solving from the domain of electrical networks; based on them we define 43 related problems. For the defined set of problems we benchmarked five systems: ILOG OPL, AMPL, GAMS, Mathematica and UniCalc. As expected some of the systems performed very well for some problems while others performed very well on others.
Bargaining over the interference channel
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we analyze the interference channel as a conflict situation. This viewpoint implies that certain points in the rate region are unreasonable to one of the players. Therefore these points cannot be considered achievable based on game theoretic considerations. We then propose to use Nash bargaining solution as a tool that provides preferred points on the boundary of the game theoretic rate region. We provide analysis for the 2x2 intereference channel using the FDM achievable rate region. We also outline how to generalize our results to other achievable rate regions for the interference channel as well as the multiple access channel. Keywords: Spectrum optimization, distributed coordination, game theory, interference channel, multiple access channel.
Using SMART for Customized Monitoring of Windows Services
Venue: arXiv cs.NI 2006
Year: 2006

We focus on examining and working with an important category of computer software called Services, which are provided as a part of newer Microsoft Windows operating systems. A typical Windows user transparently utilizes many of these services but is frequently unaware of their existence. Since some services have the potential to create significant problems when they are executing, it is important for a system administrator to identify which services are running on the network, the types of processing done by each service, and any interrelationships among the various services. This information can then be used to improve the overall integrity of both the individual computer where a questionable service is running and in aggregate an entire network of computers. NCSA has developed an application called SMART (Services Monitoring And Reporting Tool) that can be used to identify and display all services currently running in the network. A commercial program called Hyena remotely monitors the services on all computers attached to the network and exports this information to SMART. SMART produces various outputs that the system administrator can analyze and then determine appropriate actions to take. In particular, SMART provides a color coordinated user interface to quickly identify and classify both potentially hazardous services and also unknown services.
A Business Goal Driven Approach for Understanding and Specifying Information Security Requirements
Venue: arXiv cs.CR 2006
Year: 2006

In this paper we present an approach for specifying and prioritizing information security requirements in organizations. It is important to prioritize security requirements since hundred per cent security is not achievable and the limited resources available should be directed to satisfy the most important ones. We propose to link explicitly security requirements with the organization's business vision, i.e. to provide business rationale for security requirements. The rationale is then used as a basis for comparing the importance of different security requirements. A conceptual framework is presented, where the relationships between business vision, critical impact factors and valuable assets (together with their security requirements) are shown.
Semi-Supervised Learning -- A Statistical Physics Approach
Venue: arXiv cs.LG 2006
Year: 2006

We present a novel approach to semi-supervised learning which is based on statistical physics. Most of the former work in the field of semi-supervised learning classifies the points by minimizing a certain energy function, which corresponds to a minimal k-way cut solution. In contrast to these methods, we estimate the distribution of classifications, instead of the sole minimal k-way cut, which yields more accurate and robust results. Our approach may be applied to all energy functions used for semi-supervised learning. The method is based on sampling using a Multicanonical Markov chain Monte-Carlo algorithm, and has a straightforward probabilistic interpretation, which allows for soft assignments of points to classes, and also to cope with yet unseen class types. The suggested approach is demonstrated on a toy data set and on two real-life data sets of gene expression.
The Case for Modeling Security, Privacy, Usability and Reliability (SPUR) in Automotive Software
Venue: arXiv cs.SE 2006
Year: 2006

Over the past five years, there has been considerable growth and established value in the practice of modeling automotive software requirements. Much of this growth has been centered on requirements of software associated with the established functional areas of an automobile, such as those associated with powertrain, chassis, body, safety and infotainment. This paper makes a case for modeling four additional attributes that are increasingly important as vehicles become information conduits: security, privacy, usability, and reliability. These four attributes are important in creating specifications for embedded in-vehicle automotive software.
Communication Bottlenecks in Scale-Free Networks
Venue: arXiv cs.NI 2006
Year: 2006

We consider the effects of network topology on the optimality of packet routing quantified by $γ_c$, the rate of packet insertion beyond which congestion and queue growth occurs. The key result of this paper is to show that for any network, there exists an absolute upper bound, expressed in terms of vertex separators, for the scaling of $γ_c$ with network size $N$, irrespective of the routing algorithm used. We then derive an estimate to this upper bound for scale-free networks, and introduce a novel static routing protocol which is superior to shortest path routing under intense packet insertion rates.
An Extremal Inequality Motivated by Multiterminal Information Theoretic Problems
Venue: arXiv cs.IT 2006
Year: 2006

We prove a new extremal inequality, motivated by the vector Gaussian broadcast channel and the distributed source coding with a single quadratic distortion constraint problems. As a corollary, this inequality yields a generalization of the classical entropy-power inequality (EPI). As another corollary, this inequality sheds insight into maximizing the differential entropy of the sum of two dependent random variables.