OpenRaiser/Intern-Atlas huggingface dataset:
Measures of edge-uncolorability
Venue: arXiv cs.DM 2010
Year: 2010

The resistance $r(G)$ of a graph $G$ is the minimum number of edges that have to be removed from $G$ to obtain a graph which is $Δ(G)$-edge-colorable. The paper relates the resistance to other parameters that measure how far is a graph from being $Δ$-edge-colorable. The first part considers regular graphs and the relation of the resistance to structural properties in terms of 2-factors. The second part studies general (multi-) graphs $G$. Let $r_v(G)$ be the minimum number of vertices that have to be removed from $G$ to obtain a class 1 graph. We show that $\frac{r(G)}{r_v(G)} \leq \lfloor \frac{Δ(G)}{2} \rfloor$, and that this bound is best possible.
Robust multi-camera view face recognition
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents multi-appearance fusion of Principal Component Analysis (PCA) and generalization of Linear Discriminant Analysis (LDA) for multi-camera view offline face recognition (verification) system. The generalization of LDA has been extended to establish correlations between the face classes in the transformed representation and this is called canonical covariate. The proposed system uses Gabor filter banks for characterization of facial features by spatial frequency, spatial locality and orientation to make compensate to the variations of face instances occurred due to illumination, pose and facial expression changes. Convolution of Gabor filter bank to face images produces Gabor face representations with high dimensional feature vectors. PCA and canonical covariate are then applied on the Gabor face representations to reduce the high dimensional feature spaces into low dimensional Gabor eigenfaces and Gabor canonical faces. Reduced eigenface vector and canonical face vector are fused together using weighted mean fusion rule. Finally, support vector machines (SVM) have trained with augmented fused set of features and perform the recognition task. The system has been evaluated with UMIST face database consisting of multiview faces. The experimental results demonstrate the efficiency and robustness of the proposed system for multi-view face images with high recognition rates. Complexity analysis of the proposed system is also presented at the end of the experimental results.
Offline Signature Identification by Fusion of Multiple Classifiers using Statistical Learning Theory
Venue: arXiv cs.CV 2010
Year: 2010

This paper uses Support Vector Machines (SVM) to fuse multiple classifiers for an offline signature system. From the signature images, global and local features are extracted and the signatures are verified with the help of Gaussian empirical rule, Euclidean and Mahalanobis distance based classifiers. SVM is used to fuse matching scores of these matchers. Finally, recognition of query signatures is done by comparing it with all signatures of the database. The proposed system is tested on a signature database contains 5400 offline signatures of 600 individuals and the results are found to be promising.
CWTS crown indicator measures citation impact of a research group's publication oeuvre
Venue: arXiv cs.DL 2010
Year: 2010

The article "Caveats for the journal and field normalizations in the CWTS (`Leiden') evaluations of research performance", published by Tobias Opthof and Loet Leydesdorff (arXiv:1002.2769) deals with a subject as important as the application of so called field normalized indicators of citation impact in the assessment of research performance of individual researchers and research groups. Field normalization aims to account for differences in citation practices across scientific-scholarly subject fields. As the primary author of the papers presenting the "Leiden" indicators and of many reports and articles reporting on the outcomes of assessments actually using these measures, I comment on the 3 main issues addressed in the paper by Opthof and Leydesdorff.
A Characterization of Combined Traces Using Labeled Stratified Order Structures
Venue: arXiv cs.DC 2010
Year: 2010

This paper defines a class of labeled stratified order structures that characterizes exactly the notion of combined traces (i.e., comtraces) proposed by Janicki and Koutny in 1995. Our main technical contributions are the representation theorems showing that comtrace quotient monoid, combined dependency graph (Kleijn and Koutny 2008) and our labeled stratified order structure characterization are three different and yet equivalent ways to represent comtraces.
Quantitative Information Flow - Verification Hardness and Possibilities
Venue: arXiv cs.CR 2010
Year: 2010

