OpenRaiser/Intern-Atlas huggingface dataset:
Beeping a Maximal Independent Set
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in O(log^3 n) time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in O(log^3 n) time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in O(log^2 n) time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in O(log^2 n) time.
Streaming algorithms for recognizing nearly well-parenthesized expressions
Venue: arXiv cs.CC 2012
Year: 2012

We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x' in 1-turn-Dyck2 such that x is obtained by flipping at most $k$ locations of x' using: - O(k log n) space, O(k log n) randomness, and poly(k log n) time per item and with error at most 1/poly(n). - O(k^{1+epsilon} + log n) space for every 0 <= epsilon <= 1, O(log n) randomness, O(polylog(n) + poly(k)) time per item, with error at most 1/8. Here, we also prove that any randomized one-pass algorithm that makes error at most k/n requires at least Omega(k log(n/k)) space to accept strings which are exactly k-away from strings in 1-turn-Dyck2 and to reject strings which are exactly (k+2)-away from strings in 1-turn-Dyck2. Since 1-turn-Dyck2 and the Hamming Distance problem are closely related we also obtain new upper and lower bounds for this problem. Dyck2 with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string x' in Dyck2 such that x is obtained from x' by changing (in some restricted manner) at most k positions using: - O(k log n + sqrt(n log n)) space, O(k log n) randomness, poly(k log n) time per element and with error at most 1/poly(n). - O(k^(1+epsilon)+ sqrt(n log n)) space for every 0 <= epsilon <= 1, O(log n) randomness, O(polylog(n) + poly(k)) time per element, with error at most 1/8.
Non-Termination Sets of Simple Linear Loops
Venue: arXiv cs.LO 2012
Year: 2012

A simple linear loop is a simple while loop with linear assignments and linear loop guards. If a simple linear loop has only two program variables, we give a complete algorithm for computing the set of all the inputs on which the loop does not terminate. For the case of more program variables, we show that the non-termination set cannot be described by Tarski formulae in general
3-Colourability of Dually Chordal Graphs in Linear Time
Venue: arXiv cs.DM 2012
Year: 2012

A graph G is dually chordal if there is a spanning tree T of G such that any maximal clique of G induces a subtree in T. This paper investigates the Colourability problem on dually chordal graphs. It will show that it is NP-complete in case of four colours and solvable in linear time with a simple algorithm in case of three colours. In addition, it will be shown that a dually chordal graph is 3-colourable if and only if it is perfect and has no clique of size four.
Examining Motivations behind Paper Usage in Academia
Venue: arXiv cs.HC 2012
Year: 2012

We carried out a qualitative study to identify the "missing pieces" in current computing devices and technologies that are preventing people from eliminating paper from their lives. Most of the existing literature has looked into the work practices of businesses, while a few have researched how high school and college students and teaching assistants at universities work with paper. We were specifically interested in analysing paper use for people in the research side of academia, and seeing how our results compare to existing work. We recruited and interviewed participants from academia to understand what kind of tasks they use paper for, what kind of tasks they use computing devices for and what motivates them to use these two media. We found that, despite having access to at least one personal computing device, the participants preferred to work with paper in many situations. This appears to be attributed to certain intrinsic qualities that paper has, such as open format, easy navigation, readability, and the aff?ordances these qualities provide. In order to eventually replace paper with devices, designers of new technology will have to successfully emulate these qualities.
Sparse Trace Norm Regularization
Venue: arXiv cs.LG 2012
Year: 2012

We study the problem of estimating multiple predictive functions from a dictionary of basis functions in the nonparametric regression setting. Our estimation scheme assumes that each predictive function can be estimated in the form of a linear combination of the basis functions. By assuming that the coefficient matrix admits a sparse low-rank structure, we formulate the function estimation problem as a convex program regularized by the trace norm and the $\ell_1$-norm simultaneously. We propose to solve the convex program using the accelerated gradient (AG) method and the alternating direction method of multipliers (ADMM) respectively; we also develop efficient algorithms to solve the key components in both AG and ADMM. In addition, we conduct theoretical analysis on the proposed function estimation scheme: we derive a key property of the optimal solution to the convex program; based on an assumption on the basis functions, we establish a performance bound of the proposed function estimation scheme (via the composite regularization). Simulation studies demonstrate the effectiveness and efficiency of the proposed algorithms.
Energy-Aware Task Partitioning on Heterogeneous Multiprocessor Platforms
Venue: arXiv cs.OS 2012
Year: 2012

