OpenRaiser/Intern-Atlas huggingface dataset:
An Unconditionally Secure Key Management Scheme for Large-Scale Heterogeneous Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Key establishment in sensor networks becomes a challenging problem because of the resource limitations of the sensors and also due to vulnerability to physical capture of the sensor nodes. In this paper, we propose an unconditionally secure probabilistic group-based key pre-distribution scheme for a heterogeneous wireless sensor network. The proposed scheme always guarantees that no matter how many sensor nodes are compromised, the non-compromised nodes can still communicate with 100% secrecy, i.e., the proposed scheme is always unconditionally secure against node capture attacks. Moreover, it provides significantly better trade-off between communication overhead, computational overhead, network connectivity and security against node capture as compared to the existing key pre-distribution schemes. It also supports dynamic node addition after the initial deployment of the nodes in the network.
Arrangement Computation for Planar Algebraic Curves
Venue: arXiv cs.SC 2011
Year: 2011

We present a new certified and complete algorithm to compute arrangements of real planar algebraic curves. Our algorithm provides a geometric-topological analysis of the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition of the plane. Compared to previous approaches, we improve in two main aspects: Firstly, we significantly reduce the amount of exact operations, that is, our algorithms only uses resultant and gcd as purely symbolic operations. Secondly, we introduce a new hybrid method in the lifting step of our algorithm which combines the usage of a certified numerical complex root solver and information derived from the resultant computation. Additionally, we never consider any coordinate transformation and the output is also given with respect to the initial coordinate system. We implemented our algorithm as a prototypical package of the C++-library CGAL. Our implementation exploits graphics hardware to expedite the resultant and gcd computation. We also compared our implementation with the current reference implementation, that is, CGAL's curve analysis and arrangement for algebraic curves. For various series of challenging instances, our experiments show that the new implementation outperforms the existing one.
Robust Spectrum Sharing via Worst Case Approach
Venue: arXiv cs.NI 2011
Year: 2011

This paper considers non-cooperative and fully-distributed power-allocation for secondary-users (SUs) in spectrum-sharing environments when normalized-interference to each secondary-user is uncertain. We model each uncertain parameter by the sum of its nominal (estimated) value and a bounded additive error in a convex set, and show that the allocated power always converges to its equilibrium, called robust Nash equilibrium (RNE). In the case of a bounded and symmetric uncertainty set, we show that the power allocation problem for each SU is simplified, and can be solved in a distributed manner. We derive the conditions for RNE's uniqueness and for convergence of the distributed algorithm; and show that the total throughput (social utility) is less than that at NE when RNE is unique. We also show that for multiple RNEs, the the social utility may be higher at a RNE as compared to that at the corresponding NE, and demonstrate that this is caused by SUs' orthogonal utilization of bandwidth for increasing the social utility. Simulations confirm our analysis.
Mining User Comment Activity for Detecting Forum Spammers in YouTube
Venue: arXiv cs.IR 2011
Year: 2011

Research shows that comment spamming (comments which are unsolicited, unrelated, abusive, hateful, commercial advertisements etc) in online discussion forums has become a common phenomenon in Web 2.0 applications and there is a strong need to counter or combat comment spamming. We present a method to automatically detect comment spammer in YouTube (largest and a popular video sharing website) forums. The proposed technique is based on mining comment activity log of a user and extracting patterns (such as time interval between subsequent comments, presence of exactly same comment across multiple unrelated videos) indicating spam behavior. We perform empirical analysis on data crawled from YouTube and demonstrate that the proposed method is effective for the task of comment spammer detection.
Termination Proofs in the Dependency Pair Framework May Induce Multiple Recursive Derivational Complexity
Venue: arXiv cs.LO 2011
Year: 2011

