OpenRaiser/Intern-Atlas huggingface dataset:
Teaching Wireless Sensor Networks: An Holistic Approach Bridging Theory and Practice at the Master Level
Venue: arXiv cs.CY 2013
Year: 2013

Wireless Sensor Networks (WSNs) are a new technology that has received a substantial attention from several academic research fields in the last years. There are many applications of WSNs, including environmental monitoring, industrial automation, intelligent transportation systems, healthcare and wellbeing, smart energy, to mention a few. Courses have been introduced both at the PhD and at the Master levels. However, these existing courses focus on particular aspects of WSNs (Networking, or Signal Processing, or Embedded Software), whereas WSNs encompass disciplines traditionally separated in Electrical Engineering and Computer Sciences. This paper gives two original contributions: the essential knowledge that should be brought in a WSNs course is characterized, and a course structure with an harmonious holistic approach is proposed. A method based on both theory and experiments is illustrated for the design of this course, whereby the students have hands-on to implement, understand, and develop in practice the implications of theoretical concepts. Theory and applications are thus considered all together. Ultimately, the objective of this paper is to design a new course, to use innovative hands-on experiments to illustrate the theoretical concepts in the course, to show that theoretical aspects are essential for the solution of real-life engineering WSNs problems, and finally to create a fun and interesting teaching and learning environments for WSNs.
On QBF Proofs and Preprocessing
Venue: arXiv cs.LO 2013
Year: 2013

QBFs (quantified boolean formulas), which are a superset of propositional formulas, provide a canonical representation for PSPACE problems. To overcome the inherent complexity of QBF, significant effort has been invested in developing QBF solvers as well as the underlying proof systems. At the same time, formula preprocessing is crucial for the application of QBF solvers. This paper focuses on a missing link in currently-available technology: How to obtain a certificate (e.g. proof) for a formula that had been preprocessed before it was given to a solver? The paper targets a suite of commonly-used preprocessing techniques and shows how to reconstruct certificates for them. On the negative side, the paper discusses certain limitations of the currently-used proof systems in the light of preprocessing. The presented techniques were implemented and evaluated in the state-of-the-art QBF preprocessor bloqqer.
All Your Location are Belong to Us: Breaking Mobile Social Networks for Automated User Location Tracking
Venue: arXiv cs.SI 2013
Year: 2013

Many popular location-based social networks (LBSNs) support built-in location-based social discovery with hundreds of millions of users around the world. While user (near) realtime geographical information is essential to enable location-based social discovery in LBSNs, the importance of user location privacy has also been recognized by leading real-world LBSNs. To protect user's exact geographical location from being exposed, a number of location protection approaches have been adopted by the industry so that only relative location information are publicly disclosed. These techniques are assumed to be secure and are exercised on the daily base. In this paper, we question the safety of these location-obfuscation techniques used by existing LBSNs. We show, for the first time, through real world attacks that they can all be easily destroyed by an attacker with the capability of no more than a regular LBSN user. In particular, by manipulating location information fed to LBSN client app, an ill-intended regular user can easily deduce the exact location information by running LBSN apps as location oracle and performing a series of attacking strategies. We develop an automated user location tracking system and test it on the most popular LBSNs including Wechat, Skout and Momo. We demonstrate its effectiveness and efficiency via a 3 week real-world experiment with 30 volunteers. Our evaluation results show that we could geo-locate a target with high accuracy and can readily recover users' Top 5 locations. We also propose to use grid reference system and location classification to mitigate the attacks. Our work shows that the current industrial best practices on user location privacy protection are completely broken, and it is critical to address this immediate threat.
Traveling Trends: Social Butterflies or Frequent Fliers?
Venue: arXiv cs.SI 2013
Year: 2013

Trending topics are the online conversations that grab collective attention on social media. They are continually changing and often reflect exogenous events that happen in the real world. Trends are localized in space and time as they are driven by activity in specific geographic areas that act as sources of traffic and information flow. Taken independently, trends and geography have been discussed in recent literature on online social media; although, so far, little has been done to characterize the relation between trends and geography. Here we investigate more than eleven thousand topics that trended on Twitter in 63 main US locations during a period of 50 days in 2013. This data allows us to study the origins and pathways of trends, how they compete for popularity at the local level to emerge as winners at the country level, and what dynamics underlie their production and consumption in different geographic areas. We identify two main classes of trending topics: those that surface locally, coinciding with three different geographic clusters (East coast, Midwest and Southwest); and those that emerge globally from several metropolitan areas, coinciding with the major air traffic hubs of the country. These hubs act as trendsetters, generating topics that eventually trend at the country level, and driving the conversation across the country. This poses an intriguing conjecture, drawing a parallel between the spread of information and diseases: Do trends travel faster by airplane than over the Internet?
Multi-Source Multi-Path HTTP (mHTTP): A Proposal
Venue: arXiv cs.NI 2013
Year: 2013

