OpenRaiser/Intern-Atlas huggingface dataset:
Understanding the Tenets of Agile Software Engineering: Lecturing, Exploration and Critical Thinking
Venue: arXiv cs.CY 2010
Year: 2010

The use of agile principles and practices in software development is becoming a powerful force in today's workplace. In our quest to develop better products, therefore, it is imperative that we strive to learn and understand the application of Agile methods, principles and techniques to the software development enterprise. Unfortunately, in many educational institutions courses and projects that emphasize Agile Software Development are minimal. At best, students have only limited exposure to the agile philosophy, principles and practices at the graduate and undergraduate levels of education. In an effort to address this concern, we offered a graduate-level course entitled "Agile Software Engineering" in the Department of Computer Science at Virginia Tech in Fall 2009. The primary objectives of the class were to introduce the values, principles and practices underlying the agile philosophy, and to do so in an atmosphere that encourages debate and critical thinking. The course was designed around three central components: (1) teaching the essentials of how one develops a product within an Agile framework, (2) having invited presentation by notable industry experts, and (3) having students present and discuss current research topics and issues. This paper describes our experiences during the offering of that course, and in particular, the unique perspectives of the class instructor, the teaching assistant and a student who was enrolled in the class.
Exploring Selfish Trends of Malicious Mobile Devices in MANET
Venue: arXiv cs.CY 2010
Year: 2010

The research effort on mobile computing has focused mainly on routing and usually assumes that all mobile devices (MDs) are cooperative. These assumptions hold on military or search and rescue operations, where all hosts are from the same authority and their users have common goals. The application of mobile ad hoc networks (MANETs) as open networks has emerged recently but proliferated exponentially. Energy is a valuable commodity in MANETs due to the limited battery of the portable devices. Batteries typically cannot be replaced in MANETs, making their lifetime limited. Diverse users, with unlike goals, share the resources of their devices and ensuring global connectivity comes very low in their priority. This sort of communities can already be found in wired networks, namely on peer-to-peer networks. In this scenario, open MANETs will likely resemble social environments. A group of persons can provide benefits to each of its members as long as everyone provides his contribution. For our particular case, each element of a MANET will be called to forward messages and to participate on routing protocols. A selfish behavior threatens the entire community and also this behavior is infectious as, other MDs may also start to perform in the same way. In the extreme, this can take to the complete sabotage of the network. This paper investigates the prevalent malicious attacks in MANET and analyzes recent selfish trends in MANET. We analyzed the respective strengths and vulnerabilities of the existing selfish behaviour prevention scheme.
Unprovability of the Logical Characterization of Bisimulation
Venue: arXiv cs.LO 2010
Year: 2010

We quickly review labelled Markov processes (LMP) and provide a counterexample showing that in general measurable spaces, event bisimilarity and state bisimilarity differ in LMP. This shows that the logic in Desharnais [*] does not characterize state bisimulation in non-analytic measurable spaces. Furthermore we show that, under current foundations of Mathematics, such logical characterization is unprovable for spaces that are projections of a coanalytic set. Underlying this construction there is a proof that stationary Markov processes over general measurable spaces do not have semi-pullbacks. ([*] J. Desharnais, Labelled Markov Processes. School of Computer Science. McGill University, Montréal (1999))
On Byzantine Containment Properties of the $min+1$ Protocol
Venue: arXiv cs.DC 2010
Year: 2010

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a breadth-first spanning tree in this context. Combining these two properties proves difficult: we demonstrate that it is impossible to contain the impact of Byzantine nodes in a strictly or strongly stabilizing manner. We then adopt the weaker scheme of topology-aware strict stabilization and we present a similar weakening of strong stabilization. We prove that the classical $min+1$ protocol has optimal Byzantine containment properties with respect to these criteria.
Symmetries of Symmetry Breaking Constraints
Venue: arXiv cs.AI 2010
Year: 2010

Symmetry is an important feature of many constraint programs. We show that any problem symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. This simple but powerful idea can be used in a number of different ways. We describe one application within model restarts, a search technique designed to reduce the conflict between symmetry breaking and the branching heuristic. In model restarts, we restart search periodically with a random symmetry of the symmetry breaking constraints. Experimental results show that this symmetry breaking technique is effective in practice on some standard benchmark problems.
Simple Wriggling is Hard unless You Are a Fat Hippo
Venue: arXiv cs.CG 2010
Year: 2010

We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest path for a long snake amidst polygonal obstacles is NP-hard. On the positive side, we show that snake's problem is "length-tractable": if the snake is "fat", i.e., its length/width ratio is small, the shortest path can be computed in polynomial time.
Quantitative parametrization of texts written by Ivan Franko: An attempt of the project
Venue: arXiv cs.CL 2010
Year: 2010

