OpenRaiser/Intern-Atlas huggingface dataset:
Are there any good digraph width measures?
Venue: arXiv cs.DM 2010
Year: 2010

Several different measures for digraph width have appeared in the last few years. However, none of them shares all the "nice" properties of treewidth: First, being \emph{algorithmically useful} i.e. admitting polynomial-time algorithms for all $\MS1$-definable problems on digraphs of bounded width. And, second, having nice \emph{structural properties} i.e. being monotone under taking subdigraphs and some form of arc contractions. As for the former, (undirected) $\MS1$ seems to be the least common denominator of all reasonably expressive logical languages on digraphs that can speak about the edge/arc relation on the vertex set.The latter property is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing the ordinary treewidth. Our main result is that \emph{any reasonable} algorithmically useful and structurally nice digraph measure cannot be substantially different from the treewidth of the underlying undirected graph. Moreover, we introduce \emph{directed topological minors} and argue that they are the weakest useful notion of minors for digraphs.
Node Sensing & Dynamic Discovering Routes for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

The applications of Wireless Sensor Networks (WSN) contain a wide variety of scenarios. In most of them, the network is composed of a significant number of nodes deployed in an extensive area in which not all nodes are directly connected. Then, the data exchange is supported by multihop communications. Routing protocols are in charge of discovering and maintaining the routes in the network. However, the correctness of a particular routing protocol mainly depends on the capabilities of the nodes and on the application requirements. This paper presents a dynamic discover routing method for communication between sensor nodes and a base station in WSN. This method tolerates failures of arbitrary individual nodes in the network (node failure) or a small part of the network (area failure). Each node in the network does only local routing preservation, needs to record only its neighbor nodes' information, and incurs no extra routing overhead during failure free periods. It dynamically discovers new routes when an intermediate node or a small part of the network in the path from a sensor node to a base station fails. In our planned method, every node decides its path based only on local information, such as its parent node and neighbor nodes' routing information. So, it is possible to form a loop in the routing path. We believe that the loop problem in sensor network routing is not as serious as that in the Internet routing or traditional mobile ad-hoc routing. We are trying to find all possible loops and eliminate the loops as far as possible in WSN.
Efficient multicore-aware parallelization strategies for iterative stencil computations
Venue: arXiv cs.PF 2010
Year: 2010

Stencil computations consume a major part of runtime in many scientific simulation codes. As prototypes for this class of algorithms we consider the iterative Jacobi and Gauss-Seidel smoothers and aim at highly efficient parallel implementations for cache-based multicore architectures. Temporal cache blocking is a known advanced optimization technique, which can reduce the pressure on the memory bus significantly. We apply and refine this optimization for a recently presented temporal blocking strategy designed to explicitly utilize multicore characteristics. Especially for the case of Gauss-Seidel smoothers we show that simultaneous multi-threading (SMT) can yield substantial performance improvements for our optimized algorithm.
A Model of Cloud Based Application Environment for Software Testing
Venue: arXiv cs.SE 2010
Year: 2010

Cloud computing is an emerging platform of service computing designed for swift and dynamic delivery of assured computing resources. Cloud computing provide Service-Level Agreements (SLAs) for guaranteed uptime availability for enabling convenient and on-demand network access to the distributed and shared computing resources. Though the cloud computing paradigm holds its potential status in the field of distributed computing, cloud platforms are not yet to the attention of majority of the researchers and practitioners. More specifically, still the researchers and practitioners community has fragmented and imperfect knowledge on cloud computing principles and techniques. In this context, one of the primary motivations of the work presented in this paper is to reveal the versatile merits of cloud computing paradigm and hence the objective of this work is defined to bring out the remarkable significances of cloud computing paradigm through an application environment. In this work, a cloud computing model for software testing is developed.
An Achievable Rate for the MIMO Individual Channel
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of communicating over a multiple-input multiple-output (MIMO) real valued channel for which no mathematical model is specified, and achievable rates are given as a function of the channel input and output sequences known a-posteriori. This paper extends previous results regarding individual channels by presenting a rate function for the MIMO individual channel, and showing its achievability in a fixed transmission rate communication scenario.
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
Venue: arXiv cs.DS 2010
Year: 2010

We give the first algorithm for testing the feasibility of a system of sporadic real-time tasks on a set of identical processors, solving one major open problem in the area of multiprocessor real-time scheduling [S.K. Baruah and K. Pruhs, Journal of Scheduling, 2009]. We also investigate the related notion of schedulability and a notion that we call online feasibility. Finally, we show that discrete-time schedules are as powerful as continuous-time schedules, which answers another open question in the above mentioned survey.
Addressing the P2P Bootstrap Problem for Small Networks
Venue: arXiv cs.DC 2010
Year: 2010

