OpenRaiser/Intern-Atlas huggingface dataset:
Energy-Neutral Source-Channel Coding with Battery and Memory Size Constraints
Venue: arXiv cs.IT 2014
Year: 2014

We study energy management policies for the compression and transmission of source data collected by an energy-harvesting sensor node with a finite energy buffer (e.g., rechargeable battery) and a finite data buffer (memory) between source encoder and channel encoder. The sensor node can adapt the source and channel coding rates depending on the observation and channel states. In such a system, the absence of precise information about the amount of energy available in the future is a key challenge. We provide analytical bounds and scaling laws for the average distortion that depend on the size of the energy and data buffers. We furthermore design a resource allocation policy that achieves almost optimal distortion scaling. Our results demonstrate that the energy leakage of state of art energy management policies can be avoided by jointly controlling the source and channel coding rates.
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Venue: arXiv cs.DS 2014
Year: 2014

We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length $n$ in several of the possible models. In the read-only and write-only model, we show that $p$-pass algorithms need memory space $Θ(n/p)$. But if either the output stream or the input stream is read-write, then the complexity falls to $Θ(n/p^2)$. It becomes $polylog(n)$ if $p = O(log n)$ and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has $O(1)$ expansion, $O(log n)$ passes and $O(log n)$ memory.
Non-Malleable Coding Against Bit-wise and Split-State Tampering
Venue: arXiv cs.IT 2014
Year: 2014

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Dziembowski et al. show existence of non-malleable codes for any class of tampering functions of bounded size. We consider constructions of coding schemes against two well-studied classes of tampering functions: bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). 1. For bit-tampering, we obtain explicit and efficiently encodable and decodable codes of length $n$ achieving rate $1-o(1)$ and error (security) $\exp(-\tildeΩ(n^{1/7}))$. We improve the error to $\exp(-\tildeΩ(n))$ at the cost of making the construction Monte Carlo with success probability $1-\exp(-Ω(n))$. Previously, the best known construction of bit-tampering codes was the Monte Carlo construction of Dziembowski et al. (ICS 2010) achieving rate ~.1887. 2. We initiate the study of seedless non-malleable extractors as a variation of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove existence of such extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.
Rank-frequency relation for Chinese characters
Venue: arXiv cs.CL 2014
Year: 2014

We show that the Zipf's law for Chinese characters perfectly holds for sufficiently short texts (few thousand different characters). The scenario of its validity is similar to the Zipf's law for words in short English texts. For long Chinese texts (or for mixtures of short Chinese texts), rank-frequency relations for Chinese characters display a two-layer, hierarchic structure that combines a Zipfian power-law regime for frequent characters (first layer) with an exponential-like regime for less frequent characters (second layer). For these two layers we provide different (though related) theoretical descriptions that include the range of low-frequency characters (hapax legomena). The comparative analysis of rank-frequency relations for Chinese characters versus English words illustrates the extent to which the characters play for Chinese writers the same role as the words for those writing within alphabetical systems.
On the Positivity Problem for Simple Linear Recurrence Sequences
Venue: arXiv cs.DM 2014
Year: 2014

Given a linear recurrence sequence (LRS) over the integers, the Positivity Problem} asks whether all terms of the sequence are positive. We show that, for simple LRS (those whose characteristic polynomial has no repeated roots) of order 9 or less, Positivity is decidable, with complexity in the Counting Hierarchy.
Towards a Software Product Sustainability Model
Venue: arXiv cs.SE 2014
Year: 2014

The necessity to adapt current products and services into a way of working environmentally friendly is already a social and economic demand. Although the GreenIT can be considered a mature discipline, software sustainability, both in its process and its use, has not begun to be a topic of interest until the last few years. In this sense we think is fundamental to define what we consider that is software sustainability and how to evaluate it properly.
Tractable vs. Intractable Cases of Matching Dependencies for Query Answering under Entity Resolution
Venue: arXiv cs.DB 2014
Year: 2014

Matching Dependencies (MDs) are a relatively recent proposal for declarative entity resolution. They are rules that specify, on the basis of similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The resolved answers to queries are those that are invariant under the resulting class of resolved instances. Previous work identified certain classes of queries and sets of MDs for which resolved query answering is tractable. Special emphasis was placed on cyclic sets of MDs. In this work we further investigate the complexity of this problem, identifying intractable cases, and exploring the frontier between tractability and intractability. We concentrate mostly on acyclic sets of MDs. For a special case we obtain a dichotomy result relative to NP-hardness.
Matching colored points with rectangles
Venue: arXiv cs.CG 2014
Year: 2014

