OpenRaiser/Intern-Atlas huggingface dataset:
Course Material Selection Rubric for Creating Network Security Courses
Venue: arXiv cs.CY 2009
Year: 2009

Teaching network security can be a difficult task for university teachers, especially for teachers at smaller universities where the course loads are more diverse. Creating a new course in network security requires investigation into multiple subject areas within the field and from multiple sources. This task can be daunting and overwhelming for teachers from smaller universities because of their requirement to teach multiple subjects, not just network security. Along with the requirement of teachers to understand the material that they wish to teach, the factors of obsolescence and the ability to build material off of core topics need to be addressed. These three factors are difficult for a smaller university teacher to address without a set of standards to analyze these areas. A rubric addressing these topic areas of timelessness, associability, and simplicity has been created to assist in the selection of materials based on the three criteria. The use of this rubric provides an effective means to choose material for a new course and help teachers to present the material they determine most appropriate to teach.
Spherical Distribution of 5 Points with Maximal Distance Sum
Venue: arXiv cs.DM 2009
Year: 2009

In this paper, we mainly consider the problem of spherical distribution of 5 points, that is, how to configure 5 points on a sphere such that the mutual distance sum attains the maximum. It is conjectured that the sum of distances is maximal if 5 points form a bipyramid configuration in which case two points are positioned at two poles of the sphere and the other three are positioned uniformly on the equator. We study this problem using interval methods and related technics, and give a proof for the conjecture through computers in finite time.
On the Decidability of (ground) Reachability Problems for Cryptographic Protocols (extended version)
Venue: arXiv cs.LO 2009
Year: 2009

Analysis of cryptographic protocols in a symbolic model is relative to a deduction system that models the possible actions of an attacker regarding an execution of this protocol. We present in this paper a transformation algorithm for such deduction systems provided the equational theory has the finite variant property. the termination of this transformation entails the decidability of the ground reachability problems. We prove that it is necessary to add one other condition to obtain the decidability of non-ground problems, and provide one new such criterion.
Error Exponents for Broadcast Channels with Degraded Message Sets
Venue: arXiv cs.IT 2009
Year: 2009

We consider a broadcast channel with a degraded message set, in which a single transmitter sends a common message to two receivers and a private message to one of the receivers only. The main goal of this work is to find new lower bounds to the error exponents of the strong user, the one that should decode both messages, and of the weak user, that should decode only the common message. Unlike previous works, where suboptimal decoders where used, the exponents we derive in this work pertain to optimal decoding and depend on both rates. We take two different approaches. The first approach is based, in part, on variations of Gallager-type bounding techniques that were presented in a much earlier work on error exponents for erasure/list decoding. The resulting lower bounds are quite simple to understand and to compute. The second approach is based on a technique that is rooted in statistical physics, and it is exponentially tight from the initial step and onward. This technique is based on analyzing the statistics of certain enumerators. Numerical results show that the bounds obtained by this technique are tighter than those obtained by the first approach and previous results. The derivation, however, is more complex than the first approach and the retrieved exponents are harder to compute.
A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds
Venue: arXiv cs.DS 2009
Year: 2009

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds. To illustrate the approach we consider three problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009). We show that a generalization of one of the problems and non-trivial special cases of the other two are fixed-parameter tractable.
The Physics of Compressive Sensing and the Gradient-Based Recovery Algorithms
Venue: arXiv cs.IT 2009
Year: 2009

The physics of compressive sensing (CS) and the gradient-based recovery algorithms are presented. First, the different forms for CS are summarized. Second, the physical meanings of coherence and measurement are given. Third, the gradient-based recovery algorithms and their geometry explanations are provided. Finally, we conclude the report and give some suggestion for future work.
On "A Novel Maximum Likelihood Decoding Algorithm for Orthogonal Space-Time Block Codes"
Venue: arXiv cs.IT 2009
Year: 2009

The computational complexity of the Maximum Likelihood decoding algorithm in [1], [2] for orthogonal space-time block codes is smaller than specified.
Uniform unweighted set cover: The power of non-oblivious local search
Venue: arXiv cs.DS 2009
Year: 2009