Researchers have proposed formal definitions of quantitative information flow based on information theoretic notions such as the Shannon entropy, the min entropy, the guessing entropy, and channel capacity. This paper investigates the hardness and possibilities of precisely checking and inferring quantitative information flow according to such definitions. We prove that, even for just comparing two programs on which has the larger flow, none of the definitions is a k-safety property for any k, and therefore is not amenable to the self-composition technique that has been successfully applied to precisely checking non-interference. We also show a complexity theoretic gap with non-interference by proving that, for loop-free boolean programs whose non-interference is coNP-complete, the comparison problem is #P-hard for all of the definitions. For positive results, we show that universally quantifying the distribution in the comparison problem, that is, comparing two programs according to the entropy based definitions on which has the larger flow for all distributions, is a 2-safety problem in general and is coNP-complete when restricted for loop-free boolean programs. We prove this by showing that the problem is equivalent to a simple relation naturally expressing the fact that one program is more secure than the other. We prove that the relation also refines the channel-capacity based definition, and that it can be precisely checked via the self-composition as well as the "interleaved" self-composition technique.
A New Proof for the Correctness of F5 (F5-Like) Algorithm
Venue: arXiv cs.SC 2010
Year: 2010

The famous F5 algorithm for computing Gröbner basis was presented by Faugère in 2002 without complete proofs for its correctness. The current authors have simplified the original F5 algorithm into an F5 algorithm in Buchberger's style (F5B algorithm), which is equivalent to original F5 algorithm and may deduce some F5-like versions. In this paper, the F5B algorithm is briefly revisited and a new complete proof for the correctness of F5B algorithm is proposed. This new proof is not limited to homogeneous systems and does not depend on the strategy of selecting critical pairs (i.e. the strategy deciding which critical pair is computed first) such that any strategy could be utilized in F5B (F5) algorithm. From this new proof, we find that the special reduction procedure (F5-reduction) is the key of F5 algorithm, so maintaining this special reduction, various variation algorithms become available. A natural variation of F5 algorithm, which transforms original F5 algorithm to a non-incremental algorithm, is presented and proved in this paper as well. This natural variation has been implemented over the Boolean ring. The two revised criteria in this natural variation are also able to reject almost all unnecessary computations and few polynomials reduce to 0 in most examples.
Opportunistic Routing in Ad Hoc Networks: How many relays should there be? What rate should nodes use?
Venue: arXiv cs.NI 2010
Year: 2010

Opportunistic routing is a multi-hop routing scheme which allows for selection of the best immediately available relay. In blind opportunistic routing protocols, where transmitters blindly broadcast without knowledge of the surrounding nodes, two fundamental design parameters are the node transmission probability and the transmission spectral efficiency. In this paper these parameters are selected to maximize end-to-end performance, characterized by the product of transmitter density, hop distance and rate. Due to the intractability of the problem as stated, an approximation function is examined which proves reasonably accurate. Our results show how the above design parameters should be selected based on inherent system parameters such as the path loss exponent and the noise level.
Radio Interface for High Data Rate Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper gives an overview of radio interfaces devoted for high data rate Wireless Sensor Networks. Four aerospace applications of WSN are presented to underline the importance of achieving high data rate. Then, two modulation schemes by which High Data Rate can be achieved are compared : Multi carrier approaches, represented by the popular Orthogonal Frequency Division Multiplexing (OFDM) and Single carrier methods, represented by Single Carrier Frequency division Equalization and its application for multiple access Single Carrier Frequency division multiple Access (SC-FDMA). SC-FDMA, with a very low Peak Average Power Ratio (PAPR), is as strong alternative to the OFDM scheme for highly power constraint application. The Chosen radio interface will be, finally, tested by a model based design approach based on Simulink and FPGA realization. SC-FDMA, with a very low Peak Average Power Ratio (PAPR), is as strong alternative to the OFDM scheme for highly power constraint application. The Chosen radio interface will be, finally, tested by a model based design approach based on Simulink and FPGA realization.
Affective Ludology, Flow and Immersion in a First- Person Shooter: Measurement of Player Experience
Venue: arXiv cs.HC 2010
Year: 2010

Gameplay research about experiential phenomena is a challenging undertaking, given the variety of experiences that gamers encounter when playing and which currently do not have a formal taxonomy, such as flow, immersion, boredom, and fun. These informal terms require a scientific explanation. Ludologists also acknowledge the need to understand cognition, emotion, and goal- oriented behavior of players from a psychological perspective by establishing rigorous methodologies. This paper builds upon and extends prior work in an area for which we would like to coin the term "affective ludology." The area is concerned with the affective measurement of player-game interaction. The experimental study reported here investigated different traits of gameplay experience using subjective (i.e., questionnaires) and objective (i.e., psychophysiological) measures. Participants played three Half-Life 2 game level design modifications while measures such as electromyography (EMG), electrodermal activity (EDA) were taken and questionnaire responses were collected. A level designed for combat-oriented flow experience demonstrated significant high-arousal positive affect emotions. This method shows that emotional patterns emerge from different level designs, which has great potential for providing real-time emotional profiles of gameplay that may be generated together with self- reported subjective player experience descriptions.
Trends and Techniques in Visual Gaze Analysis
Venue: arXiv cs.HC 2010
Year: 2010

