OpenRaiser/Intern-Atlas huggingface dataset:
A General Mechanism Design Methodology for Social Utility Maximization with Linear Constraints
Venue: arXiv cs.GT 2015
Year: 2015

Social utility maximization refers to the process of allocating resources in such a way that the sum of agents' utilities is maximized under the system constraints. Such allocation arises in several problems in the general area of communications, including unicast (and multicast multi-rate) service on the Internet, as well as in applications with (local) public goods, such as power allocation in wireless networks, spectrum allocation, etc. Mechanisms that implement such allocations in Nash equilibrium have also been studied but either they do not possess full implementation property, or are given in a case-by-case fashion, thus obscuring fundamental understanding of these problems. In this paper we propose a unified methodology for creating mechanisms that fully implement, in Nash equilibria, social utility maximizing functions arising in various contexts where the constraints are convex. The construction of the mechanism is done in a systematic way by considering the dual optimization problem. In addition to the required properties of efficiency and individual rationality that such mechanisms ought to satisfy, three additional design goals are the focus of this paper: a) the size of the message space scaling linearly with the number of agents (even if agents' types are entire valuation functions), b) allocation being feasible on and off equilibrium, and c) strong budget balance at equilibrium and also off equilibrium whenever demand is feasible.
Towards Making Random Passwords Memorable: Leveraging Users' Cognitive Ability Through Multiple Cues
Venue: arXiv cs.HC 2015
Year: 2015