We are given n base elements and a finite collection of subsets of them. The size of any subset varies between p to k (p < k). In addition, we assume that the input contains all possible subsets of size p. Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of (p,k) = (2,4). The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering i new elements, starting from i = k down to i = p+1. At a final step we cover the remaining base elements by the subsets of size p. We derive the exact performance guarantee of this algorithm for all values of k and p, which is less than Hk, where Hk is the k'th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted k-set cover problem (in which subset sizes are only restricted not to exceed k), and hence it serves as a benchmark for our improved algorithm. The improved algorithm for the special case of (p,k) = (2,4) is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of 1.5 + epsilon, and the local search algorithm achieves a better ratio, which is bounded by 1.458333... + epsilon.
Segmentation of Facial Expressions Using Semi-Definite Programming and Generalized Principal Component Analysis
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, we use semi-definite programming and generalized principal component analysis (GPCA) to distinguish between two or more different facial expressions. In the first step, semi-definite programming is used to reduce the dimension of the image data and "unfold" the manifold which the data points (corresponding to facial expressions) reside on. Next, GPCA is used to fit a series of subspaces to the data points and associate each data point with a subspace. Data points that belong to the same subspace are claimed to belong to the same facial expression category. An example is provided.
Towards Improving Validation, Verification, Crash Investigations, and Event Reconstruction of Flight-Critical Systems with Self-Forensics
Venue: arXiv cs.SE 2009
Year: 2009

This paper introduces a novel concept of self-forensics to complement the standard autonomic self-CHOP properties of the self-managed systems, to be specified in the Forensic Lucid language. We argue that self-forensics, with the forensics taken out of the cybercrime domain, is applicable to "self-dissection" for the purpose of verification of autonomous software and hardware systems of flight-critical systems for automated incident and anomaly analysis and event reconstruction by the engineering teams in a variety of incident scenarios during design and testing as well as actual flight data.
Ideal Stabilization
Venue: arXiv cs.DC 2009
Year: 2009

We define and explore the concept of ideal stabilization. The program is ideally stabilizing if its every state is legitimate. Ideal stabilization allows the specification designer to prescribe with arbitrary degree of precision not only the fault-free program behavior but also its recovery operation. Specifications may or may not mention all possible states. We identify approaches to designing ideal stabilization to both kinds of specifications. For the first kind, we state the necessary condition for an ideally stabilizing solution. On the basis of this condition we prove that there is no ideally stabilizing solution to the leader election problem. We illustrate the utility of the concept by providing examples of well-known programs and proving them ideally stabilizing. Specifically, we prove ideal stabilization of the conflict manager, the alternator, the propagation of information with feedback and the alternating bit protocol.
Ftklipse - Design and Implementation of an Extendable Computer Forensics Environment: Specification Design Document
Venue: arXiv cs.CR 2009
Year: 2009

The purpose of this work is to design and implement a plugin-based environment that allows to integrate forensic tools working together to support programming tasks and addition of new tools. Integration is done through GUI components. The end-system environment must have user friendly GUI, configuration capabilities, plug-in capabilities to insert/inject new tools, case management, and chain of custody capabilities, along with evidence gathering capabilities, evidence preservation capabilities, and, finally report generation capabilities. A subset of these requirements has been implemented in Ftklipse, an open-source project, which is detailed throughout the rest of this document.
On the Representation of Finite Automata
Venue: arXiv cs.FL 2009
Year: 2009

We give an unique string representation, up to isomorphism, for initially connected deterministic finite automata (ICDFAs) with n states over an alphabet of k symbols. We show how to generate all these strings for each n and k, and how its enumeration provides an alternative way to obtain the exact number of ICDFAs.
The use of dynamic distance potential fields for pedestrian flow around corners
Venue: arXiv cs.MA 2009
Year: 2009

This contribution investigates situations in pedestrian dynamics, where trying to walk the shortest path leads to largely different results than trying to walk the quickest path. A heuristic one-shot method to model the influence of the will to walk the quickest path is introduced.
Maximal digital straight segments and convergence of discrete geometric estimators
Venue: arXiv cs.CV 2009
Year: 2009

Discrete geometric estimators approach geometric quantities on digitized shapes without any knowledge of the continuous shape. A classical yet difficult problem is to show that an estimator asymptotically converges toward the true geometric quantity as the resolution increases. We study here the convergence of local estimators based on Digital Straight Segment (DSS) recognition. It is closely linked to the asymptotic growth of maximal DSS, for which we show bounds both about their number and sizes. These results not only give better insights about digitized curves but indicate that curvature estimators based on local DSS recognition are not likely to converge. We indeed invalidate an hypothesis which was essential in the only known convergence theorem of a discrete curvature estimator. The proof involves results from arithmetic properties of digital lines, digital convexity, combinatorics, continued fractions and random polytopes.
Chebyshev Expansions for Solutions of Linear Differential Equations
Venue: arXiv cs.SC 2009
Year: 2009