In the article, the project of quantitative parametrization of all texts by Ivan Franko is manifested. It can be made only by using modern computer techniques after the frequency dictionaries for all Franko's works are compiled. The paper describes the application spheres, methodology, stages, principles and peculiarities in the compilation of the frequency dictionary of the second half of the 19th century - the beginning of the 20th century. The relation between the Ivan Franko frequency dictionary, explanatory dictionary of writer's language and text corpus is discussed.
On the Utility of Directional Information for Repositioning Errant Probes in Central Force Optimization
Venue: arXiv cs.OH 2010
Year: 2010

Central Force Optimization is a global search and optimization algorithm that searches a decision space by flying "probes" whose trajectories are deterministically computed using two equations of motion. Because it is possible for a probe to fly outside the domain of feasible solutions, a simple errant probe retrieval method has been used previously that does not include the directional information contained in a probe's acceleration vector. This note investigates the effect of adding directionality to the "repositioning factor" approach. As a general proposition, it appears that doing so does not improve convergence speed or accuracy. In fact, adding directionality to the original errant probe retrieval scheme appears to be highly inadvisable. Nevertheless, there may be alternative probe retrieval schemes that do benefit from directional information, and the results reported here may assist in or encourage their development.
The DMM bound: multivariate (aggregate) separation bounds
Venue: arXiv cs.SC 2010
Year: 2010

In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (\dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Canny's gap theorem \cite{c-crmp-87} by a factor of $\OO(d^{n-1})$, where $d$ bounds the degree of the polynomials, and $n$ is the number of variables. One application is to the bitsize of the eigenvalues and eigenvectors of an integer matrix, which also yields a new proof that the problem is polynomial. We also compare against recent lower bounds on the absolute value of the root coordinates by Brownawell and Yap \cite{by-issac-2009}, obtained under the hypothesis there is a 0-dimensional projection. Our bounds are in general comparable, but exploit sparseness; they are also tighter when bounding the value of a positive polynomial over the simplex. For this problem, we also improve upon the bounds in \cite{bsr-arxix-2009,jp-arxiv-2009}. Our analysis provides a precise asymptotic upper bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milne's algorithm \cite{Miln92} in 2D.
On Omega Context Free Languages which are Borel Sets of Infinite Rank
Venue: arXiv cs.LO 2010
Year: 2010

This paper is a continuation of the study of topological properties of omega context free languages (omega-CFL). We proved before that the class of omega-CFL exhausts the hierarchy of Borel sets of finite rank, and that there exist some omega-CFL which are analytic but non Borel sets. We prove here that there exist some omega context free languages which are Borel sets of infinite (but not finite) rank, giving additional answer to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994), 583-621].
Transforming Outermost into Context-Sensitive Rewriting
Venue: arXiv cs.LO 2010
Year: 2010