Efficient task partitioning plays a crucial role in achieving high performance at multiprocessor plat forms. This paper addresses the problem of energy-aware static partitioning of periodic real-time tasks on heterogeneous multiprocessor platforms. A Particle Swarm Optimization variant based on Min-min technique for task partitioning is proposed. The proposed approach aims to minimize the overall energy consumption, meanwhile avoid deadline violations. An energy-aware cost function is proposed to be considered in the proposed approach. Extensive simulations and comparisons are conducted in order to validate the effectiveness of the proposed technique. The achieved results demonstrate that the proposed partitioning scheme significantly surpasses previous approaches in terms of both number of iterations and energy savings.
Congestion Games on Weighted Directed Graphs, with Applications to Spectrum Sharing
Venue: arXiv cs.NI 2012
Year: 2012

With the advance of complex large-scale networks, it is becoming increasingly important to understand how selfish and spatially distributed individuals will share network resources without centralized coordinations. In this paper, we introduce the graphical congestion game with weighted edges (GCGWE) as a general theoretical model to study this problem. In GCGWE, we view the players as vertices in a weighted graph. The amount of negative impact (e.g. congestion) caused by two close-by players to each other is determined by the weight of the edge linking them. The GCGWE unifies and significantly generalizes several simpler models considered in the previous literature, and is well suited for modeling a wide range of networking scenarios. One good example is to use the GCGWE to model spectrum sharing in wireless networks, where we can properly define the edge weights and payoff functions to capture the rather complicated interference relationship between wireless nodes. By identifying which GCGWEs possess pure Nash equilibria and the very desirable finite improvement property, we gain insight into when spatially distributed wireless nodes will be able to self-organize into a mutually acceptable resource allocation. We also consider the efficiency of the pure Nash equilibria, and the computational complexity of finding them.
Simultaneous Embeddings with Vertices Mapping to Pre-Specified Points
Venue: arXiv cs.CG 2012
Year: 2012

We discuss the problem of embedding graphs in the plane with restrictions on the vertex mapping. In particular, we introduce a technique for drawing planar graphs with a fixed vertex mapping that bounds the number of times edges bend. An immediate consequence of this technique is that any planar graph can be drawn with a fixed vertex mapping so that edges map to piecewise linear curves with at most $3n + O(1)$ bends each. By considering uniformly random planar graphs, we show that $2n + O(1)$ bends per edge is sufficient on average. To further utilize our technique, we consider simultaneous embeddings of $k$ uniformly random planar graphs with vertices mapping to a fixed, common point set. We explain how to achieve such a drawing so that edges map to piecewise linear curves with $O(n^{1-1/k})$ bends each, which holds with overwhelming probability. This result improves upon the previously best known result of O(n) bends per edge for the case where $k \geq 2$. Moreover, we give a lower bound on the number of bends that matches our upper bound, proving our results are optimal.
Sequence-Based Control for Networked Control Systems Based on Virtual Control Inputs
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, we address the problem of controlling a system over an unreliable connection that is affected by time-varying delays and randomly occurring packet losses. A novel sequence-based approach is proposed that extends a given controller designed without consideration of the network-induced disturbances. Its key idea is to model the unknown future control inputs by random variables, the so-called virtual control inputs, which are characterized by discrete probability density functions. Subject to this probabilistic description, the actual sequence of future control inputs is determined and transmitted to the actuator. The high performance of the proposed approach is demonstrated by means of Monte Carlo simulation runs with an inverted pendulum on a cart and by a detailed comparison to standard NCS approaches.
Synergy-based Hand Pose Sensing: Reconstruction Enhancement
Venue: arXiv cs.RO 2012
Year: 2012