Let $S$ be a point set in the plane such that each of its elements is colored either red or blue. A matching of $S$ with rectangles is any set of pairwise-disjoint axis-aligned rectangles such that each rectangle contains exactly two points of $S$. Such a matching is monochromatic if every rectangle contains points of the same color, and is bichromatic if every rectangle contains points of different colors. In this paper we study the following two problems: 1. Find a maximum monochromatic matching of $S$ with rectangles. 2. Find a maximum bichromatic matching of $S$ with rectangles. For each problem we provide a polynomial-time approximation algorithm that constructs a matching with at least $1/4$ of the number of rectangles of an optimal matching. We show that the first problem is $\mathsf{NP}$-hard even if either the matching rectangles are restricted to axis-aligned segments or $S$ is in general position, that is, no two points of $S$ share the same $x$ or $y$ coordinate. We further show that the second problem is also $\mathsf{NP}$-hard, even if $S$ is in general position. These $\mathsf{NP}$-hardness results follow by showing that deciding the existence of a perfect matching is $\mathsf{NP}$-complete in each case. The approximation results are based on a relation of our problem with the problem of finding a maximum independent set in a family of axis-aligned rectangles. With this paper we extend previous ones on matching one-colored points with rectangles and squares, and matching two-colored points with segments. Furthermore, using our techniques, we prove that it is $\mathsf{NP}$-complete to decide a perfect matching with rectangles in the case where all points have the same color, solving an open problem of Bereg, Mutsanas, and Wolff [CGTA (2009)].
Diffusive Molecular Communication with Disruptive Flows
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the performance of detectors in a diffusive molecular communication environment where steady uniform flow is present. We derive the expected number of information molecules to be observed in a passive spherical receiver, and determine the impact of flow on the assumption that the concentration of molecules throughout the receiver is uniform. Simulation results show the impact of advection on detector performance as a function of the flow's magnitude and direction. We highlight that there are disruptive flows, i.e., flows that are not in the direction of information transmission, that lead to an improvement in detector performance as long as the disruptive flow does not dominate diffusion and sufficient samples are taken.
A Comparative Usability Study of Two-Factor Authentication
Venue: arXiv cs.CR 2014
Year: 2014

Two-factor authentication (2F) aims to enhance resilience of password-based authentication by requiring users to provide an additional authentication factor, e.g., a code generated by a security token. However, it also introduces non-negligible costs for service providers and requires users to carry out additional actions during the authentication process. In this paper, we present an exploratory comparative study of the usability of 2F technologies. First, we conduct a pre-study interview to identify popular technologies as well as contexts and motivations in which they are used. We then present the results of a quantitative study based on a survey completed by 219 Mechanical Turk users, aiming to measure the usability of three popular 2F solutions: codes generated by security tokens, one-time PINs received via email or SMS, and dedicated smartphone apps (e.g., Google Authenticator). We record contexts and motivations, and study their impact on perceived usability. We find that 2F technologies are overall perceived as usable, regardless of motivation and/or context of use. We also present an exploratory factor analysis, highlighting that three metrics -- ease-of-use, required cognitive efforts, and trustworthiness -- are enough to capture key factors affecting 2F usability.
Implementation of a language driven Backpropagation algorithm
Venue: arXiv cs.NE 2014
Year: 2014

Inspired by the importance of both communication and feedback on errors in human learning, our main goal was to implement a similar mechanism in supervised learning of artificial neural networks. The starting point in our study was the observation that words should accompany the input vectors included in the training set, thus extending the ANN input space. This had as consequence the necessity to take into consideration a modified sigmoid activation function for neurons in the first hidden layer (in agreement with a specific MLP apartment structure), and also a modified version of the Backpropagation algorithm, which allows using of unspecified (null) desired output components. Following the belief that basic concepts should be tested on simple examples, the previous mentioned mechanism was applied on both the XOR problem and a didactic color case study. In this context, we noticed the interesting fact that the ANN was capable to categorize all desired input vectors in the absence of their corresponding words, even though the training set included only word accompanied inputs, in both positive and negative examples. Further analysis along applying this approach to more complex scenarios is currently in progress, as we consider the proposed language-driven algorithm might contribute to a better understanding of learning in humans, opening as well the possibility to create a specific category of artificial neural networks, with abstraction capabilities.
Coefficient Matrices Computation of Structural Vector Autoregressive Model
Venue: arXiv cs.NA 2014
Year: 2014

In this paper we present the Large Inverse Cholesky (LIC) method, an efficient method for computing the coefficient matrices of a Structural Vector Autoregressive (SVAR) model.
Simple and Efficient Local Codes for Distributed Stable Network Construction
Venue: arXiv cs.DC 2014
Year: 2014

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol (i.e. the system is homogeneous). Moreover, we assume pairwise interactions between the processes that are scheduled by an adversary. The only constraint on the adversary scheduler is that it must be fair. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of the their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. We provide proofs of correctness for all of our protocols and analyze the expected time to convergence of most of them under a uniform random scheduler that selects the next pair of interacting processes uniformly at random from all such pairs. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks.
Ensuring High-Quality Randomness in Cryptographic Key Generation
Venue: arXiv cs.CR 2014
Year: 2014

The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an entropy authority into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public-key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a 2.1x slowdown over conventional RSA key generation and it incurs a 4.4x slowdown over conventional EC-DSA key generation.
Stationary Cycling Induced by Switched Functional Electrical Stimulation Control
Venue: arXiv cs.SY 2014
Year: 2014

