OpenRaiser/Intern-Atlas huggingface dataset:
Slime Mould Memristors
Venue: arXiv cs.ET 2014
Year: 2014

In laboratory experiments we demonstrate that protoplasmic tubes of acellular slime mould \emph{Physarum polycephalum} show current versus voltage profiles consistent with memristive systems and that the effect is due to the living protoplasm of the mould. This complements previous findings on memristive properties of other living systems (human skin and blood) and contributes to development of self-growing bio-electronic circuits. Distinctive asymmetric $V$-$I$ curves which were occasionally observed when the internal current is on the same order as the driven current, are well-modelled by the concept of active memristors.
Algorithms for Tolerant Tverberg Partitions
Venue: arXiv cs.CG 2014
Year: 2014

Let $P$ be a $d$-dimensional $n$-point set. A partition $T$ of $P$ is called a Tverberg partition if the convex hulls of all sets in $T$ intersect in at least one point. We say $T$ is $t$-tolerant if it remains a Tverberg partition after deleting any $t$ points from $P$. Soberón and Strausz proved that there is always a $t$-tolerant Tverberg partition with $\lceil n / (d+1)(t+1) \rceil$ sets. However, so far no nontrivial algorithms for computing or approximating such partitions have been presented. For $d \leq 2$, we show that the Soberón-Strausz bound can be improved, and we show how the corresponding partitions can be found in polynomial time. For $d \geq 3$, we give the first polynomial-time approximation algorithm by presenting a reduction to the Tverberg problem with no tolerance. Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is t-tolerant.
A cost-benefit analysis of low latency via added utilization
Venue: arXiv cs.NI 2014
Year: 2014

Several recently proposed techniques achieve latency reduction by trading it off for some amount of additional bandwidth usage. But how would one quantify whether the tradeoff is actually beneficial in a given system? We develop an economic cost vs. benefit analysis for answering this question. We use the analysis to derive a benchmark for wide-area client-server applications, and demonstrate how it can be applied to reason about a particular latency saving technique --- redundant DNS requests.
OFDM Synthetic Aperture Radar Imaging with Sufficient Cyclic Prefix
Venue: arXiv cs.IT 2014
Year: 2014

The existing linear frequency modulated (LFM) (or step frequency) and random noise synthetic aperture radar (SAR) systems may correspond to the frequency hopping (FH) and direct sequence (DS) spread spectrum systems in the past second and third generation wireless communications. Similar to the current and future wireless communications generations, in this paper, we propose OFDM SAR imaging, where a sufficient cyclic prefix (CP) is added to each OFDM pulse. The sufficient CP insertion converts an inter-symbol interference (ISI) channel from multipaths into multiple ISI-free subchannels as the key in a wireless communications system, and analogously, it provides an inter-range-cell interference (IRCI) free (high range resolution) SAR image in a SAR system. The sufficient CP insertion along with our newly proposed SAR imaging algorithm particularly for the OFDM signals also differentiates this paper from all the existing studies in the literature on OFDM radar signal processing. Simulation results are presented to illustrate the high range resolution performance of our proposed CP based OFDM SAR imaging algorithm.
Iterative Plan Construction for the Workflow Satisfiability Problem
Venue: arXiv cs.DS 2014
Year: 2014

The \emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a \emph{plan} -- an assignment of tasks to authorized users -- such that all constraints are satisfied. Several bespoke algorithms have been constructed for solving the WSP, optimised to deal with constraints (business rules) of particular types. It is natural to see the WSP as a subclass of the {\em Constraint Satisfaction Problem (CSP)} in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive as a CSP is that we can assume that the number of tasks is very small compared to the number of users. This is in sharp contrast with traditional CSP models where the domain is small and the number of variables is very large. As such, it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. We have identified a new FPT constraint language, user-independent constraint, that includes many of the constraints of interest in business processing systems. We are also able to prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. In this paper we present our generic algorithm, in which plans are grouped into equivalence classes, each class being associated with a \emph{pattern}. We demonstrate that our generic algorithm has running time $O^*(2^{k\log k})$, where $k$ is the number of tasks, for the language of user-independent constraints. We also show that there is no algorithm of running time $O^*(2^{o(k\log k)})$ for user-independent constraints unless the Exponential Time Hypothesis fails.
Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Venue: arXiv cs.DS 2014
Year: 2014