Low-cost sensing gloves for reconstruction posture provide measurements which are limited under several regards. They are generated through an imperfectly known model, are subject to noise, and may be less than the number of Degrees of Freedom (DoFs) of the hand. Under these conditions, direct reconstruction of the hand posture is an ill-posed problem, and performance can be very poor. This paper examines the problem of estimating the posture of a human hand using(low-cost) sensing gloves, and how to improve their performance by exploiting the knowledge on how humans most frequently use their hands. To increase the accuracy of pose reconstruction without modifying the glove hardware - hence basically at no extra cost - we propose to collect, organize, and exploit information on the probabilistic distribution of human hand poses in common tasks. We discuss how a database of such an a priori information can be built, represented in a hierarchy of correlation patterns or postural synergies, and fused with glove data in a consistent way, so as to provide a good hand pose reconstruction in spite of insufficient and inaccurate sensing data. Simulations and experiments on a low-cost glove are reported which demonstrate the effectiveness of the proposed techniques.
O(1) Delta Component Computation Technique for the Quadratic Assignment Problem
Venue: arXiv cs.DS 2012
Year: 2012

The paper describes a novel technique that allows to reduce by half the number of delta values that were required to be computed with complexity O(N) in most of the heuristics for the quadratic assignment problem. Using the correlation between the old and new delta values, obtained in this work, a new formula of complexity O(1) is proposed. Found result leads up to 25% performance increase in such well-known algorithms as Robust Tabu Search and others based on it.
The COMICS Tool - Computing Minimal Counterexamples for Discrete-time Markov Chains
Venue: arXiv cs.SE 2012
Year: 2012

This report presents the tool COMICS, which performs model checking and generates counterexamples for DTMCs. For an input DTMC, COMICS computes an abstract system that carries the model checking information and uses this result to compute a critical subsystem, which induces a counterexample. This abstract subsystem can be refined and concretized hierarchically. The tool comes with a command-line version as well as a graphical user interface that allows the user to interactively influence the refinement process of the counterexample.
Secure FSM- based arithmetic codes
Venue: arXiv cs.CR 2012
Year: 2012

Recently, arithmetic coding has attracted the attention of many scholars because of its high compression capability. Accordingly, in this paper a method which adds secrecy to this well-known source code is proposed. Finite state arithmetic code (FSAC) is used as source code to add security. Its finite state machine (FSM) characteristic is exploited to insert some random jumps during source coding process. In addition, a Huffman code is designed for each state to make decoding possible even in jumps. Being Prefix free, Huffman codes are useful in tracking correct states for an authorized user when s/he decodes with correct symmetric pseudo random key. The robustness of our proposed scheme is further reinforced by adding another extra uncertainty by swapping outputs of Huffman codes in each state. Several test images are used for inspecting the validity of the proposed Huffman Finite State Arithmetic Coding (HFSAC). The results of several experimental, key space analyses, statistical analysis, key sensitivity and plaintext sensitivity tests show that HFSAC with a little effect on compression efficiency for image cryptosystem provides an efficient and secure way for real-time image encryption and transmission.
Possibilistic Pertinence Feedback and Semantic Networks for Goal's Extraction
Venue: arXiv cs.AI 2012
Year: 2012

Pertinence Feedback is a technique that enables a user to interactively express his information requirement by modifying his original query formulation with further information. This information is provided by explicitly confirming the pertinent of some indicating objects and/or goals extracted by the system. Obviously the user cannot mark objects and/or goals as pertinent until some are extracted, so the first search has to be initiated by a query and the initial query specification has to be good enough to pick out some pertinent objects and/or goals from the Semantic Network. In this paper we present a short survey of fuzzy and Semantic approaches to Knowledge Extraction. The goal of such approaches is to define flexible Knowledge Extraction Systems able to deal with the inherent vagueness and uncertainty of the Extraction process. It has long been recognised that interactivity improves the effectiveness of Knowledge Extraction systems. Novice user's queries are the most natural and interactive medium of communication and recent progress in recognition is making it possible to build systems that interact with the user. However, given the typical novice user's queries submitted to Knowledge Extraction Systems, it is easy to imagine that the effects of goal recognition errors in novice user's queries must be severely destructive on the system's effectiveness. The experimental work reported in this paper shows that the use of possibility theory in classical Knowledge Extraction techniques for novice user's query processing is more robust than the use of the probability theory. Moreover, both possibilistic and probabilistic pertinence feedback can be effectively employed to improve the effectiveness of novice user's query processing.
A Cross-Layer Design Based on Geographic Information for Cooperative Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