P2P overlays provide a framework for building distributed applications consisting of few to many resources with features including self-configuration, scalability, and resilience to node failures. Such systems have been successfully adopted in large-scale services for content delivery networks, file sharing, and data storage. In small-scale systems, they can be useful to address privacy concerns and for network applications that lack dedicated servers. The bootstrap problem, finding an existing peer in the overlay, remains a challenge to enabling these services for small-scale P2P systems. In large networks, the solution to the bootstrap problem has been the use of dedicated services, though creating and maintaining these systems requires expertise and resources, which constrain their usefulness and make them unappealing for small-scale systems. This paper surveys and summarizes requirements that allow peers potentially constrained by network connectivity to bootstrap small-scale overlays through the use of existing public overlays. In order to support bootstrapping, a public overlay must support the following requirements: a method for reflection in order to obtain publicly reachable addresses, so peers behind network address translators and firewalls can receive incoming connection requests; communication relaying to share public addresses and communicate when direct communication is not feasible; and rendezvous for discovering remote peers, when the overlay lacks stable membership. After presenting a survey of various public overlays, we identify two overlays that match the requirements: XMPP overlays, such as Google Talk and Live Journal Talk, and Brunet, a structured overlay based upon Symphony. We present qualitative experiences with prototypes that demonstrate the ability to bootstrap small-scale private structured overlays from public Brunet or XMPP infrastructures.
Complexity Analysis of Balloon Drawing for Rooted Trees
Venue: arXiv cs.CG 2010
Year: 2010

In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of descendants associated with the node. Among various styles of tree drawings reported in the literature, the balloon drawing enjoys a desirable feature of displaying tree structures in a rather balanced fashion. For each internal node in a balloon drawing, the ray from the node to each of its children divides the wedge accommodating the subtree rooted at the child into two sub-wedges. Depending on whether the two sub-wedge angles are required to be identical or not, a balloon drawing can further be divided into two types: even sub-wedge and uneven sub-wedge types. In the most general case, for any internal node in the tree there are two dimensions of freedom that affect the quality of a balloon drawing: (1) altering the order in which the children of the node appear in the drawing, and (2) for the subtree rooted at each child of the node, flipping the two sub-wedges of the subtree. In this paper, we give a comprehensive complexity analysis for optimizing balloon drawings of rooted trees with respect to angular resolution, aspect ratio and standard deviation of angles under various drawing cases depending on whether the tree is of even or uneven sub-wedge type and whether (1) and (2) above are allowed. It turns out that some are NP-complete while others can be solved in polynomial time. We also derive approximation algorithms for those that are intractable in general.
A novel pseudo-random number generator based on discrete chaotic iterations
Venue: arXiv cs.CR 2010
Year: 2010

Security of information transmitted through the Internet, against passive or active attacks is an international concern. The use of a chaos-based pseudo-random bit sequence to make it unrecognizable by an intruder, is a field of research in full expansion. This mask of useful information by modulation or encryption is a fundamental part of the TLS Internet exchange protocol. In this paper, a new method using discrete chaotic iterations to generate pseudo-random numbers is presented. This pseudo-random number generator has successfully passed the NIST statistical test suite (NIST SP800-22). Security analysis shows its good characteristics. The application for secure image transmission through the Internet is proposed at the end of the paper.
Relay-Assisted Partial Packet Recovery with IDMA Method in CDMA Wireless Network
Venue: arXiv cs.IT 2010
Year: 2010

Automatic Repeat Request (ARQ) is an effective technique for reliable transmission of packets in wireless networks. In ARQ, however, only a few erroneous bits in a packet will cause the entire packet to be discarded at the receiver. In this case, it's wasteful to retransmit the correct bit in the received packet. The partial packet recovery only retransmits the unreliable decoded bits in order to increase the throughput of network. In addition, the cooperative transmission based on Interleave-division multiple-access (IDMA) can obtain diversity gains with multiple relays with different locations for multiple sources simultaneously. By exploring the diversity from the channel between relay and destination, we propose a relay-assisted partial packet recovery in CDMA wireless network to improve the performance of throughput. In the proposed scheme, asynchronous IDMA iterative chip-by-chip multiuser detection is utilized as a method of multiple partial recovery, which can be a complementarity in a current CDMA network. The confidence values' concept is applied to detect unreliable decoded bits. According to the result of unreliable decoded bits' position, we use a recursive algorithm based on cost evaluation to decide a feedback strategy. Then the feedback request with minimum cost can be obtained. The simulation results show that the performance of throughput can be significantly improved with our scheme, compared with traditional ARQ scheme. The upper bound with our scheme is provided in our simulation. Moreover, we show how relays' location affects the performance.
Enhancing Curriculum Acceptance among Students with E-learning 2.0
Venue: arXiv cs.CY 2010
Year: 2010