We study the derivational complexity of rewrite systems whose termination is provable in the dependency pair framework using the processors for reduction pairs, dependency graphs, or the subterm criterion. We show that the derivational complexity of such systems is bounded by a multiple recursive function, provided the derivational complexity induced by the employed base techniques is at most multiple recursive. Moreover we show that this upper bound is tight.
A protocol for a message system for the tiles of the heptagrid, in the hyperbolic plane
Venue: arXiv cs.DM 2011
Year: 2011

This paper introduces a communication system for the tiles of the heptagrid, a tiling of the hyperbolic plane. The method can be extended to other tilings of this plane. The paper focuses on an actual implementation at the programming stage with a short account of two experiments.
On the Correspondence between Display Postulates and Deep Inference in Nested Sequent Calculi for Tense Logics
Venue: arXiv cs.LO 2011
Year: 2011

We consider two styles of proof calculi for a family of tense logics, presented in a formalism based on nested sequents. A nested sequent can be seen as a tree of traditional single-sided sequents. Our first style of calculi is what we call "shallow calculi", where inference rules are only applied at the root node in a nested sequent. Our shallow calculi are extensions of Kashima's calculus for tense logic and share an essential characteristic with display calculi, namely, the presence of structural rules called "display postulates". Shallow calculi enjoy a simple cut elimination procedure, but are unsuitable for proof search due to the presence of display postulates and other structural rules. The second style of calculi uses deep-inference, whereby inference rules can be applied at any node in a nested sequent. We show that, for a range of extensions of tense logic, the two styles of calculi are equivalent, and there is a natural proof theoretic correspondence between display postulates and deep inference. The deep inference calculi enjoy the subformula property and have no display postulates or other structural rules, making them a better framework for proof search.
Nobody but You: Sensor Selection for Voltage Regulation in Smart Grid
Venue: arXiv cs.SY 2011
Year: 2011

The increasing availability of distributed energy resources (DERs) and sensors in smart grid, as well as overlaying communication network, provides substantial potential benefits for improving the power system's reliability. In this paper, the problem of sensor selection is studied for the MAC layer design of wireless sensor networks for regulating the voltages in smart grid. The framework of hybrid dynamical system is proposed, using Kalman filter for voltage state estimation and LQR feedback control for voltage adjustment. The approach to obtain the optimal sensor selection sequence is studied. A sub- optimal sequence is obtained by applying the sliding window algorithm. Simulation results show that the proposed sensor selection strategy achieves a 40% performance gain over the baseline algorithm of the round-robin sensor polling.
Triangular Dynamic Architecture for Distributed Computing in a LAN Environment
Venue: arXiv cs.DC 2011
Year: 2011

A computationally intensive large job, granulized to concurrent pieces and operating in a dynamic environment should reduce the total processing time. However, distributing jobs across a networked environment is a tedious and difficult task. Job distribution in a Local Area Network based on Triangular Dynamic Architecture (TDA) is a mechanism that establishes a dynamic environment for job distribution, load balancing and distributed processing with minimum interaction from the user. This paper introduces TDA and discusses its architecture and shows the benefits gained by utilizing such architecture in a distributed computing environment.
The Space Complexity of Long-lived and One-Shot Timestamp Implementations
Venue: arXiv cs.DC 2011
Year: 2011

This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary universe. Ellen, Fatourou and Ruppert (2008) showed that sqrt{n}/2-O(1) registers are required for any obstruction-free implementation of long-lived timestamp systems from atomic registers (meaning processors can repeatedly get timestamps). We improve this existing lower bound in two ways. First we establish a lower bound of n/6 - O(1) registers for the obstruction-free long-lived timestamp problem. Previous such linear lower bounds were only known for constrained versions of the timestamp problem. This bound is asymptotically tight; Ellen, Fatourou and Ruppert (2008) constructed a wait-free algorithm that uses n-1 registers. Second we show that sqrt{n} - O(1) registers are required for any obstruction-free implementation of one-shot timestamp systems(meaning each processor can get a timestamp at most once). We show that this bound is also asymptotically tight by providing a wait-free one-shot timestamp system that uses fewer than 2 sqrt{n} registers, thus establishing a space complexity gap between one-shot and long-lived timestamp systems.
Multi-path Routing Metrics for Reliable Wireless Mesh Routing Topologies
Venue: arXiv cs.NI 2011
Year: 2011