Most of geographic routing approaches in wireless ad hoc and sensor networks do not take into consideration the medium access control (MAC) and physical layers when designing a routing protocol. In this paper, we focus on a cross-layer framework design that exploits the synergies between network, MAC, and physical layers. In the proposed CoopGeo, we use a beaconless forwarding scheme where the next hop is selected through a contention process based on the geographic position of nodes. We optimize this Network-MAC layer interaction using a cooperative relaying technique with a relay selection scheme also based on geographic information in order to improve the system performance in terms of reliability.
An Informed Model of Personal Information Release in Social Networking Sites
Venue: arXiv cs.SI 2012
Year: 2012

The emergence of online social networks and the growing popularity of digital communication has resulted in an increasingly amount of information about individuals available on the Internet. Social network users are given the freedom to create complex digital identities, and enrich them with truthful or even fake personal information. However, this freedom has led to serious security and privacy incidents, due to the role users' identities play in establishing social and privacy settings. In this paper, we take a step toward a better understanding of online information exposure. Based on the detailed analysis of a sample of real-world data, we develop a deception model for online users. The model uses a game theoretic approach to characterizing a user's willingness to release, withhold or lie about information depending on the behavior of individuals within the user's circle of friends. In the model, we take into account both the heterogeneous nature of users and their different attitudes, as well as the different types of information they may expose online.
A Machine Learning Approach For Opinion Holder Extraction In Arabic Language
Venue: arXiv cs.IR 2012
Year: 2012

Opinion mining aims at extracting useful subjective information from reliable amounts of text. Opinion mining holder recognition is a task that has not been considered yet in Arabic Language. This task essentially requires deep understanding of clauses structures. Unfortunately, the lack of a robust, publicly available, Arabic parser further complicates the research. This paper presents a leading research for the opinion holder extraction in Arabic news independent from any lexical parsers. We investigate constructing a comprehensive feature set to compensate the lack of parsing structural outcomes. The proposed feature set is tuned from English previous works coupled with our proposed semantic field and named entities features. Our feature analysis is based on Conditional Random Fields (CRF) and semi-supervised pattern recognition techniques. Different research models are evaluated via cross-validation experiments achieving 54.03 F-measure. We publicly release our own research outcome corpus and lexicon for opinion mining community to encourage further research.
Hedge detection as a lens on framing in the GMO debates: A position paper
Venue: arXiv cs.CL 2012
Year: 2012

Understanding the ways in which participants in public discussions frame their arguments is important in understanding how public opinion is formed. In this paper, we adopt the position that it is time for more computationally-oriented research on problems involving framing. In the interests of furthering that goal, we propose the following specific, interesting and, we believe, relatively accessible question: In the controversy regarding the use of genetically-modified organisms (GMOs) in agriculture, do pro- and anti-GMO articles differ in whether they choose to adopt a "scientific" tone? Prior work on the rhetoric and sociology of science suggests that hedging may distinguish popular-science text from text written by professional scientists for their colleagues. We propose a detailed approach to studying whether hedge detection can be used to understanding scientific framing in the GMO debates, and provide corpora to facilitate this study. Some of our preliminary analyses suggest that hedges occur less frequently in scientific discourse than in popular text, a finding that contradicts prior assertions in the literature. We hope that our initial work and data will encourage others to pursue this promising line of inquiry.
Power Grid Vulnerability to Geographically Correlated Failures - Analysis and Control Implications
Venue: arXiv cs.SY 2012
Year: 2012

We consider power line outages in the transmission system of the power grid, and specifically those caused by a natural disaster or a large scale physical attack. In the transmission system, an outage of a line may lead to overload on other lines, thereby eventually leading to their outage. While such cascading failures have been studied before, our focus is on cascading failures that follow an outage of several lines in the same geographical area. We provide an analytical model of such failures, investigate the model's properties, and show that it differs from other models used to analyze cascades in the power grid (e.g., epidemic/percolation-based models). We then show how to identify the most vulnerable locations in the grid and perform extensive numerical experiments with real grid data to investigate the various effects of geographically correlated outages and the resulting cascades. These results allow us to gain insights into the relationships between various parameters and performance metrics, such as the size of the original event, the final number of connected components, and the fraction of demand (load) satisfied after the cascade. In particular, we focus on the timing and nature of optimal control actions used to reduce the impact of a cascade, in real time. We also compare results obtained by our model to the results of a real cascade that occurred during a major blackout in the San Diego area on Sept. 2011. The analysis and results presented in this paper will have implications both on the design of new power grids and on identifying the locations for shielding, strengthening, and monitoring efforts in grid upgrades.