Given the choice, users produce passwords reflecting common strategies and patterns that ease recall but offer uncertain and often weak security. System-assigned passwords provide measurable security but suffer from poor memorability. To address this usability-security tension, we argue that systems should assign random passwords but also help with memorization and recall. We investigate the feasibility of this approach with CuedR, a novel cued-recognition authentication scheme that provides users with multiple cues (visual, verbal, and spatial) and lets them choose the cues that best fit their learning process for later recognition of system-assigned keywords. In our lab study, all 37 of our participants could log in within three attempts one week after registration (mean login time: 38.0 seconds). A pilot study on using multiple CuedR passwords also showed 100% recall within three attempts. Based on our results, we suggest appropriate applications for CuedR, such as financial and e-commerce accounts.
Fitting 3D Morphable Models using Local Features
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a novel fitting method that uses local image features to fit a 3D Morphable Model to 2D images. To overcome the obstacle of optimising a cost function that contains a non-differentiable feature extraction operator, we use a learning-based cascaded regression method that learns the gradient direction from data. The method allows to simultaneously solve for shape and pose parameters. Our method is thoroughly evaluated on Morphable Model generated data and first results on real data are presented. Compared to traditional fitting methods, which use simple raw features like pixel colour or edge maps, local features have been shown to be much more robust against variations in imaging conditions. Our approach is unique in that we are the first to use local features to fit a Morphable Model. Because of the speed of our method, it is applicable for realtime applications. Our cascaded regression framework is available as an open source library (https://github.com/patrikhuber).
Botnet Detection using Social Graph Analysis
Venue: arXiv cs.SI 2015
Year: 2015

Signature-based botnet detection methods identify botnets by recognizing Command and Control (C\&C) traffic and can be ineffective for botnets that use new and sophisticate mechanisms for such communications. To address these limitations, we propose a novel botnet detection method that analyzes the social relationships among nodes. The method consists of two stages: (i) anomaly detection in an "interaction" graph among nodes using large deviations results on the degree distribution, and (ii) community detection in a social "correlation" graph whose edges connect nodes with highly correlated communications. The latter stage uses a refined modularity measure and formulates the problem as a non-convex optimization problem for which appropriate relaxation strategies are developed. We apply our method to real-world botnet traffic and compare its performance with other community detection methods. The results show that our approach works effectively and the refined modularity measure improves the detection accuracy.
Buffer Aided Relaying Improves Both Throughput and End-to-End Delay
Venue: arXiv cs.IT 2015
Year: 2015

Buffer aided relaying has recently attracted a lot of attention due to the improvement in the system throughput. However, a side effect usually deemed is that buffering at relay nodes results in the increase in packet delays. In this paper, we study the effect of buffering relays on the end-to-end delay of users' data, from the time they arrive at source until delivery to the destination. We use simple discussions to provide an insight on the overall waiting time of the packets in the system. By studying the Bernoulli distributed channel conditions, and using intuitive generalizations, we conclude that the use of buffers at relays improves not only throughput, but ironically the end-to-end delay as well. Computer simulations in the settings of practical systems confirm the above results.
Timed pushdown automata revisited
Venue: arXiv cs.FL 2015
Year: 2015

This paper contains two results on timed extensions of pushdown automata (PDA). As our first result we prove that the model of dense-timed PDA of Abdulla et al. collapses: it is expressively equivalent to dense-timed PDA with timeless stack. Motivated by this result, we advocate the framework of first-order definable PDA, a specialization of PDA in sets with atoms, as the right setting to define and investigate timed extensions of PDA. The general model obtained in this way is Turing complete. As our second result we prove NEXPTIME upper complexity bound for the non-emptiness problem for an expressive subclass. As a byproduct, we obtain a tight EXPTIME complexity bound for a more restrictive subclass of PDA with timeless stack, thus subsuming the complexity bound known for dense-timed PDA.
Distributed execution of bigraphical reactive systems
Venue: arXiv cs.DC 2015
Year: 2015

The bigraph embedding problem is crucial for many results and tools about bigraphs and bigraphical reactive systems (BRS). Current algorithms for computing bigraphical embeddings are centralized, i.e. designed to run locally with a complete view of the guest and host bigraphs. In order to deal with large bigraphs, and to parallelize reactions, we present a decentralized algorithm, which distributes both state and computation over several concurrent processes. This allows for distributed, parallel simulations where non-interfering reactions can be carried out concurrently; nevertheless, even in the worst case the complexity of this distributed algorithm is no worse than that of a centralized algorithm.
The coloring problem for $\{P_5,\bar{P_5}\}$-free graphs and $\{P_5,K_p-e\}$-free graphs is polynomial
Venue: arXiv cs.DM 2015
Year: 2015

We show that determining the chromatic number of a $\{P_5,\bar{P_5}\}$-free graph or a $\{P_5,K_p-e\}$-free graph can be done in polynomial time
Security of Power Packet Dispatching Using Differential Chaos Shift Keying
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates and confirms one advantageous function of a power packet dispatching system, which has been proposed by authors' group with being apart from the conventional power distribution system. Here is focused on the function to establish the security of power packet dispatching for prohibiting not only information but also power of power packet from being stolen by attackers. For the purpose of protecting power packets, we introduce a simple encryption of power packets before sending them. Encryption scheme based on chaotic signal is one possibility for this purpose. This paper adopts the Differential Chaos Shift Keying (DCSK) scheme for the encryption, those are partial power packet encryption and whole power packet encryption.
Scrambled geometric net integration over general product spaces
Venue: arXiv cs.NA 2015
Year: 2015

Quasi-Monte Carlo (QMC) sampling has been developed for integration over $[0,1]^s$ where it has superior accuracy to Monte Carlo (MC) for integrands of bounded variation. Scrambled net quadrature gives allows replication based error estimation for QMC with at least the same accuracy and for smooth enough integrands even better accuracy than plain QMC. Integration over triangles, spheres, disks and Cartesian products of such spaces is more difficult for QMC because the induced integrand on a unit cube may fail to have the desired regularity. In this paper, we present a construction of point sets for numerical integration over Cartesian products of $s$ spaces of dimension $d$, with triangles ($d=2$) being of special interest. The point sets are transformations of randomized $(t,m,s)$-nets using recursive geometric partitions. The resulting integral estimates are unbiased and their variance is $o(1/n)$ for any integrand in $L^2$ of the product space. Under smoothness assumptions on the integrand, our randomized QMC algorithm has variance $O(n^{-1 - 2/d} (\log n)^{s-1})$, for integration over $s$-fold Cartesian products of $d$-dimensional domains, compared to $O(n^{-1})$ for ordinary Monte Carlo.
Generating Single Peaked Votes
Venue: arXiv cs.GT 2015
Year: 2015

We discuss how to generate singled peaked votes uniformly from the Impartial Culture model.
Improved Connectivity Condition for Byzantine Fault Tolerance
Venue: arXiv cs.DC 2015
Year: 2015

Given a network in which some pairs of nodes can communicate freely, and some subsets of the nodes could be faulty and colluding to disrupt communication, when can messages reliably be sent from one given node to another? We give a new characterization of when the agreement problem can be solved and provide an agreement algorithm which can reach agreement when the number of Byzantine nodes along each minimal vertex cut is bounded. Our new bound holds for a strict superset of cases than the previously known bound. We show that the new bound is tight. Furthermore, we show that this algorithm does not require the processes to know the graph structure, as the previously known algorithm did. Finally, we explore some of the situations in which we can reach agreement if we assume that individual nodes or entire subgraphs are trustworthy.
Free Space Optical Communication with Spatial Modulation and Coherent Detection over H-K Atmospheric Turbulence Channels
Venue: arXiv cs.IT 2015
Year: 2015

The use of optical spatial modulation (OSM), which has been recently emerged as a power and bandwidth efficient pulsed modulation technique for indoor optical wireless communication, is proposed as a simple, low-complexity means of achieving spatial diversity in coherent free space optical (FSO) communication systems. In doing so, this paper makes several novel contributions as follows. It presents a generic analytical framework for obtaining the Average Bit Error Probability (ABEP) of uncoded OSM with coherent detection in the presence of turbulence-induced fading. Although the framework is general enough to accommodate any type of models based on turbulence scattering, the focus in this paper is the H-K distribution. Although this distribution represents a very general scattering model valid over a wide range of atmospheric conditions, it is has not been considered in the past in conjunction with FSO systems possibly because of its mathematical complexity. The proposed analytical framework yields exact performance evaluation results for MIMO systems with two transmit- and an arbitrary number of receive apertures. In addition, tight upper bounds are derived for the error probability for OSM systems with an arbitrary number of transmit apertures as well as for convolutionally encoded signals. The performance of OSM is compared to that of well established coherent FSO schemes, employing spatial diversity at the transmitter or the receiver only. Specifically, it is shown that OSM can offer comparable performance with conventional coherent FSO schemes while outperforming the latter in terms of spectral efficiency and hardware complexity. Various numerical performance evaluation results are also presented and compared with equivalent results obtained by Monte Carlo simulations which verify the accuracy of the derived analytical expressions.
An Upper Bound on the Complexity of Recognizable Tree Languages
Venue: arXiv cs.FL 2015
Year: 2015

The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $\Game (D\_n({\bfΣ}^0\_2))$ for some natural number $n\geq 1$, where $\Game$ is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^ω$ into the class ${\bfΔ}^1\_2$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ${\bfΔ}^1\_2$.
Wideband Self-Adaptive RF Cancellation Circuit for Full-Duplex Radio: Operating Principle and Measurements
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a novel RF circuit architecture for self-interference cancellation in inband full-duplex radio transceivers. The developed canceller is able to provide wideband cancellation with waveform bandwidths in the order of 100 MHz or beyond and contains also self-adaptive or self-healing features enabling automatic tracking of time-varying self-interference channel characteristics. In addition to architecture and operating principle descriptions, we also provide actual RF measurements at 2.4 GHz ISM band demonstrating the achievable cancellation levels with different bandwidths and when operating in different antenna configurations and under low-cost highly nonlinear power amplifier. In a very challenging example with a 100 MHz waveform bandwidth, around 41 dB total cancellation is obtained while the corresponding cancellation figure is close to 60 dB with the more conventional 20 MHz carrier bandwidth. Also, efficient tracking in time-varying reflection scenarios is demonstrated.
Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
Venue: arXiv cs.IT 2015
Year: 2015

This paper explores robust recovery of a superposition of $R$ distinct complex exponential functions from a few random Gaussian projections. We assume that the signal of interest is of $2N-1$ dimensional and $R<<2N-1$. This framework covers a large class of signals arising from real applications in biology, automation, imaging science, etc. To reconstruct such a signal, our algorithm is to seek a low-rank Hankel matrix of the signal by minimizing its nuclear norm subject to the consistency on the sampled data. Our theoretical results show that a robust recovery is possible as long as the number of projections exceeds $O(R\ln^2N)$. No incoherence or separation condition is required in our proof. Our method can be applied to spectral compressed sensing where the signal of interest is a superposition of $R$ complex sinusoids. Compared to existing results, our result here does not need any separation condition on the frequencies, while achieving better or comparable bounds on the number of measurements. Furthermore, our method provides theoretical guidance on how many samples are required in the state-of-the-art non-uniform sampling in NMR spectroscopy. The performance of our algorithm is further demonstrated by numerical experiments.
Fast and Robust Fixed-Rank Matrix Recovery
Venue: arXiv cs.CV 2015
Year: 2015

We address the problem of efficient sparse fixed-rank (S-FR) matrix decomposition, i.e., splitting a corrupted matrix $M$ into an uncorrupted matrix $L$ of rank $r$ and a sparse matrix of outliers $S$. Fixed-rank constraints are usually imposed by the physical restrictions of the system under study. Here we propose a method to perform accurate and very efficient S-FR decomposition that is more suitable for large-scale problems than existing approaches. Our method is a grateful combination of geometrical and algebraical techniques, which avoids the bottleneck caused by the Truncated SVD (TSVD). Instead, a polar factorization is used to exploit the manifold structure of fixed-rank problems as the product of two Stiefel and an SPD manifold, leading to a better convergence and stability. Then, closed-form projectors help to speed up each iteration of the method. We introduce a novel and fast projector for the $\text{SPD}$ manifold and a proof of its validity. Further acceleration is achieved using a Nystrom scheme. Extensive experiments with synthetic and real data in the context of robust photometric stereo and spectral clustering show that our proposals outperform the state of the art.
Technical Analysis on Financial Forecasting
Venue: arXiv cs.NE 2015
Year: 2015

Financial forecasting is an estimation of future financial outcomes for a company, industry, country using historical internal accounting and sales data. We may predict the future outcome of BSE_SENSEX practically by some soft computing techniques and can also optimized using PSO (Particle Swarm Optimization), EA (Evolutionary Algorithm) or DEA (Differential Evolutionary Algorithm) etc. PSO is a biologically inspired computational search & optimization method developed in 1995 by Dr. Eberhart and Dr. Kennedy based on the social behaviors of fish schooling or birds flocking. PSO is a promising method to train Artificial Neural Network (ANN). It is easy to implement then Genetic Algorithm except few parameters are adjusted. PSO is a random & pattern search technique based on populating of particle. In PSO, the particles are having some position and velocity in the search space. Two terms are used in PSO one is Local Best and another one is Global Best. To optimize problems that are like Irregular, Noisy, Change over time, Static etc. PSO uses a classic optimization method such as Gradient Decent & Quasi-Newton Methods. The observation and review of few related studies in the last few years, focusing on function of PSO, modification of PSO and operation that have implemented using PSO like function optimization, ANN Training & Fuzzy Control etc. Differential Evolution is an efficient EA technique for optimization of numerical problems, financial problems etc. PSO technique is introduced due to the swarming behavior of animals which is the collective behavior of similar size that aggregates together.
Structured Spreadsheet Modeling and Implementation
Venue: arXiv cs.SE 2015
Year: 2015

Developing an error-free spreadsheet has been a problem since the beginning of end-user computing. In this paper, we present a methodology that separates the modeling from the implementation. Using proven techniques from Information Systems and Software Engineering, we present strict, but simple, rules governing the implementation from the model. The resulting spreadsheet should be easier to understand, audit and maintain.
Iterative Merging Algorithm for Cooperative Data Exchange
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of finding the minimum sum-rate strategy in cooperative data exchange systems that do not allow packet-splitting (NPS-CDE). In an NPS-CDE system, there are a number of geographically close cooperative clients who send packets to help the others recover a packet set. A minimum sum-rate strategy is the strategy that achieves universal recovery (the situation when all the clients recover the whole packet set) with the the minimal sum-rate (the total number of transmissions). We propose an iterative merging (IM) algorithm that recursively merges client sets based on a lower estimate of the minimum sum-rate and updates to the value of the minimum sum-rate. We also show that a minimum sum-rate strategy can be learned by allocating rates for the local recovery in each merged client set in the IM algorithm. We run an experiment to show that the complexity of the IM algorithm is lower than that of the existing deterministic algorithm when the number of clients is lower than $94$.
An information system for integrated land and water resources management in the Kara River basin (Togo and Benin)
Venue: arXiv cs.CY 2015
Year: 2015

A prerequisite for integrated land and water resources management (ILWRM) is a holistic river basin assessment. The latter requires information and data from different scientific disciplines but also appropriate data management systems to store and manage historical and real time data, set up protocols that facilitate data and information access and sharing among different stakeholders, and triggering further collaboration among different institutions in support of watershed-based assessment, management and planning. In West Africa in general and especially in the transboundary Volta River basin where different environmental data are collected and managed by different agencies in different countries and also where data access and dissemination are very challenging and difficult tasks, comprehensive river basin information systems are required. This paper presents the Oti River Basin Information System (OtiRBIS), a web-based data storage, management andanalysis platform that addresses these needs and facilitates ILWRM implementation in the Kara river basin.
Approximation of Statistical Analysis and Estimation by Morphological Adaptation in a Model of Slime Mould
Venue: arXiv cs.ET 2015
Year: 2015

True slime mould Physarum polycephalum approximates a range of complex computations via growth and adaptation of its proto- plasmic transport network, stimulating a large body of recent research into how such a simple organism can perform such complex feats. The properties of networks constructed by slime mould are known to be in- fluenced by the local distribution of stimuli within its environment. But can the morphological adaptation of slime mould yield any information about the global statistical properties of its environment? We explore this possibility using a particle based model of slime mould. We demonstrate how morphological adaptation in blobs of virtual slime mould may be used as a simple computational mechanism that can coarsely approx- imate statistical analysis, estimation and tracking. Preliminary results include the approximation of the geometric centroid of 2D shapes, ap- proximation of arithmetic mean from spatially represented sorted and unsorted data distributions, and the estimation and dynamical tracking of moving object position in the presence of noise contaminated input stimuli. The results suggest that it is possible to utilise collectives of very simple components with limited individual computational ability (for ex- ample swarms of simple robotic devices) to extract statistical features from complex datasets by means of material adaptation and sensorial fusion.