We define two transformations from term rewriting systems (TRSs) to context-sensitive TRSs in such a way that termination of the target system implies outermost termination of the original system. In the transformation based on 'context extension', each outermost rewrite step is modeled by exactly one step in the transformed system. This transformation turns out to be complete for the class of left-linear TRSs. The second transformation is called `dynamic labeling' and results in smaller sized context-sensitive TRSs. Here each modeled step is adjoined with a small number of auxiliary steps. As a result state-of-the-art termination methods for context-sensitive rewriting become available for proving termination of outermost rewriting. Both transformations have been implemented in Jambox, making it the most successful tool in the category of outermost rewriting of the last edition of the annual termination competition.
Inter-atom Interference Mitigation for Sparse Signal Reconstruction Using Semi-blindly Weighted Minimum Variance Distortionless Response
Venue: arXiv cs.IT 2010
Year: 2010

The feasibility of sparse signal reconstruction depends heavily on the inter-atom interference of redundant dictionary. In this paper, a semi-blindly weighted minimum variance distortionless response (SBWMVDR) is proposed to mitigate the inter-atom interference. Examples of direction of arrival estimation are presented to show that the orthogonal match pursuit (OMP) based on SBWMVDR performs better than the ordinary OMP algorithm.
Ivan Franko's novel Dlja domashnjoho ohnyshcha (For the Hearth) in the light of the frequency dictionary
Venue: arXiv cs.CL 2010
Year: 2010

In the article, the methodology and the principles of the compilation of the Frequency dictionary for Ivan Franko's novel Dlja domashnjoho ohnyshcha (For the Hearth) are described. The following statistical parameters of the novel vocabulary are obtained: variety, exclusiveness, concentration indexes, correlation between word rank and text coverage, etc. The main quantitative characteristics of Franko's novels Perekhresni stezhky (The Cross-Paths) and Dlja domashnjoho ohnyshcha are compared on the basis of their frequency dictionaries.
Perfusion Linearity and Its Applications
Venue: arXiv cs.CE 2010
Year: 2010

Perfusion analysis computes blood flow parameters (blood volume, blood flow, mean transit time) from the observed flow of contrast agent, passing through the patient's vascular system. Perfusion deconvolution has been widely accepted as the principal numerical tool for perfusion analysis, and is used routinely in clinical applications. This extensive use of perfusion in clinical decision-making makes numerical stability and robustness of perfusion computations vital for accurate diagnostics and patient safety. The main goal of this paper is to propose a novel approach for validating numerical properties of perfusion algorithms. The approach is based on Perfusion Linearity Property (PLP), which we find in perfusion deconvolution, as well as in many other perfusion techniques. PLP allows one to study perfusion values as weighted averages of the original imaging data. This, in turn, uncovers hidden problems with the existing deconvolution techniques, and may be used to suggest more reliable computational approaches and methodology.
Stream Control Transmission Protocol Steganography
Venue: arXiv cs.CR 2010
Year: 2010

Stream Control Transmission Protocol (SCTP) is a new transport layer protocol that is due to replace TCP (Transmission Control Protocol) and UDP (User Datagram Protocol) protocols in future IP networks. Currently, it is implemented in such operating systems like BSD, Linux, HP-UX or Sun Solaris. It is also supported in Cisco network devices operating system (Cisco IOS) and may be used in Windows. This paper describes potential steganographic methods that may be applied to SCTP and may pose a threat to network security. Proposed methods utilize new, characteristic SCTP features like multi-homing and multistreaming. Identified new threats and suggested countermeasures may be used as a supplement to RFC 5062, which describes security attacks in SCTP protocol and can induce further standard modifications.
Adaptive Demodulation in Differentially Coherent Phase Systems: Design and Performance Analysis
Venue: arXiv cs.IT 2010
Year: 2010

Adaptive Demodulation (ADM) is a newly proposed rate-adaptive system which operates without requiring Channel State Information (CSI) at the transmitter (unlike adaptive modulation) by using adaptive decision region boundaries at the receiver and encoding the data with a rateless code. This paper addresses the design and performance of an ADM scheme for two common differentially coherent schemes: M-DPSK (M-ary Differential Phase Shift Keying) and M-DAPSK (M-ary Differential Amplitude and Phase Shift Keying) operating over AWGN and Rayleigh fading channels. The optimal method for determining the most reliable bits for a given differential detection scheme is presented. In addition, simple (near-optimal) implementations are provided for recovering the most reliable bits from a received pair of differentially encoded symbols for systems using 16-DPSK and 16- DAPSK. The new receivers offer the advantages of a rate-adaptive system, without requiring CSI at the transmitter and a coherent phase reference at the receiver. Bit error analysis for the ADM system in both cases is presented along with numerical results of the spectral efficiency for the rate-adaptive systems operating over a Rayleigh fading channel.
Effective Capacity and Randomness of Closed Sets
Venue: arXiv cs.LO 2010
Year: 2010

We investigate the connection between measure and capacity for the space of nonempty closed subsets of {0,1}*. For any computable measure, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions that characterize when the capacity of a random closed set equals zero or is >0. We construct for certain measures an effectively closed set with positive capacity and with Lebesgue measure zero.
Irregular Turbo Codes in Block-Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

We study irregular binary turbo codes over non-ergodic block-fading channels. We first propose an extension of channel multiplexers initially designed for regular turbo codes. We then show that, using these multiplexers, irregular turbo codes that exhibit a small decoding threshold over the ergodic Gaussian-noise channel perform very close to the outage probability on block-fading channels, from both density evolution and finite-length perspectives.
Impossibility of independence amplification in Kolmogorov complexity theory
Venue: arXiv cs.CC 2010
Year: 2010

The paper studies randomness extraction from sources with bounded independence and the issue of independence amplification of sources, using the framework of Kolmogorov complexity. The dependency of strings $x$ and $y$ is ${\rm dep}(x,y) = \max\{C(x) - C(x \mid y), C(y) - C(y\mid x)\}$, where $C(\cdot)$ denotes the Kolmogorov complexity. It is shown that there exists a computable Kolmogorov extractor $f$ such that, for any two $n$-bit strings with complexity $s(n)$ and dependency $α(n)$, it outputs a string of length $s(n)$ with complexity $s(n)- α(n)$ conditioned by any one of the input strings. It is proven that the above are the optimal parameters a Kolmogorov extractor can achieve. It is shown that independence amplification cannot be effectively realized. Specifically, if (after excluding a trivial case) there exist computable functions $f_1$ and $f_2$ such that ${\rm dep}(f_1(x,y), f_2(x,y)) \leq β(n)$ for all $n$-bit strings $x$ and $y$ with ${\rm dep}(x,y) \leq α(n)$, then $β(n) \geq α(n) - O(\log n)$.
Channel Decoding with a Bayesian Equalizer
Venue: arXiv cs.IT 2010
Year: 2010

Low-density parity-check (LPDC) decoders assume the channel estate information (CSI) is known and they have the true a posteriori probability (APP) for each transmitted bit. But in most cases of interest, the CSI needs to be estimated with the help of a short training sequence and the LDPC decoder has to decode the received word using faulty APP estimates. In this paper, we study the uncertainty in the CSI estimate and how it affects the bit error rate (BER) output by the LDPC decoder. To improve these APP estimates, we propose a Bayesian equalizer that takes into consideration not only the uncertainty due to the noise in the channel, but also the uncertainty in the CSI estimate, reducing the BER after the LDPC decoder.
On the definition of a theoretical concept of an operating system
Venue: arXiv cs.OS 2010
Year: 2010

We dwell on how a definition of a theoretical concept of an operating system, suitable to be incorporated in a mathematical theory of operating systems, could look like. This is considered a valuable preparation for the development of a mathematical theory of operating systems.
Treatment the Effects of Studio Wall Resonance and Coincidence Phenomena for Recording Noisy Speech Via FPGA Digital Filter
Venue: arXiv cs.SD 2010
Year: 2010

This work introduces an economic solution for the problems of sound insulation of recording studios. Sound insulation at wall resonance frequency is weak. Instead of acoustical treatment, a digital filter is used to eliminate the effects of wall resonance and coincidence phenomena on recording of speech. Sound insulation of studio is measured to calculate the wall resonance frequency and the coincidence frequency. Pole /zero placement technique is used to calculate the IIR filter coefficients. The digital filter is designed, simulated and implemented. The proposed system is used to treat these problems and it is shown to be effective in recording the noisy speech. In this work digital signal processing is used instead of the acoustic treatment to eliminate the effect of noise at the studio wall resonance. This technique is cheap and effective in canceling the noise at the desired frequencies. Field Programmable Gate Array (FPGA) is used for hardware implementation of the proposed filter structure which provides fast and cheap solution for processing real time audio signals. The implementation is carried out using Spartan chip from Xinlinx achieving higher performance than commercially available software solutions.
Fundamental Limits of Wideband Localization - Part I: A General Framework
Venue: arXiv cs.IT 2010
Year: 2010

The availability of positional information is of great importance in many commercial, public safety, and military applications. The coming years will see the emergence of location-aware networks with sub-meter accuracy, relying on accurate range measurements provided by wide bandwidth transmissions. In this two-part paper, we determine the fundamental limits of localization accuracy of wideband wireless networks in harsh multipath environments. We first develop a general framework to characterize the localization accuracy of a given node here and then extend our analysis to cooperative location-aware networks in Part II. In this paper, we characterize localization accuracy in terms of a performance measure called the squared position error bound (SPEB), and introduce the notion of equivalent Fisher information to derive the SPEB in a succinct expression. This methodology provides insights into the essence of the localization problem by unifying localization information from individual anchors and information from a priori knowledge of the agent's position in a canonical form. Our analysis begins with the received waveforms themselves rather than utilizing only the signal metrics extracted from these waveforms, such as time-of-arrival and received signal strength. Hence, our framework exploits all the information inherent in the received waveforms, and the resulting SPEB serves as a fundamental limit of localization accuracy.
A Low-Complexity Joint Detection-Decoding Algorithm for Nonbinary LDPC-Coded Modulation Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we present a low-complexity joint detection-decoding algorithm for nonbinary LDPC codedmodulation systems. The algorithm combines hard-decision decoding using the message-passing strategy with the signal detector in an iterative manner. It requires low computational complexity, offers good system performance and has a fast rate of decoding convergence. Compared to the q-ary sum-product algorithm (QSPA), it provides an attractive candidate for practical applications of q-ary LDPC codes.
On improving security of GPT cryptosystems
Venue: arXiv cs.CR 2010
Year: 2010

The public key cryptosystem based on rank error correcting codes (the GPT cryptosystem) was proposed in 1991. Use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This enabled using public keys of a smaller size. Several attacks against this system were published, including Gibson's attacks and more recently Overbeck's attacks. A few modifications were proposed withstanding Gibson's attack but at least one of them was broken by the stronger attacks by Overbeck. A tool to prevent Overbeck's attack is presented in [12]. In this paper, we apply this approach to other variants of the GPT cryptosystem.