Today, most devices have multiple network interfaces. Coupled with wide-spread replication of popular content at multiple locations, this provides substantial path diversity in the Internet. We propose Multi-source Multipath HTTP, mHTTP, which takes advantage of all existing types of path diversity in the Internet. mHTTP needs only client-side but not server-side or network modifications as it is a receiver-oriented mechanism. Moreover, the modifications are restricted to the socket interface. Thus, no changes are needed to the applications or to the kernel. As mHTTP relies on HTTP range requests, it is specific to HTTP which accounts for more than 60% of the Internet traffic. We implement mHTTP and study its performance by conducting measurements over a testbed and in the wild. Our results show that mHTTP indeed takes advantage of all types of path diversity in the Internet, and that it is a viable alternative to Multipath TCP for HTTP traffic. mHTTP decreases download times for large objects up to 50%, whereas it does no harm to small object downloads.
On price of symmetrisation
Venue: arXiv cs.DM 2013
Year: 2013

We introduce the price of symmetrisation, a concept that aims to compare fundamental differences (gap and quotient) between values of a given graph invariant for digraphs and the values of the same invariant of the symmetric versions of these digraphs. Basically, given some invariant our goal is to characterise digraphs that maximise price of symmetrisation. In particular, we show that for some invariants, as diameter or domination number, the problem is easy. The main contribution of this paper is about (partial) results on the price of symmetrisation of the average distance. It appears to be much more intricate than the simple cases mentioned above. First, we state a conjecture about digraphs that maximise this price of symmetrisation. Then, we prove that this conjecture is true for some particular class of digraphs (called bags) but it remains open for general digraphs. Moreover, we study several graph transformations in order to remove some configurations that do not appear in the conjectured extremal digraphs.
Composing DTI Visualizations with End-user Programming
Venue: arXiv cs.GR 2013
Year: 2013

We present the design and prototype implementation of a scientific visualization language called Zifazah for composing 3D visualizations of diffusion tensor magnetic resonance imaging (DT-MRI or DTI) data. Unlike existing tools allowing flexible customization of data visualizations that are programmer-oriented, we focus on domain scientists as end users in order to enable them to freely compose visualizations of their scientific data set. We analyzed end-user descriptions extracted from interviews with neurologists and physicians conducting clinical practices using DTI about how they would build and use DTI visualizations to collect syntax and semantics for the language design, and have discovered the elements and structure of the proposed language. Zifazah makes use of the initial set of lexical terms and semantics to provide a declarative language in the spirit of intuitive syntax and usage. This work contributes three, among others, main design principles for scientific visualization language design as well as a practice of such language for DTI visualization with Zifazah. First, Zifazah incorporated visual symbolic mapping based on color, size and shape, which is a sub-set of Bertin's taxonomy migrated to scientific visualizations. Second, Zifazah is defined as a spatial language whereby lexical representation of spatial relationship for 3D object visualization and manipulations, which is characteristic of scientific data, can be programmed. Third, built on top of Bertin's semiology, flexible data encoding specifically for scientific visualizations is integrated in our language in order to allow end users to achieve optimal visual composition at their best. Along with sample scripts representative of our language design features, some new DTI visualizations as the running results created by end users using the novel visualization language have also been presented.
Polynomial Kernels for λ-extendible Properties Parameterized Above the Poljak-Turzík Bound
Venue: arXiv cs.DM 2013
Year: 2013

Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < λ < 1 and λ-extendible property Π, any connected graph G on n vertices and m edges contains a spanning subgraph H in Π with at least λm + (1-λ)(n-1)/2 edges. The property of being bipartite is λ-extendible for λ = 1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max-Cut. Other examples of λ-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some integer q. Mnich et. al. (FSTTCS 2012) defined the closely related notion of strong λ-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly λ-extendible property Π is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound - does there exist a spanning subgraph H of a connected graph G such that H in Π and H has at least λm + (1-λ)(n-1)/2 + k edges? - subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when λ = 1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.
Keyboard for inputting Chinese language
Venue: arXiv cs.HC 2013
Year: 2013