Several emerging classes of applications that run over wireless networks have a need for mathematical models and tools to systematically characterize the reliability of the network. We propose two metrics for measuring the reliability of wireless mesh routing topologies, one for flooding and one for unicast routing. The Flooding Path Probability (FPP) metric measures the end-to-end packet delivery probability when each node broadcasts a packet after hearing from all its upstream neighbors. The Unicast Retransmission Flow (URF) metric measures the end-to-end packet delivery probability when a relay node retransmits a unicast packet on its outgoing links until it receives an acknowledgement or it tries all the links. Both metrics rely on specific packet forwarding models, rather than heuristics, to derive explicit expressions of the end-to-end packet delivery probability from individual link probabilities and the underlying connectivity graph. We also propose a distributed, greedy algorithm that uses the URF metric to construct a reliable routing topology. This algorithm constructs a Directed Acyclic Graph (DAG) from a weighted, undirected connectivity graph, where each link is weighted by its success probability. The algorithm uses a vector of decreasing reliability thresholds to coordinate when nodes can join the routing topology. Simulations demonstrate that, on average, this algorithm constructs a more reliable topology than the usual minimum hop DAG.
LIFO-search on digraphs: A searching game for cycle-rank
Venue: arXiv cs.DM 2011
Year: 2011

We consider the extension of the last-in-first-out graph searching game of Giannopoulou and Thilikos to digraphs. We show that all common variations of the game require the same number of searchers, and the minimal number of searchers required is one more than the cycle-rank of the digraph. We also obtain a tight duality theorem, giving a precise min-max characterization of obstructions for cycle-rank.
Interference, Cooperation and Connectivity - A Degrees of Freedom Perspective
Venue: arXiv cs.IT 2011
Year: 2011

We explore the interplay between interference, cooperation and connectivity in heterogeneous wireless interference networks. Specifically, we consider a 4-user locally-connected interference network with pairwise clustered decoding and show that its degrees of freedom (DoF) are bounded above by 12/5. Interestingly, when compared to the corresponding fully connected setting which is known to have 8/3 DoF, the locally connected network is only missing interference-carrying links, but still has lower DoF, i.e., eliminating these interference-carrying links reduces the DoF. The 12/5 DoF outer bound is obtained through a novel approach that translates insights from interference alignment over linear vector spaces into corresponding sub-modularity relationships between entropy functions.
The weak password problem: chaos, criticality, and encrypted p-CAPTCHAs
Venue: arXiv cs.CR 2011
Year: 2011

Vulnerabilities related to weak passwords are a pressing global economic and security issue. We report a novel, simple, and effective approach to address the weak password problem. Building upon chaotic dynamics, criticality at phase transitions, CAPTCHA recognition, and computational round-off errors we design an algorithm that strengthens security of passwords. The core idea of our method is to split a long and secure password into two components. The first component is memorized by the user. The second component is transformed into a CAPTCHA image and then protected using evolution of a two-dimensional dynamical system close to a phase transition, in such a way that standard brute-force attacks become ineffective. We expect our approach to have wide applications for authentication and encryption technologies.
Ergodic Transmission Capacity of Wireless Ad Hoc Networks with Interference Management
Venue: arXiv cs.IT 2011
Year: 2011