E-learning; enhanced by communicating and interacting is becoming increasingly accepted and this puts Web 2.0 at the center of the new educational technologies. E-Learning 2.0 emerges as an innovative method of online learning for its incorporation of Web 2.0 tools. For any academic study, the curriculum provides overview of intact learning area. The Curriculum provides overview to content of the Subject. Many institutions place student interaction as a priority of their online curriculum design. It is proved that interaction has a great effect on the students' involvement in learning and acceptance of Curriculum. Students are accepting curriculum that is designed by teacher; whereas E-learning 2.0 enabled Curriculum management system allows student to involve in learning activities. It works as a stimulus and increases their dedication to the Curriculum. While Institute adapts E-Learning 2.0 as Learning Management System, it also provides Social Networking services and provides direct and transparent interaction between students and teachers. This view of the e-Learning 2.0 shifts its focus from LMS to the students, equipping them, with the means to become ever more autonomous, accepting them to make use of these means in solving problems on their own initiative. Curriculum usage will empower student involvement and enhancing E-learning 2.0 spreading. This paper, analyzing implementation E-learning 2.0 for Curriculum management and discusses Opportunities & Challenges for Curriculum over Web 2.0.
Error Rates of Capacity-Achieving Codes Are Convex
Venue: arXiv cs.IT 2010
Year: 2010

Motivated by a wide-spread use of convex optimization techniques, convexity properties of bit error rate of the maximum likelihood detector operating in the AWGN channel are studied for arbitrary constellations and bit mappings, which also includes coding under maximum-likelihood decoding. Under this generic setting, the pairwise probability of error and bit error rate are shown to be convex functions of the SNR and noise power in the high SNR/low noise regime with explicitly-determined boundary. Any code, including capacity-achieving ones, whose decision regions include the hardened noise spheres (from the noise sphere hardening argument in the channel coding theorem) satisfies this high SNR requirement and thus has convex error rates in both SNR and noise power. We conjecture that all capacity-achieving codes have convex error rates.
Experimenting with Innate Immunity
Venue: arXiv cs.AI 2010
Year: 2010

In a previous paper the authors argued the case for incorporating ideas from innate immunity into artificial immune systems (AISs) and presented an outline for a conceptual framework for such systems. A number of key general properties observed in the biological innate and adaptive immune systems were highlighted, and how such properties might be instantiated in artificial systems was discussed in detail. The next logical step is to take these ideas and build a software system with which AISs with these properties can be implemented and experimentally evaluated. This paper reports on the results of that step - the libtissue system.
HMC: Verifying Functional Programs Using Abstract Interpreters
Venue: arXiv cs.PL 2010
Year: 2010

We present Hindley-Milner-Cousots (HMC), an algorithm that allows any interprocedural analysis for first-order imperative programs to be used to verify safety properties of typed higher-order functional programs. HMC works as follows. First, it uses the type structure of the functional program to generate a set of logical refinement constraints whose satisfaction implies the safety of the source program. Next, it transforms the logical refinement constraints into a simple first-order imperative program that is safe iff the constraints are satisfiable. Thus, in one swoop, HMC makes tools for invariant generation, e.g., based on abstract domains, predicate abstraction, counterexample-guided refinement, and Craig interpolation be directly applicable to verify safety properties of modern functional languages in a fully automatic manner. We have implemented HMC and describe preliminary experimental results using two imperative checkers -- ARMC and InterProc -- to verify OCaml programs. Thus, by composing type-based reasoning grounded in program syntax and state-based reasoning grounded in abstract interpretation, HMC opens the door to automatic verification of programs written in modern programming languages.
On the approximability of robust spanning tree problems
Venue: arXiv cs.CC 2010
Year: 2010

In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min-max, min-max regret and 2-stage min-max versions of the problem are discussed. The complexity and approximability of all these problems are explored. It is proved that the min-max and min-max regret versions with nonnegative edge costs are hard to approximate within $O(\log^{1-ε} n)$ for any $ε>0$ unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min-max problem cannot be approximated within $O(\log n)$ unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance ratio of $O(\log^2 n)$ for min-max and 2-stage min-max problems are also proposed.
Streaming Graph Computations with a Helpful Advisor
Venue: arXiv cs.DS 2010
Year: 2010

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such {\em annotation models} by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only a constant number of hash values are needed for single-pass algorithms given linear-sized annotations. We also obtain a protocol achieving \textit{optimal} tradeoffs between annotation length and memory usage for matrix-vector multiplication; this result contributes to a trend of recent research on numerical linear algebra in streaming models.
Computing Critical Pairs in 2-Dimensional Rewriting Systems
Venue: arXiv cs.FL 2010
Year: 2010