There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved performance in Quicksort is not sustained in Quickselect; a variant of Quicksort for finding order statistics. We investigate the number of comparisons made by Quickselect to find a key with a randomly selected rank under Yaroslavskiy's algorithm. This grand averaging is a smoothing operator over all individual distributions for specific fixed order statistics. We give the exact grand average. The grand distribution of the number of comparison (when suitably scaled) is given as the fixed-point solution of a distributional equation of a contraction in the Zolotarev metric space. Our investigation shows that Quickselect under older partitioning methods slightly outperforms Quickselect under Yaroslavskiy's algorithm, for an order statistic of a random rank. Similar results are obtained for extremal order statistics, where again we find the exact average, and the distribution for the number of comparisons (when suitably scaled). Both limiting distributions are of perpetuities (a sum of products of independent mixed continuous random variables).
Classifying and Visualizing Motion Capture Sequences using Deep Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

The gesture recognition using motion capture data and depth sensors has recently drawn more attention in vision recognition. Currently most systems only classify dataset with a couple of dozens different actions. Moreover, feature extraction from the data is often computational complex. In this paper, we propose a novel system to recognize the actions from skeleton data with simple, but effective, features using deep neural networks. Features are extracted for each frame based on the relative positions of joints (PO), temporal differences (TD), and normalized trajectories of motion (NT). Given these features a hybrid multi-layer perceptron is trained, which simultaneously classifies and reconstructs input data. We use deep autoencoder to visualize learnt features, and the experiments show that deep neural networks can capture more discriminative information than, for instance, principal component analysis can. We test our system on a public database with 65 classes and more than 2,000 motion sequences. We obtain an accuracy above 95% which is, to our knowledge, the state of the art result for such a large dataset.
Time- and Frequency-Varying $K$-Factor of Non-Stationary Vehicular Channels for Safety Relevant Scenarios
Venue: arXiv cs.NI 2014
Year: 2014

Vehicular communication channels are characterized by a non-stationary time- and frequency-selective fading process due to fast changes in the environment. We characterize the distribution of the envelope of the first delay bin in vehicle-to-vehicle channels by means of its Rician $K$-factor. We analyze the time-frequency variability of this channel parameter using vehicular channel measurements at 5.6 GHz with a bandwidth of 240 MHz for safety-relevant scenarios in intelligent transportation systems (ITS). This data enables a frequency-variability analysis from an IEEE 802.11p system point of view, which uses 10 MHz channels. We show that the small-scale fading of the envelope of the first delay bin is Ricean distributed with a varying $K$-factor. The later delay bins are Rayleigh distributed. We demonstrate that the $K$-factor cannot be assumed to be constant in time and frequency. The causes of these variations are the frequency-varying antenna radiation patterns as well as the time-varying number of active scatterers, and the effects of vegetation. We also present a simple but accurate bi-modal Gaussian mixture model, that allows to capture the $K$-factor variability in time for safety-relevant ITS scenarios.
Bounding the Estimation Error of Sampling-based Shapley Value Approximation
Venue: arXiv cs.GT 2014
Year: 2014

The Shapley value is arguably the most central normative solution concept in cooperative game theory. It specifies a unique way in which the reward from cooperation can be "fairly" divided among players. While it has a wide range of real world applications, its use is in many cases hampered by the hardness of its computation. A number of researchers have tackled this problem by (i) focusing on classes of games where the Shapley value can be computed efficiently, or (ii) proposing representation formalisms that facilitate such efficient computation, or (iii) approximating the Shapley value in certain classes of games. For the classical \textit{characteristic function} representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro \textit{et al.} \cite{castro}. While this algorithm provides a bound on the approximation error, this bound is \textit{asymptotic}, meaning that it only holds when the number of samples increases to infinity. On the other hand, when a finite number of samples is drawn, an unquantifiable error is introduced, meaning that the bound no longer holds. With this in mind, we provide non-asymptotic bounds on the estimation error for two cases: where (i) the \textit{variance}, and (ii) the \textit{range}, of the players' marginal contributions is known. Furthermore, for the second case, we show that when the range is significantly large relative to the Shapley value, the bound can be improved (from $O(\frac{r}{m})$ to $O(\sqrt{\frac{r}{m}})$). Finally, we propose, and demonstrate the effectiveness of using stratified sampling for improving the bounds further.
Uplink Performance of Time-Reversal MRC in Massive MIMO Systems Subject to Phase Noise
Venue: arXiv cs.IT 2014
Year: 2014