Most work on wireless network throughput ignores the temporal correlation inherent to wireless channels because it degrades tractability. To better model and quantify the temporal variations of wireless network throughput, this paper introduces a metric termed ergodic transmission capacity (ETC), which includes spatial and temporal ergodicity. All transmitters in the network form a homogeneous Poisson point process and all channels are modeled by a finite state Markov chain. The bounds on outage probability and ETC are characterized, and their scaling behaviors for a sparse and dense network are discussed. From these results, we show that the ETC can be characterized by the inner product of the channel-state related vector and the invariant probability vector of the Markov chain. This indicates that channel-aware opportunistic transmission does not always increase ETC. Finally, we look at outage probability with interference management from a stochastic geometry point of view. The improved bounds on outage probability and ETC due to interference management are characterized and they provide some useful insights on how to effectively manage interference in sparse and dense networks.
A Doubly Exponentially Crumbled Cake
Venue: arXiv cs.CG 2011
Year: 2011

We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjoint interiors, each of them having a point of P as the lower left corner; Alice keeps the rest. It has been conjectured that Bob can always secure at least half of the cake. This remains unsettled, and it is not even known whether Bob can get any positive fraction independent of n. We prove that if Alice can force Bob's share to tend to zero, then she must use very many points; namely, to prevent Bob from gaining more than 1/r of the cake, she needs at least 2^{2^{Ω(r)}} points.
Probabilistic Operational Semantics for the Lambda Calculus
Venue: arXiv cs.LO 2011
Year: 2011

Probabilistic operational semantics for a nondeterministic extension of pure lambda calculus is studied. In this semantics, a term evaluates to a (finite or infinite) distribution of values. Small-step and big-step semantics are both inductively and coinductively defined. Moreover, small-step and big-step semantics are shown to produce identical outcomes, both in call-by- value and in call-by-name. Plotkin's CPS translation is extended to accommodate the choice operator and shown correct with respect to the operational semantics. Finally, the expressive power of the obtained system is studied: the calculus is shown to be sound and complete with respect to computable probability distributions.
Recursive double-size fixed precision arithmetic
Venue: arXiv cs.CR 2011
Year: 2011

This work is a part of the SHIVA (Secured Hardware Immune Versatile Architecture) project whose purpose is to provide a programmable and reconfigurable hardware module with high level of security. We propose a recursive double-size fixed precision arithmetic called RecInt. Our work can be split in two parts. First we developped a C++ software library with performances comparable to GMP ones. Secondly our simple representation of the integers allows an implementation on FPGA. Our idea is to consider sizes that are a power of 2 and to apply doubling techniques to implement them efficiently: we design a recursive data structure where integers of size 2^k, for k>k0 can be stored as two integers of size 2^{k-1}. Obviously for k<=k0 we use machine arithmetic instead (k0 depending on the architecture).
Ludics with repetitions (Exponentials, Interactive types and Completeness)
Venue: arXiv cs.LO 2011
Year: 2011

Ludics is peculiar in the panorama of game semantics: we first have the definition of interaction-composition and then we have semantical types, as a set of strategies which "behave well" and react in the same way to a set of tests. The semantical types which are interpretations of logical formulas enjoy a fundamental property, called internal completeness, which characterizes ludics and sets it apart also from realizability. Internal completeness entails standard full completeness as a consequence. A growing body of work start to explore the potential of this specific interactive approach. However, ludics has some limitations, which are consequence of the fact that in the original formulation, strategies are abstractions of MALL proofs. On one side, no repetitions are allowed. On the other side, the proofs tend to rely on the very specific properties of the MALL proof-like strategies, making it difficult to transfer the approach to semantical types into different settings. In this paper, we provide an extension of ludics which allows repetitions and show that one can still have interactive types and internal completeness. From this, we obtain full completeness w.r.t. a polarized version of MELL. In our extension, we use less properties than in the original formulation, which we believe is of independent interest. We hope this may open the way to applications of ludics approach to larger domains and different settings.
Computing Optimal Coverability Costs in Priced Timed Petri Nets
Venue: arXiv cs.LO 2011
Year: 2011