A Chebyshev expansion is a series in the basis of Chebyshev polynomials of the first kind. When such a series solves a linear differential equation, its coefficients satisfy a linear recurrence equation. We interpret this equation as the numerator of a fraction of linear recurrence operators. This interpretation lets us give a simple view of previous algorithms, analyze their complexity, and design a faster one for large orders.
A measurement driven, 802.11 anti-jamming system
Venue: arXiv cs.NI 2009
Year: 2009

Dense, unmanaged 802.11 deployments tempt saboteurs into launching jamming attacks by injecting malicious interference. Nowadays, jammers can be portable devices that transmit intermittently at low power in order to conserve energy. In this paper, we first conduct extensive experiments on an indoor 802.11 network to assess the ability of two physical layer functions, rate adaptation and power control, in mitigating jamming. In the presence of a jammer we find that: (a) the use of popular rate adaptation algorithms can significantly degrade network performance and, (b) appropriate tuning of the carrier sensing threshold allows a transmitter to send packets even when being jammed and enables a receiver capture the desired signal. Based on our findings, we build ARES, an Anti-jamming REinforcement System, which tunes the parameters of rate adaptation and power control to improve the performance in the presence of jammers. ARES ensures that operations under benign conditions are unaffected. To demonstrate the effectiveness and generality of ARES, we evaluate it in three wireless testbeds: (a) an 802.11n WLAN with MIMO nodes, (b) an 802.11a/g mesh network with mobile jammers and (c) an 802.11a WLAN. We observe that ARES improves the network throughput across all testbeds by up to 150%.
Personal applications, based on moveable / resizable elements
Venue: arXiv cs.HC 2009
Year: 2009

All the modern day applications have the interface, absolutely defined by the developers. The use of adaptive interface or dynamic layout allows some variations, but even all of them are predetermined on the design stage, because the best reaction (from designer's view) on any possible users' movement was hardcoded. But there is a different world of applications, totally constructed on moveable / resizable elements; such applications turn the full control to the users. The crucial thing in such programs is that not something but everything must become moveable and resizable. This article describes the features of such applications and the algorithm behind their design.
Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere
Venue: arXiv cs.CG 2009
Year: 2009

We present two exact implementations of efficient output-sensitive algorithms that compute Minkowski sums of two convex polyhedra in 3D. We do not assume general position. Namely, we handle degenerate input, and produce exact results. We provide a tight bound on the exact maximum complexity of Minkowski sums of polytopes in 3D in terms of the number of facets of the summand polytopes. The algorithms employ variants of a data structure that represents arrangements embedded on two-dimensional parametric surfaces in 3D, and they make use of many operations applied to arrangements in these representations. We have developed software components that support the arrangement data-structure variants and the operations applied to them. These software components are generic, as they can be instantiated with any number type. However, our algorithms require only (exact) rational arithmetic. These software components together with exact rational-arithmetic enable a robust, efficient, and elegant implementation of the Minkowski-sum constructions and the related applications. These software components are provided through a package of the Computational Geometry Algorithm Library (CGAL) called Arrangement_on_surface_2. We also present exact implementations of other applications that exploit arrangements of arcs of great circles embedded on the sphere. We use them as basic blocks in an exact implementation of an efficient algorithm that partitions an assembly of polyhedra in 3D with two hands using infinite translations. This application distinctly shows the importance of exact computation, as imprecise computation might result with dismissal of valid partitioning-motions.
Communications in cellular automata
Venue: arXiv cs.CC 2009
Year: 2009

The goal of this paper is to show why the framework of communication complexity seems suitable for the study of cellular automata. Researchers have tackled different algorithmic problems ranging from the complexity of predicting to the decidability of different dynamical properties of cellular automata. But the difference here is that we look for communication protocols arising in the dynamics itself. Our work is guided by the following idea: if we are able to give a protocol describing a cellular automaton, then we can understand its behavior.
Self-Assembly of Infinite Structures
Venue: arXiv cs.CC 2009
Year: 2009

We review some recent results related to the self-assembly of infinite structures in the Tile Assembly Model. These results include impossibility results, as well as novel tile assembly systems in which shapes and patterns that represent various notions of computation self-assemble. Several open questions are also presented and motivated.
Efficient And Portable SDR Waveform Development: The Nucleus Concept
Venue: arXiv cs.IT 2009
Year: 2009

Future wireless communication systems should be flexible to support different waveforms (WFs) and be cognitive to sense the environment and tune themselves. This has lead to tremendous interest in software defined radios (SDRs). Constraints like throughput, latency and low energy demand high implementation efficiency. The tradeoff of going for a highly efficient implementation is the increase of porting effort to a new hardware (HW) platform. In this paper, we propose a novel concept for WF development, the Nucleus concept, that exploits the common structure in various wireless signal processing algorithms and provides a way for efficient and portable implementation. Tool assisted WF mapping and exploration is done efficiently by propagating the implementation and interface properties of Nuclei. The Nucleus concept aims at providing software flexibility with high level programmability, but at the same time limiting HW flexibility to maximize area and energy efficiency.
On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results
Venue: arXiv cs.CC 2009
Year: 2009

Several older and more recent results on the boundaries of solvability and unsolvability in tag systems are surveyed. Emphasis will be put on the significance of computer experiments in research on very small tag systems.
The parameterized complexity of some geometric problems in unbounded dimension
Venue: arXiv cs.CG 2009
Year: 2009

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$: i) Given $n$ points in $\Rd$, compute their minimum enclosing cylinder. ii) Given two $n$-point sets in $\Rd$, decide whether they can be separated by two hyperplanes. iii) Given a system of $n$ linear inequalities with $d$ variables, find a maximum-size feasible subsystem. We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension $d$. %and hence not solvable in ${O}(f(d)n^c)$ time, for any computable function $f$ and constant $c$ %(unless FPT=W[1]). Our reductions also give a $n^{Ω(d)}$-time lower bound (under the Exponential Time Hypothesis).
Efficient Offline Algorithmic Techniques for Several Packet Routing Problems in Distributed Systems
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we consider several problems concerning packet routing in distributed systems. Each problem is formulated using terms from Graph Theory and for each problem we present efficient, novel, algorithmic techniques for computing optimal solutions. We address topics like: bottleneck paths (trees), optimal paths with non-linear costs, optimal paths with multiple optimization objectives, maintaining aggregate connectivity information under a sequence of network link failures, and several others.
Finding Significant Subregions in Large Image Databases
Venue: arXiv cs.DB 2009
Year: 2009