Multi-user multiple-input multiple-output (MU-MIMO) cellular systems with an excess of base station (BS) antennas (Massive MIMO) offer unprecedented multiplexing gains and radiated energy efficiency. Oscillator phase noise is introduced in the transmitter and receiver radio frequency chains and severely degrades the performance of communication systems. We study the effect of oscillator phase noise in frequency-selective Massive MIMO systems with imperfect channel state information (CSI). In particular, we consider two distinct operation modes, namely when the phase noise processes at the $M$ BS antennas are identical (synchronous operation) and when they are independent (non-synchronous operation). We analyze a linear and low-complexity time-reversal maximum-ratio combining (TR-MRC) reception strategy. For both operation modes we derive a lower bound on the sum-capacity and we compare their performance. Based on the derived achievable sum-rates, we show that with the proposed receive processing an $O(\sqrt{M})$ array gain is achievable. Due to the phase noise drift the estimated effective channel becomes progressively outdated. Therefore, phase noise effectively limits the length of the interval used for data transmission and the number of scheduled users. The derived achievable rates provide insights into the optimum choice of the data interval length and the number of scheduled users.
Multi-Agent Consensus With Relative-State-Dependent Measurement Noises
Venue: arXiv cs.SY 2014
Year: 2014

In this note, the distributed consensus corrupted by relative-state-dependent measurement noises is considered. Each agent can measure or receive its neighbors' state information with random noises, whose intensity is a vector function of agents' relative states. By investigating the structure of this interaction and the tools of stochastic differential equations, we develop several small consensus gain theorems to give sufficient conditions in terms of the control gain, the number of agents and the noise intensity function to ensure mean square (m. s.) and almost sure (a. s.) consensus and quantify the convergence rate and the steady-state error. Especially, for the case with homogeneous communication and control channels, a necessary and sufficient condition to ensure m. s. consensus on the control gain is given and it is shown that the control gain is independent of the specific network topology, but only depends on the number of nodes and the noise coefficient constant. For symmetric measurement models, the almost sure convergence rate is estimated by the Iterated Logarithm Law of Brownian motions.
Efficiently Estimating Motif Statistics of Large Networks
Venue: arXiv cs.SI 2014
Year: 2014

Exploring statistics of locally connected subgraph patterns (also known as network motifs) has helped researchers better understand the structure and function of biological and online social networks (OSNs). Nowadays the massive size of some critical networks -- often stored in already overloaded relational databases -- effectively limits the rate at which nodes and edges can be explored, making it a challenge to accurately discover subgraph statistics. In this work, we propose sampling methods to accurately estimate subgraph statistics from as few queried nodes as possible. We present sampling algorithms that efficiently and accurately estimate subgraph properties of massive networks. Our algorithms require no pre-computation or complete network topology information. At the same time, we provide theoretical guarantees of convergence. We perform experiments using widely known data sets, and show that for the same accuracy, our algorithms require an order of magnitude less queries (samples) than the current state-of-the-art algorithms.
Design and Implementation of an Unmanned Vehicle using a GSM Network without Microcontrollers
Venue: arXiv cs.SY 2014
Year: 2014

In the recent past, wireless controlled vehicles had been extensively used in a lot of areas like unmanned rescue missions, military usage for unmanned combat and many others. But the major disadvantage of these wireless unmanned robots is that they typically make use of RF circuits for maneuver and control. Essentially RF circuits suffer from a lot of drawbacks such as limited frequency range i.e. working range, and limited control. To overcome such problems associated with RF control, few papers have been written, describing methods which make use of the GSM network and the DTMF function of a cell phone to control the robotic vehicle. This paper although uses the same principle technology of the GSM network and the DTMF based mobile phone but it essentially shows the construction of a circuit using only 4 bits of wireless data communication to control the motion of the vehicle without the use of any microcontroller. This improvement results in considerable reduction of circuit complexity and of manpower for software development as the circuit built using this system does not require any form of programming. Moreover, practical results obtained showed an appreciable degree of accuracy of the system and friendliness without the use of any microcontroller.
AstraKahn: A Coordination Language for Streaming Networks
Venue: arXiv cs.PL 2014
Year: 2014

This is a preliminary version of the language report. It contains key definitions, specifications and some examples, but lacks completeness. The full document will include Chapter 3 (Data and Instrumentation Layer) and will comprise an appendix giving the complete syntax and some whole program examples. The purpose of the present document is to fix the concepts and major features of the language and to enable the production of the definition document that is required for implementation.
Design and Implementation of an Unmanned Vehicle using a GSM Network with Microcontrollers
Venue: arXiv cs.SY 2014
Year: 2014