We consider timed Petri nets, i.e., unbounded Petri nets where each token carries a real-valued clock. Transition arcs are labeled with time intervals, which specify constraints on the ages of tokens. Our cost model assigns token storage costs per time unit to places, and firing costs to transitions. We study the cost to reach a given control-state. In general, a cost-optimal run may not exist. However, we show that the infimum of the costs is computable.
Online and Batch Learning Algorithms for Data with Missing Features
Venue: arXiv cs.LG 2011
Year: 2011

We introduce new online and batch algorithms that are robust to data with missing features, a situation that arises in many practical applications. In the online setup, we allow for the comparison hypothesis to change as a function of the subset of features that is observed on any given round, extending the standard setting where the comparison hypothesis is fixed throughout. In the batch setup, we present a convex relation of a non-convex problem to jointly estimate an imputation function, used to fill in the values of missing features, along with the classification hypothesis. We prove regret bounds in the online setting and Rademacher complexity bounds for the batch i.i.d. setting. The algorithms are tested on several UCI datasets, showing superior performance over baselines.
Modeling network technology deployment rates with different network models
Venue: arXiv cs.NI 2011
Year: 2011

To understand the factors that encourage the deployment of a new networking technology, we must be able to model how such technology gets deployed. We investigate how network structure influences deployment with a simple deployment model and different network models through computer simulations. The results indicate that a realistic model of networking technology deployment should take network structure into account.
A framework of motion capture system based human behaviours simulation for ergonomic analysis
Venue: arXiv cs.RO 2011
Year: 2011

With the increasing of computer capabilities, Computer aided ergonomics (CAE) offers new possibilities to integrate conventional ergonomic knowledge and to develop new methods into the work design process. As mentioned in [1], different approaches have been developed to enhance the efficiency of the ergonomic evaluation. Ergonomic expert systems, ergonomic oriented information systems, numerical models of human, etc. have been implemented in numerical ergonomic software. Until now, there are ergonomic software tools available, such as Jack, Ergoman, Delmia Human, 3DSSPP, and Santos, etc. [2-4]. The main functions of these tools are posture analysis and posture prediction. In the visualization part, Jack and 3DSSPP produce results to visualize virtual human tasks in 3-dimensional, but without realistic physical properties. Nowadays, with the development of computer technology, the simulation of physical world is paid more attention. Physical engines [5] are used more and more in computer game (CG) field. The advantage of physical engine is the nature physical world environment simulation. The purpose of our research is to use the CG technology to create a virtual environment with physical properties for ergonomic analysis of virtual human.
Factorised Representations of Query Results
Venue: arXiv cs.DB 2011
Year: 2011

Query tractability has been traditionally defined as a function of input database and query sizes, or of both input and output sizes, where the query result is represented as a bag of tuples. In this report, we introduce a framework that allows to investigate tractability beyond this setting. The key insight is that, although the cardinality of a query result can be exponential, its structure can be very regular and thus factorisable into a nested representation whose size is only polynomial in the size of both the input database and query. For a given query result, there may be several equivalent representations, and we quantify the regularity of the result by its readability, which is the minimum over all its representations of the maximum number of occurrences of any tuple in that representation. We give a characterisation of select-project-join queries based on the bounds on readability of their results for any input database. We complement it with an algorithm that can find asymptotically optimal upper bounds and corresponding factorised representations.
How to make the most of a shared meal: plan the last bite first
Venue: arXiv cs.GT 2011
Year: 2011

If you are sharing a meal with a companion, how best to make sure you get your favourite mouthfuls? Ethiopian Dinner is a game in which two players take turns eating morsels from a common plate. Each morsel comes with a pair of utility values measuring its tastiness to the two players. Kohler and Chandrasekaharan discovered a good strategy -- a subgame perfect equilibrium, to be exact -- for this game. We give a new visual proof of their result. The players arrive at the equilibrium by figuring out their last move first and working backward. We conclude that it's never too early to start thinking about dessert.