Images have become an important data source in many scientific and commercial domains. Analysis and exploration of image collections often requires the retrieval of the best subregions matching a given query. The support of such content-based retrieval requires not only the formulation of an appropriate scoring function for defining relevant subregions but also the design of new access methods that can scale to large databases. In this paper, we propose a solution to this problem of querying significant image subregions. We design a scoring scheme to measure the similarity of subregions. Our similarity measure extends to any image descriptor. All the images are tiled and each alignment of the query and a database image produces a tile score matrix. We show that the problem of finding the best connected subregion from this matrix is NP-hard and develop a dynamic programming heuristic. With this heuristic, we develop two index based scalable search strategies, TARS and SPARS, to query patterns in a large image repository. These strategies are general enough to work with other scoring schemes and heuristics. Experimental results on real image datasets show that TARS saves more than 87% query time on small queries, and SPARS saves up to 52% query time on large queries as compared to linear search. Qualitative tests on synthetic and real datasets achieve precision of more than 80%.
Two-Dimensional ARMA Modeling for Breast Cancer Detection and Classification
Venue: arXiv cs.AI 2009
Year: 2009

We propose a new model-based computer-aided diagnosis (CAD) system for tumor detection and classification (cancerous v.s. benign) in breast images. Specifically, we show that (x-ray, ultrasound and MRI) images can be accurately modeled by two-dimensional autoregressive-moving average (ARMA) random fields. We derive a two-stage Yule-Walker Least-Squares estimates of the model parameters, which are subsequently used as the basis for statistical inference and biophysical interpretation of the breast image. We use a k-means classifier to segment the breast image into three regions: healthy tissue, benign tumor, and cancerous tumor. Our simulation results on ultrasound breast images illustrate the power of the proposed approach.
Using Agent to Coordinate Web Services
Venue: arXiv cs.CR 2009
Year: 2009

Traditionally, agent and web service are two separate research areas. We figure that, through agent communication, agent is suitable to coordinate web services. However, there exist agent communication problems due to the lack of uniform, cross-platform vocabulary. Fortunately, ontology defines a vocabulary. We thus propose a new agent communication layer and present the web ontology language (OWL)-based operational ontologies that provides a declarative description. It can be accessed by various engines to facilitate agent communication. Further, in our operational ontologies, we define the mental attitudes of agents that can be shared among other agents. Our architecture enhanced the 3APL agent platform, and it is implemented as an agent communication framework. Finally, we extended the framework to be compatible with the web ontology language for service (OWL-S), and then develop a movie recommendation system with four OWL-S semantic web services on the framework. The benefits of this work are: 1) dynamic web service coordination, 2) ontological reasoning through uniform representation, namely, the declarative description, and 3) easy reuse and extension of both ontology and engine through extending ontology.