Visualizing gaze data is an effective way for the quick interpretation of eye tracking results. This paper presents a study investigation benefits and limitations of visual gaze analysis among eye tracking professionals and researchers. The results were used to create a tool for visual gaze analysis within a Master's project.
The Degraded Poisson Wiretap Channel
Venue: arXiv cs.IT 2010
Year: 2010

Providing security guarantees for wireless communication is critically important for today's applications. While previous work in this area has concentrated on radio frequency (RF) channels, providing security guarantees for RF channels is inherently difficult because they are prone to rapid variations due small scale fading. Wireless optical communication, on the other hand, is inherently more secure than RF communication due to the intrinsic aspects of the signal propagation in the optical and near-optical frequency range. In this paper, secure communication over wireless optical links is examined by studying the secrecy capacity of a direct detection system. For the degraded Poisson wiretap channel, a closed-form expression of the secrecy capacity is given. A complete characterization of the general rate-equivocation region is also presented. For achievability, an optimal code is explicitly constructed by using the structured code designed by Wyner for the Poisson channel. The converse is proved in two different ways: the first method relies only on simple properties of the conditional expectation and basic information theoretical inequalities, whereas the second method hinges on the recent link established between minimum mean square estimation and mutual information in Poisson channels.
Approximation Algorithms for Campaign Management
Venue: arXiv cs.GT 2010
Year: 2010

We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.
Network Code Design for Orthogonal Two-hop Network with Broadcasting Relay: A Joint Source-Channel-Network Coding Approach
Venue: arXiv cs.IT 2010
Year: 2010

This paper addresses network code design for robust transmission of sources over an orthogonal two-hop wireless network with a broadcasting relay. The network consists of multiple sources and destinations in which each destination, benefiting the relay signal, intends to decode a subset of the sources. Two special instances of this network are orthogonal broadcast relay channel and the orthogonal multiple access relay channel. The focus is on complexity constrained scenarios, e.g., for wireless sensor networks, where channel coding is practically imperfect. Taking a source-channel and network coding approach, we design the network code (mapping) at the relay such that the average reconstruction distortion at the destinations is minimized. To this end, by decomposing the distortion into its components, an efficient design algorithm is proposed. The resulting network code is nonlinear and substantially outperforms the best performing linear network code. A motivating formulation of a family of structured nonlinear network codes is also presented. Numerical results and comparison with linear network coding at the relay and the corresponding distortion-power bound demonstrate the effectiveness of the proposed schemes and a promising research direction.
An Oblivious Spanning Tree for Buy-at-Bulk Network Design Problems
Venue: arXiv cs.DS 2010
Year: 2010

We consider the problem of constructing a single spanning tree for the single-source buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands (or data) along a graph to or from a designated root node. The demands could be aggregated at (or symmetrically distributed to) intermediate nodes where the fusion-cost is specified by a non-negative concave function $f$. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number of data sources (or demands) and cost function at intermediate nodes. To our knowledge, this is the first paper to propose a single spanning tree solution to this problem (as opposed to multiple overlay trees). There has been no prior work where the tree is oblivious to both the fusion cost function and the set of sources (demands). We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling graphs that guarantees $\log^{3}D\cdot\log n$-approximation over the optimal cost, where $D$ is the diameter of the graph and $n$ the total number of nodes. With constant fusion-cost function our spanning tree gives a $O(\log^3 D)$-approximation for every Steiner tree to the root.
Estimating Self-Sustainability in Peer-to-Peer Swarming Systems
Venue: arXiv cs.NI 2010
Year: 2010

Peer-to-peer swarming is one of the \emph{de facto} solutions for distributed content dissemination in today's Internet. By leveraging resources provided by clients, swarming systems reduce the load on and costs to publishers. However, there is a limit to how much cost savings can be gained from swarming; for example, for unpopular content peers will always depend on the publisher in order to complete their downloads. In this paper, we investigate this dependence. For this purpose, we propose a new metric, namely \emph{swarm self-sustainability}. A swarm is referred to as self-sustaining if all its blocks are collectively held by peers; the self-sustainability of a swarm is the fraction of time in which the swarm is self-sustaining. We pose the following question: how does the self-sustainability of a swarm vary as a function of content popularity, the service capacity of the users, and the size of the file? We present a model to answer the posed question. We then propose efficient solution methods to compute self-sustainability. The accuracy of our estimates is validated against simulation. Finally, we also provide closed-form expressions for the fraction of time that a given number of blocks is collectively held by peers.
CONCISE: Compressed 'n' Composable Integer Set
Venue: arXiv cs.DS 2010
Year: 2010