As the structure of Chinese characters are very different, it is very difficult to input Chinese characters into computer quickly and conveniently. The conventional keyboard does not support the pictorial characters in Chinese language. There are 3000 to 6000 commonly used pictorial Chinese characters (Hanzi). There are a few existing systems which include "PinYin" (phonetic) system, a combination of the PinYin system and character form techniques, whole character encoding, stroke input encoding, and stoke form encoding. Each of the methods have their own advantages and disadvantages. This article describes two inventions on inputting Chinese language through a standard keyboard.
Dynamiques globales et locales dans un réseau de télécommunications
Venue: arXiv cs.SI 2013
Year: 2013

Traditional network generation models attempt to replicate global structural properties (degree distribution, average distance, clustering coefficient, communities, etc.) through synthetic link formation mechanisms such as triadic closure or preferential attachment. In this work, we study the evolution of a very big communication network coming from mobile telephony and we analyse the link formation process. A first study conducted on the standard mechanisms allows observing that several mechanisms are responsible for the properties observed in this network. In a second study, we characterize more precisely the link formation process by searching for correlations between the probability of creating a new link and some individual properties such as the degree, the clustering coefficient and the age of the nodes.
The 10-point and 12-point Number Theoretic Hilbert Transform
Venue: arXiv cs.CR 2013
Year: 2013

This paper presents 10-point and 12-point versions of the recently introduced number theoretic Hilbert (NHT) transforms. Such transforms have applications in signal processing and scrambling. Polymorphic solutions with respect to different moduli for each of the two cases have been found. The multiplicity of solutions for the same moduli increases their applicability to cryptography.
Phase Retrieval from Coded Diffraction Patterns
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the question of recovering the phase of an object from intensity-only measurements, a problem which naturally appears in X-ray crystallography and related disciplines. We study a physically realistic setup where one can modulate the signal of interest and then collect the intensity of its diffraction pattern, each modulation thereby producing a sort of coded diffraction pattern. We show that PhaseLift, a recent convex programming technique, recovers the phase information exactly from a number of random modulations, which is polylogarithmic in the number of unknowns. Numerical experiments with noiseless and noisy data complement our theoretical analysis and illustrate our approach.
A low complexity approach of combining cooperative diversity and multiuser diversity in multiuser cooperative networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate the scheduling scheme to combine cooperative diversity (CD) and multiuser diversity (MUD) in multiuser cooperative networks under the time resource allocation (TRA) framework in which the whole transmission is divided into two phases: the broadcast phase and the relay phase. The broadcast phase is for direct transmission whereas the relay phase is for relay transmission. Based on this TRA framework, a user selection based low complexity relay protocol (US-LCRP) is proposed to combine CD and MUD. In each time slot (TS) of the broadcast phase, a "best" user is selected for transmission in order to obtain MUD. In the relay phase, the relays forward the messages of some specific users in a fixed order and then invoke the limited feedback information to achieve CD. We demonstrate that the diversity-multiplexing tradeoff (DMT) of the US-LCRP is superior to that of the existing schemes, where more TSs are allocated for direct transmission in order to jointly exploit CD and MUD. Our analytical and numerical results show that the US-LCRP constitutes a more efficient resource utilization approach than the existing schemes. Additionally, the US-LCRP can be implemented with low complexity because only the direct links' channel state information (CSI) is estimated during the whole transmission.
Next Generation Cluster Editing
Venue: arXiv cs.DS 2013
Year: 2013

This work aims at improving the quality of structural variant prediction from the mapped reads of a sequenced genome. We suggest a new model based on cluster editing in weighted graphs and introduce a new heuristic algorithm that allows to solve this problem quickly and with a good approximation on the huge graphs that arise from biological datasets.
A Probabilistic Approach to Risk Mapping for Mt. Etna
Venue: arXiv cs.CE 2013
Year: 2013