Now-a-days, a lot of research is being carried out in the development of USVs (Unmanned surface vehicles), UAVs (Unmanned Aerial Vehicles) etc. Now in case of USVs generally, we have seen that wireless controlled vehicles use RF circuits which suffer from many drawbacks such as limited working range, limited frequency range and limited control. Moreover shooting infrared outdoors on a bright sunny day is often problematic, since sunlight can interfere with the infrared signal. Use of a GSM network (in the form of a mobile phone, a cordless phone) for robotic control can overcome these limitations. It provides the advantages of robust control, working range as large as the coverage area of the service provider in comparison with that of an IR system, no interference with other controllers. This paper presents a Global System for Mobile Telecommunication (GSM) network based system which can be used to remotely send streams of 4 bit data for control of USVs. Furthermore, this paper describes the usage of the Dual Tone Multi-Frequency (DTMF) function of the phone, and builds a microcontroller based circuit to control the vehicle to demonstrate wireless data communication. Practical result obtained showed an appreciable degree of accuracy of the system and friendliness through the use of a microcontroller.
Computing a Compact Spline Representation of the Medial Axis Transform of a 2D Shape
Venue: arXiv cs.GR 2014
Year: 2014

We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.
Study and Development of a Data Acquisition & Control (DAQ) System using TCP/Modbus Protocol
Venue: arXiv cs.SY 2014
Year: 2014

The aim of the project was to develop a HMI (Human-Machine Interface) with the help of which a person could remotely control and monitor the Vacuum measurement system. The Vacuum measurement system was constructed using a DAQ (Data Acquisition & Control) implementation instead of a PLC based implementation because of the cost involvement and complexity involved in deployment when only one basic parameter i.e. vacuum is required to be measured. The system is to be installed in the Superconducting Cyclotron section of VECC. The need for remote monitoring arises as during the operation of the K500 Superconducting Cyclotron, people are not allowed to enter within a certain specified range due to effective ion radiation. Using the designed software i.e. HMI the following objective of remote monitoring could be achieved effortlessly from any area which is in the safe zone. Moreover the software was designed in a way that data could be recorded real time and in an unmanned way. The hardware is also easy to setup and overcomes the complexity involved in interfacing a PLC with other hardware. The deployment time is also quite fast. Lastly, the practical results obtained showed an appreciable degree of accuracy of the system and friendliness with the user.
Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces
Venue: arXiv cs.LO 2014
Year: 2014

Using ideas from synthetic topology, a new approach to descriptive set theory is suggested. Synthetic descriptive set theory promises elegant explanations for various phenomena in both classic and effective descriptive set theory. Presently, we mainly focus on developing the ideas in the category of represented spaces.
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
Venue: arXiv cs.IT 2014
Year: 2014

We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs $f_i(x)$'s, $x \in {\mathbb R}^d$ is global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of deterministic and randomized distributed AL methods, when the $f_i$'s are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings.
Making Octants Colorful and Related Covering Decomposition Problems
Venue: arXiv cs.CG 2014
Year: 2014

We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particular, we prove that for any positive integer k, every finite set of points in R^3 can be colored with k colors so that every translate of the negative octant containing at least k^6 points contains at least one of each color. The best previously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering by intervals under insertion of new intervals, even in a semi-online model, in which some coloring decisions can be delayed. This implies that a wide range of sweeping plane algorithms cannot guarantee any bound even for special cases of the octant problem.
Two-Way Relaying under the Presence of Relay Transceiver Hardware Impairments
Venue: arXiv cs.IT 2014
Year: 2014

Hardware impairments in physical transceivers are known to have a deleterious effect on communication systems; however, very few contributions have investigated their impact on relaying. This paper quantifies the impact of transceiver impairments in a two-way amplify-and-forward configuration. More specifically, the effective signal-to-noise-and-distortion ratios at both transmitter nodes are obtained. These are used to deduce exact and asymptotic closed-form expressions for the outage probabilities (OPs), as well as tractable formulations for the symbol error rates (SERs). It is explicitly shown that non-zero lower bounds on the OP and SER exist in the high-power regime---this stands in contrast to the special case of ideal hardware, where the OP and SER go asymptotically to zero.