Rewriting systems on words are very useful in the study of monoids. In good cases, they give finite presentations of the monoids, allowing their manipulation by a computer. Even better, when the presentation is confluent and terminating, they provide one with a notion of canonical representative for the elements of the presented monoid. Polygraphs are a higher-dimensional generalization of this notion of presentation, from the setting of monoids to the much more general setting of n-categories. Here, we are interested in proving confluence for polygraphs presenting 2-categories, which can be seen as a generalization of term rewriting systems. For this purpose, we propose an adaptation of the usual algorithm for computing critical pairs. Interestingly, this framework is much richer than term rewriting systems and requires the elaboration of a new theoretical framework for representing critical pairs, based on contexts in compact 2-categories.
Secure Localization in Wireless Sensor Networks: A Survey
Venue: arXiv cs.CR 2010
Year: 2010

Wireless sensor networks (WSNs) have gained researchers' attention in the last several years. Small sensors powered by miniaturized microprocessors are capable of supporting several applications for civil and military domains. Determining the location of sensors is a basic and essential knowledge for most WSN algorithms and protocols including data tagging, routing, node identification, among others. This paper surveys the different algorithms that have been proposed to securely determine the location of a sensor node. By "secure", we mean that adversaries cannot easily affect the accuracy of the localized sensors. In other words, the localization algorithm must be robust under several attacks. We provide a taxonomy for classifying different secure localization schemes and describe possible attacks that can harm localization. In addition, we survey different secure localization schemes and show how they map to the proposed taxonomy. We also give a comparison between the different schemes, showing the attacks addressed by each.
CellSense: A Probabilistic RSSI-based GSM Positioning System
Venue: arXiv cs.NI 2010
Year: 2010

Context-aware applications have been gaining huge interest in the last few years. With cell phones becoming ubiquitous computing devices, cell phone localization has become an important research problem. In this paper, we present CellSense, a prob- abilistic RSSI-based fingerprinting location determina- tion system for GSM phones.We discuss the challenges of implementing a probabilistic fingerprinting local- ization technique in GSM networks and present the details of the CellSense system and how it addresses the challenges. To evaluate our proposed system, we implemented CellSense on Android-based phones. Re- sults for two different testbeds, representing urban and rural environments, show that CellSense provides at least 23.8% enhancement in accuracy in rural areas and at least 86.4% in urban areas compared to other RSSI-based GSMlocalization systems. This comes with a minimal increase in computational requirements. We also evaluate the effect of changing the different system parameters on the accuracy-complexity tradeoff.
Approximation Algorithms for Dominating Set in Disk Graphs
Venue: arXiv cs.CG 2010
Year: 2010

We consider the problem of finding a lowest cost dominating set in a given disk graph containing $n$ disks. The problem has been extensively studied on subclasses of disk graphs, yet the best known approximation for disk graphs has remained $O(\log n)$ -- a bound that is asymptotically no better than the general case. We improve the status quo in two ways: for the unweighted case, we show how to obtain a PTAS using the framework recently proposed (independently)by Mustafa and Ray [SoCG 09] and by Chan and Har-Peled [SoCG 09]; for the weighted case where each input disk has an associated rational weight with the objective of finding a minimum cost dominating set, we give a randomized algorithm that obtains a dominating set whose weight is within a factor $2^{O(\log^* n)}$ of a minimum cost solution, with high probability -- the technique follows the framework proposed recently by Varadarajan [STOC 10].
Citing for High Impact
Venue: arXiv cs.DL 2010
Year: 2010

The question of citation behavior has always intrigued scientists from various disciplines. While general citation patterns have been widely studied in the literature we develop the notion of citation projection graphs by investigating the citations among the publications that a given paper cites. We investigate how patterns of citations vary between various scientific disciplines and how such patterns reflect the scientific impact of the paper. We find that idiosyncratic citation patterns are characteristic for low impact papers; while narrow, discipline-focused citation patterns are common for medium impact papers. Our results show that crossing-community, or bridging citation patters are high risk and high reward since such patterns are characteristic for both low and high impact papers. Last, we observe that recently citation networks are trending toward more bridging and interdisciplinary forms.