We evaluate susceptibility to lava flows on Mt. Etna based on specially designed die-toss experiments using probabilities for type, time and place of activation from the volcano's 400-year recorded history and current studies on its known fractures and fissures. The types of activations were forcast using a table of probabilities for events, typed by duration and volume of ejecta. Lengths of time were represented by the number of activations to expect within a given time-frame, calculated assuming Poisson-distributed inter-arrival times for activations. Locations of future activations were forecast with a probability distribution function for activation probabilities. Most likely scenarios for risk and resulting topography were generated for Etna's next activation (average 7.76 years), the next 25, 50 and 100 years. Forecasts for areas most likely affected are in good agreement with previous risk studies made. Forecasts for risks of lava invasions, as well as future topographies might be a first. Threats to lifelines are also discussed.
Impact of Interleaver Pruning on Properties of Underlying Permutations
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we address the issue of pruning (i.e., shortening) a given interleaver via truncation of the transposition vector of the mother permutation and study its impact on the structural properties of the permutation. This method of pruning allows for continuous un-interrupted data flow regardless of the permutation length since the permutation engine is a buffer whose leading element is swapped by other elements in the queue. The principle goal of pruning is that of construction of variable length and hence delay interleavers with application to iterative soft information processing and concatenated codes, using the same structure (possibly in hardware) of the interleaver and deinterleaver units. We address the issue of how pruning impacts the spread of the permutation and also look at how pruning impacts algebraically constructed permutations. We note that pruning via truncation of the transposition vector of the permutation can have a catastrophic impact on the permutation spread of algebraically constructed permutations. To remedy this problem, we propose a novel lifting method whereby a subset of the points in the permutation map leading to low spread of the pruned permutation are identified and eliminated. Practical realization of this lifting is then proposed via dummy symbol insertion in the input queue of the Finite State Permuter (FSP), and subsequent removal of the dummy symbols at the FSP output.
Dense Scattering Layer Removal
Venue: arXiv cs.CV 2013
Year: 2013

We propose a new model, together with advanced optimization, to separate a thick scattering media layer from a single natural image. It is able to handle challenging underwater scenes and images taken in fog and sandstorm, both of which are with significantly reduced visibility. Our method addresses the critical issue -- this is, originally unnoticeable impurities will be greatly magnified after removing the scattering media layer -- with transmission-aware optimization. We introduce non-local structure-aware regularization to properly constrain transmission estimation without introducing the halo artifacts. A selective-neighbor criterion is presented to convert the unconventional constrained optimization problem to an unconstrained one where the latter can be efficiently solved.
Platform Competition as Network Contestability
Venue: arXiv cs.GT 2013
Year: 2013

Recent research in industrial organisation has investigated the essential place that middlemen have in the networks that make up our global economy. In this paper we attempt to understand how such middlemen compete with each other through a game theoretic analysis using novel techniques from decision-making under ambiguity. We model a purposely abstract and reduced model of one middleman who pro- vides a two-sided platform, mediating surplus-creating interactions between two users. The middleman evaluates uncertain outcomes under positional ambiguity, taking into account the possibility of the emergence of an alternative middleman offering intermediary services to the two users. Surprisingly, we find many situations in which the middleman will purposely extract maximal gains from her position. Only if there is relatively low probability of devastating loss of business under competition, the middleman will adopt a more competitive attitude and extract less from her position.
Stabilizing discrete-time switched linear systems
Venue: arXiv cs.SY 2013
Year: 2013

This article deals with stabilizing discrete-time switched linear systems. Our contributions are threefold: Firstly, given a family of linear systems possibly containing unstable dynamics, we propose a large class of switching signals that stabilize a switched system generated by the switching signal and the given family of systems. Secondly, given a switched system, a sufficient condition for the existence of the proposed switching signal is derived by expressing the switching signal as an infinite walk on a directed graph representing the switched system. Thirdly, given a family of linear systems, we propose an algorithmic technique to design a switching signal for stabilizing the corresponding switched system.
Enabling Context-awareness by Predicate Detection in Asynchronous Pervasive Computing Environments
Venue: arXiv cs.DC 2013
Year: 2013

Pervasive applications are involving more and more autonomous computing and communicating devices, augmented with the abilities of sensing and controlling the logical / physical environment. To enable context-awareness for such applications, we are challenged by the intrinsic asynchrony among the context collecting devices. To this end, we introduce the predicate detection theory and propose the Predicate-Detection-based Context-Awareness (PD-CA) framework, in which: a) logical time is used to explicitly cope with the asynchrony; b) specification of predicates enables the applications to express contextual properties of their concerns; c) online and incremental predicate detection algorithms effectively enable context-awareness at runtime. Under the guidance of the PD-CA framework, we present the design and implementation of the MIPA middleware, which shields the applications from the burden of processing the asynchronous contexts. We also demonstrate how PD-CA simplifies the development of context-aware applications. Experimental evaluations show the performance of MIPA in supporting context-aware applications despite of the asynchrony.