Functional electrical stimulation (FES) is used to activate the dysfunctional lower limb muscles of individuals with neuromuscular disorders to produce cycling as a means of exercise and rehabilitation. However, FES-cycling is still metabolically inefficient and yields low power output at the cycle crank compared to able-bodied cycling. Previous literature suggests that these problems are symptomatic of poor muscle control and non-physiological muscle fiber recruitment. The latter is a known problem with FES in general, and the former motivates investigation of better control methods for FES-cycling.In this paper, a stimulation pattern for quadriceps femoris-only FES-cycling is derived based on the effectiveness of knee joint torque in producing forward pedaling. In addition, a switched sliding-mode controller is designed for the uncertain, nonlinear cycle-rider system with autonomous state-dependent switching. The switched controller yields ultimately bounded tracking of a desired trajectory in the presence of an unknown, time-varying, bounded disturbance, provided a reverse dwell-time condition is satisfied by appropriate choice of the control gains and a sufficient desired cadence. Stability is derived through Lyapunov methods for switched systems, and experimental results demonstrate the performance of the switched control system under typical cycling conditions.
Automatic estimation of the regularization parameter in 2-D focusing gravity inversion: an application to the Safo manganese mine in northwest of Iran
Venue: arXiv cs.CE 2014
Year: 2014

We investigate the use of Tikhonov regularization with the minimum support stabilizer for underdetermined 2-D inversion of gravity data. This stabilizer produces models with non-smooth properties which is useful for identifying geologic structures with sharp boundaries. A very important aspect of using Tikhonov regularization is the choice of the regularization parameter that controls the trade off between the data fidelity and the stabilizing functional. The L-curve and generalized cross validation techniques, which only require the relative sizes of the uncertainties in the observations are considered. Both criteria are applied in an iterative process for which at each iteration a value for regularization parameter is estimated. Suitable values for the regularization parameter are successfully determined in both cases for synthetic but practically relevant examples. Whenever the geologic situation permits, it is easier and more efficient to model the subsurface with a 2-D algorithm, rather than to apply a full 3-D approach. Then, because the problem is not large it is appropriate to use the generalized singular value decomposition for solving the problem efficiently. The method is applied on a profile of gravity data acquired over the Safo mining camp in Maku-Iran, which is well known for manganese ores. The presented results demonstrate success in reconstructing the geometry and density distribution of the subsurface source.
Evolutionary Algorithm for Graph Anonymization
Venue: arXiv cs.DB 2014
Year: 2014

In recent years there has been a significant increase in the use of graphs as a tool for representing information. It is very important to preserve the privacy of users when one wants to publish this information, especially in the case of social graphs. In this case, it is essential to implement an anonymization process in the data in order to preserve users' privacy. In this paper we present an algorithm for graph anonymization, called Evolutionary Algorithm for Graph Anonymization (EAGA), based on edge modifications to preserve the k-anonymity model.
The importance of stimulus noise analysis for self-motion studies
Venue: arXiv cs.SY 2014
Year: 2014

Motion simulators are widely employed in basic and applied research to study the neural mechanisms of perception and action under inertial stimulations. In these studies, uncontrolled simulator-introduced noise inevitably leads to a mismatch between the reproduced motion and the trajectories meticulously designed by the experimenter, possibly resulting in undesired motion cues to the investigated system. An understanding of the simulator response to different motion commands is therefore a crucial yet often underestimated step towards the interpretation of experimental results. In this work, we developed analysis methods based on signal processing techniques to quantify the noise in the actual motion, and its deterministic and stochastic components. Our methods allow comparisons between commanded and actual motion as well as between different actual motion profiles. A specific practical example from one of our studies is used to illustrate the methodologies and their relevance, but this does not detract from its general applicability. Analyses of the simulator inertial recordings show direction-dependent noise and nonlinearity related to the command amplitude. The Signal-to-Noise Ratio is one order of magnitude higher for the larger motion amplitudes we tested, compared to the smaller motion amplitudes. Deterministic and stochastic noise components are of similar magnitude for the weaker motions, whereas for stronger motions the deterministic component dominates the stochastic component. The effect of simulator noise on animal/human motion sensitivity is discussed. We conclude that accurate analyses of a simulator motion are a crucial prerequisite for the investigation of uncertainty in self-motion perception.
EVOC: A Computer Model of the Evolution of Culture
Venue: arXiv cs.MA 2014
Year: 2014

EVOC is a computer model of the EVOlution of Culture. It consists of neural network based agents that invent ideas for actions, and imitate neighbors' actions. EVOC replicates using a different fitness function the results obtained with an earlier model (MAV), including (1) an increase in mean fitness of actions, and (2) an increase and then decrease in the diversity of actions. Diversity of actions is positively correlated with number of needs, population size and density, and with the erosion of borders between populations. Slowly eroding borders maximize diversity, fostering specialization followed by sharing of fit actions. Square (as opposed to toroidal) worlds also exhibit higher diversity. Introducing a leader that broadcasts its actions throughout the population increases the fitness of actions but reduces diversity; these effects diminish the more leaders there are. Low density populations have less fit ideas but broadcasting diminishes this effect.