Bit arrays, or bitmaps, are used to significantly speed up set operations in several areas, such as data warehousing, information retrieval, and data mining, to cite a few. However, bitmaps usually use a large storage space, thus requiring compression. Nevertheless, there is a space-time tradeoff among compression schemes. The Word Aligned Hybrid (WAH) bitmap compression trades some space to allow for bitwise operations without first decompressing bitmaps. WAH has been recognized as the most efficient scheme in terms of computation time. In this paper we present CONCISE (Compressed 'n' Composable Integer Set), a new scheme that enjoys significatively better performances than those of WAH. In particular, when compared to WAH, our algorithm is able to reduce the required memory up to 50%, by having similar or better performance in terms of computation time. Further, we show that CONCISE can be efficiently used to manipulate bitmaps representing sets of integral numbers in lieu of well-known data structures such as arrays, lists, hashtables, and self-balancing binary search trees. Extensive experiments over synthetic data show the effectiveness of our approach.
Restricted Common Superstring and Restricted Common Supersequence
Venue: arXiv cs.DS 2010
Year: 2010

The {\em shortest common superstring} and the {\em shortest common supersequence} are two well studied problems having a wide range of applications. In this paper we consider both problems with resource constraints, denoted as the Restricted Common Superstring (shortly \textit{RCSstr}) problem and the Restricted Common Supersequence (shortly \textit{RCSseq}). In the \textit{RCSstr} (\textit{RCSseq}) problem we are given a set $S$ of $n$ strings, $s_1$, $s_2$, $\ldots$, $s_n$, and a multiset $t = \{t_1, t_2, \dots, t_m\}$, and the goal is to find a permutation $π: \{1, \dots, m\} \to \{1, \dots, m\}$ to maximize the number of strings in $S$ that are substrings (subsequences) of $π(t) = t_{π(1)}t_{π(2)}...t_{π(m)}$ (we call this ordering of the multiset, $π(t)$, a permutation of $t$). We first show that in its most general setting the \textit{RCSstr} problem is {\em NP-complete} and hard to approximate within a factor of $n^{1-ε}$, for any $ε> 0$, unless P = NP. Afterwards, we present two separate reductions to show that the \textit{RCSstr} problem remains NP-Hard even in the case where the elements of $t$ are drawn from a binary alphabet or for the case where all input strings are of length two. We then present some approximation results for several variants of the \textit{RCSstr} problem. In the second part of this paper, we turn to the \textit{RCSseq} problem, where we present some hardness results, tight lower bounds and approximation algorithms.
On the parity complexity measures of Boolean functions
Venue: arXiv cs.CC 2010
Year: 2010

The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decision trees, as well as with communication complexity.
User-driven applications
Venue: arXiv cs.HC 2010
Year: 2010

User-driven applications are the programs, in which the full control is given to the users. Designers of such programs are responsible only for developing an instrument for solving some task, but they do not enforce users to work with this instrument according with the predefined scenario. Users' control of the applications means that only users decide at any moment WHAT, WHEN, and HOW must appear on the screen. Such applications can be constructed only on the basis of moveable / resizable elements. Programs, based on such elements, have very interesting features and open absolutely new possibilities. This article describes the design of the user-driven applications and shows the consequences of switching to such type of programs on the samples from different areas.
Tools and techniques for Network Forensics
Venue: arXiv cs.NI 2010
Year: 2010

Network forensics deals with the capture, recording and analysis of network events in order to discover evidential information about the source of security attacks in a court of law. This paper discusses the different tools and techniques available to conduct network forensics. Some of the tools discussed include: eMailTrackerPro to identify the physical location of an email sender; Web Historian to find the duration of each visit and the files uploaded and downloaded from the visited website; packet sniffers like Etherea to capture and analyze the data exchanged among the different computers in the network. The second half of the paper presents a survey of different IP traceback techniques like packet marking that help a forensic investigator to identify the true sources of the attacking IP packets. We also discuss the use of Honeypots and Honeynets that gather intelligence about the enemy and the tools and tactics of network intruders.