OpenRaiser/Intern-Atlas huggingface dataset:
Fog Networking: An Overview on Research Opportunities
Venue: arXiv cs.NI 2016
Year: 2016

The past 15 years have seen the rise of the Cloud, along with rapid increase in Internet backbone traffic and more sophisticated cellular core networks. There are three different types of Clouds: (1) data center, (2) backbone IP network and (3) cellular core network, responsible for computation, storage, communication and network management. Now the functions of these three types of Clouds are descending to be among or near the end users, i.e., to the edge of networks, as Fog. This article presents an overview on research opportunities of Fog networking: an architecture that users one or a collaborative multitude of end-user clients or near-user edge devices to carry out a substantial amount of storage, communication and management. Architecture allocates functionalities, while engineering artifacts that may use a Fog architecture include 5G, home/personal networking, and the Internet of Things.
Forecasting Social Navigation in Crowded Complex Scenes
Venue: arXiv cs.CV 2016
Year: 2016

When humans navigate a crowed space such as a university campus or the sidewalks of a busy street, they follow common sense rules based on social etiquette. In this paper, we argue that in order to enable the design of new algorithms that can take fully advantage of these rules to better solve tasks such as target tracking or trajectory forecasting, we need to have access to better data in the first place. To that end, we contribute the very first large scale dataset (to the best of our knowledge) that collects images and videos of various types of targets (not just pedestrians, but also bikers, skateboarders, cars, buses, golf carts) that navigate in a real-world outdoor environment such as a university campus. We present an extensive evaluation where different methods for trajectory forecasting are evaluated and compared. Moreover, we present a new algorithm for trajectory prediction that exploits the complexity of our new dataset and allows to: i) incorporate inter-class interactions into trajectory prediction models (e.g, pedestrian vs bike) as opposed to just intra-class interactions (e.g., pedestrian vs pedestrian); ii) model the degree to which the social forces are regulating an interaction. We call the latter "social sensitivity"and it captures the sensitivity to which a target is responding to a certain interaction. An extensive experimental evaluation demonstrates the effectiveness of our novel approach.
Dataflow Graphs as Matrices and Programming with Higher-order Matrix Elements
Venue: arXiv cs.PL 2016
Year: 2016

We consider dataflow architecture for two classes of computations which admit taking linear combinations of execution runs: probabilistic sampling and generalized animation. We improve the earlier technique of almost continuous program transformations by adopting a discipline of bipartite graphs linking nodes obtained via general transformations and nodes obtained via linear transformations which makes it possible to develop and evolve dataflow programs over these classes of computations by continuous program transformations. The use of bipartite graphs allows us to represent the dataflow programs from this class as matrices of real numbers and evolve and modify programs by continuous change of these numbers. We develop a formalism for higher-order dataflow programming for this class of dataflow graphs based on the higher-order matrix elements. Some of our software experiments are briefly discussed.
On the Scaling Exponent of Polar Codes for Binary-Input Energy-Harvesting Channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the scaling exponent of polar codes for binary-input energy-harvesting (EH) channels with infinite-capacity batteries. The EH process is characterized by a sequence of i.i.d. random variables with finite variances. The scaling exponent $μ$ of polar codes for a binary-input memoryless channel (BMC) characterizes the closest gap between the capacity and non-asymptotic rates achieved by polar codes with error probabilities no larger than some non-vanishing $\varepsilon\in(0,1)$. It has been shown that for any $\varepsilon\in(0,1)$, the scaling exponent $μ$ for any binary-input memoryless symmetric channel (BMSC) with $I(q_{Y|X})\in(0,1)$ lies between 3.579 and 4.714 , where the upper bound $4.714$ was shown by an explicit construction of polar codes. Our main result shows that $4.714$ remains to be a valid upper bound on the scaling exponent for any binary-input EH channel, i.e., a BMC subject to additional EH constraints. Our result thus implies that the EH constraints do not worsen the rate of convergence to capacity if polar codes are employed. The main result is proved by leveraging the following three existing results: scaling exponent analyses for BMSCs, construction of polar codes designed for binary-input memoryless asymmetric channels, and the save-and-transmit strategy for EH channels.
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
Venue: arXiv cs.CC 2016
Year: 2016

A significant progress has been made in the past three decades over the study of combinatorial NP optimization problems and their associated optimization and approximate classes, such as NPO, PO, APX (or APXP), and PTAS. Unfortunately, a collection of problems that are simply placed inside the P-solvable optimization class PO never have been studiously analyzed regarding their exact computational complexity. To improve this situation, the existing framework based on polynomial-time computability needs to be expanded and further refined for an insightful analysis of various approximation algorithms targeting optimization problems within PO. In particular, we deal with those problems characterized in terms of logarithmic-space computations and uniform-circuit computations. We are focused on nondeterministic logarithmic-space (NL) optimization problems or NPO problems. Our study covers a wide range of optimization and approximation classes, dubbed as, NLO, LO, APXL, and LSAS as well as new classes NC1O, APXNC1, NC1AS, and AC0O, which are founded on uniform families of Boolean circuits. Although many NL decision problems can be naturally converted into NL optimization (NLO) problems, few NLO problems have been studied vigorously. We thus provide a number of new NLO problems falling into those low-complexity classes. With the help of NC1 or AC0 approximation-preserving reductions, we also identify the most difficult problems (known as complete problems) inside those classes. Finally, we demonstrate a number of collapses and separations among those refined optimization and approximation classes with or without unproven complexity-theoretical assumptions.
A simple technique for improving multi-class classification with neural networks
Venue: arXiv cs.LG 2016
Year: 2016

We present a novel method to perform multi-class pattern classification with neural networks and test it on a challenging 3D hand gesture recognition problem. Our method consists of a standard one-against-all (OAA) classification, followed by another network layer classifying the resulting class scores, possibly augmented by the original raw input vector. This allows the network to disambiguate hard-to-separate classes as the distribution of class scores carries considerable information as well, and is in fact often used for assessing the confidence of a decision. We show that by this approach we are able to significantly boost our results, overall as well as for particular difficult cases, on the hard 10-class gesture classification task.
Part-of-Speech Tagging for Code-mixed Indian Social Media Text at ICON 2015
Venue: arXiv cs.CL 2016
Year: 2016

This paper discusses the experiments carried out by us at Jadavpur University as part of the participation in ICON 2015 task: POS Tagging for Code-mixed Indian Social Media Text. The tool that we have developed for the task is based on Trigram Hidden Markov Model that utilizes information from dictionary as well as some other word level features to enhance the observation probabilities of the known tokens as well as unknown tokens. We submitted runs for Bengali-English, Hindi-English and Tamil-English Language pairs. Our system has been trained and tested on the datasets released for ICON 2015 shared task: POS Tagging For Code-mixed Indian Social Media Text. In constrained mode, our system obtains average overall accuracy (averaged over all three language pairs) of 75.60% which is very close to other participating two systems (76.79% for IIITH and 75.79% for AMRITA_CEN) ranked higher than our system. In unconstrained mode, our system obtains average overall accuracy of 70.65% which is also close to the system (72.85% for AMRITA_CEN) which obtains the highest average overall accuracy.
A Comprehensive Formal Security Analysis of OAuth 2.0
Venue: arXiv cs.CR 2016
Year: 2016

The OAuth 2.0 protocol is one of the most widely deployed authorization/single sign-on (SSO) protocols and also serves as the foundation for the new SSO standard OpenID Connect. Despite the popularity of OAuth, so far analysis efforts were mostly targeted at finding bugs in specific implementations and were based on formal models which abstract from many web features or did not provide a formal treatment at all. In this paper, we carry out the first extensive formal analysis of the OAuth 2.0 standard in an expressive web model. Our analysis aims at establishing strong authorization, authentication, and session integrity guarantees, for which we provide formal definitions. In our formal analysis, all four OAuth grant types (authorization code grant, implicit grant, resource owner password credentials grant, and the client credentials grant) are covered. They may even run simultaneously in the same and different relying parties and identity providers, where malicious relying parties, identity providers, and browsers are considered as well. Our modeling and analysis of the OAuth 2.0 standard assumes that security recommendations and best practices are followed, in order to avoid obvious and known attacks. When proving the security of OAuth in our model, we discovered four attacks which break the security of OAuth. The vulnerabilities can be exploited in practice and are present also in OpenID Connect. We propose fixes for the identified vulnerabilities, and then, for the first time, actually prove the security of OAuth in an expressive web model. In particular, we show that the fixed version of OAuth (with security recommendations and best practices in place) provides the authorization, authentication, and session integrity properties we specify.
BYOD Security: A New Business Challenge
Venue: arXiv cs.CR 2016
Year: 2016

Bring Your Own Device (BYOD) is a rapidly growing trend in businesses concerned with information technology. BYOD presents a unique list of security concerns for businesses implementing BYOD policies. Recent publications indicate a definite awareness of risks involved in incorporating BYOD into business, however it is still an underrated issue compared to other IT security concerns. This paper focuses on two key BYOD security issues: security challenges and available frameworks. A taxonomy specifically classifying BYOD security challenges is introduced alongside comprehensive frameworks and solutions which are also analysed to gauge their limitations.
Shape Animation with Combined Captured and Simulated Dynamics
Venue: arXiv cs.GR 2016
Year: 2016

We present a novel volumetric animation generation framework to create new types of animations from raw 3D surface or point cloud sequence of captured real performances. The framework considers as input time incoherent 3D observations of a moving shape, and is thus particularly suitable for the output of performance capture platforms. In our system, a suitable virtual representation of the actor is built from real captures that allows seamless combination and simulation with virtual external forces and objects, in which the original captured actor can be reshaped, disassembled or reassembled from user-specified virtual physics. Instead of using the dominant surface-based geometric representation of the capture, which is less suitable for volumetric effects, our pipeline exploits Centroidal Voronoi tessellation decompositions as unified volumetric representation of the real captured actor, which we show can be used seamlessly as a building block for all processing stages, from capture and tracking to virtual physic simulation. The representation makes no human specific assumption and can be used to capture and re-simulate the actor with props or other moving scenery elements. We demonstrate the potential of this pipeline for virtual reanimation of a real captured event with various unprecedented volumetric visual effects, such as volumetric distortion, erosion, morphing, gravity pull, or collisions.
Internet of Drones
Venue: arXiv cs.NI 2016
Year: 2016

The Internet of Drones (IoD) is a layered network control architecture designed mainly for coordinating the access of unmanned aerial vehicles to controlled airspace, and providing navigation services between locations referred to as nodes. The IoD provides generic services for various drone applications such as package delivery, traffic surveillance, search and rescue and more. In this paper, we present a conceptual model of how such an architecture can be organized and we specify the features that an IoD system based on our architecture should implement. For doing so, we extract key concepts from three existing large scale networks, namely the air traffic control network, the cellular network, and the Internet and explore their connections to our novel architecture for drone traffic management.
Visibility Graphs, Dismantlability, and the Cops and Robbers Game
Venue: arXiv cs.CG 2016
Year: 2016

We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
A Serial Multilevel Hypergraph Partitioning Algorithm
Venue: arXiv cs.DS 2016
Year: 2016

The graph partitioning problem has many applications in scientific computing such as computer aided design, data mining, image compression and other applications with sparse-matrix vector multiplications as a kernel operation. In many cases it is advantageous to use hypergraphs as they, compared to graphs, have a more general structure and can be used to model more complex relationships between groups of objects. This motivates our focus on the less-studied hypergraph partitioning problem. In this paper, we propose a serial multi-level bipartitioning algorithm. One important step in current heuristics for hypergraph partitioning is clustering during which similar vertices must be recognized. This can be particularly difficult in irregular hypergraphs with high variation of vertex degree and hyperedge size; heuristics that rely on local vertex clustering decisions often give poor partitioning quality. A novel feature of the proposed algorithm is to use the techniques of rough set clustering to address this problem. We show that our proposed algorithm gives on average between 18.8 per cent and 71.1 per cent better quality on these irregular hypergraphs by comparing it to state-of-the-art hypergraph partitioning algorithms on benchmarks taken from real applications.
Convergence Analysis of the Gaussian Regularized Shannon Sampling Formula
Venue: arXiv cs.IT 2016
Year: 2016

We consider the reconstruction of a bandlimited function from its finite localized sample data. Truncating the classical Shannon sampling series results in an unsatisfactory convergence rate due to the slow decayness of the sinc function. To overcome this drawback, a simple and highly effective method, called the Gaussian regularization of the Shannon series, was proposed in the engineering and has received remarkable attention. It works by multiplying the sinc function in the Shannon series with a regularized Gaussian function. L. Qian (Proc. Amer. Math. Soc., 2003) established the convergence rate of $O(\sqrt{n}\exp(-\frac{π-δ}2n))$ for this method, where $δ<π$ is the bandwidth and $n$ is the number of sample data. C. Micchelli {\it et al.} (J. Complexity, 2009) proposed a different regularized method and obtained the corresponding convergence rate of $O(\frac1{\sqrt{n}}\exp(-\frac{π-δ}2n))$. This latter rate is by far the best among all regularized methods for the Shannon series. However, their regularized method involves the solving of a linear system and is implicit and more complicated. The main objective of this note is to show that the Gaussian regularization of the Shannon series can also achieve the same best convergence rate as that by C. Micchelli {\it et al}. We also show that the Gaussian regularization method can improve the convergence rate for the useful average sampling. Finally, the outstanding performance of numerical experiments justifies our results.
Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
Venue: arXiv cs.DS 2016
Year: 2016

In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability of ATSP on topologically restricted graphs. It has been shown by [Oveis Gharan and Saberi 2011] that there exists polynomial-time constant-factor approximations on planar graphs and more generally graphs of constant orientable genus. This result was extended to non-orientable genus by [Erickson and Sidiropoulos 2014]. We show that for any class of \emph{nearly-embeddable} graphs, ATSP admits a polynomial-time constant-factor approximation. More precisely, we show that for any fixed $k\geq 0$, there exist $α, β>0$, such that ATSP on $n$-vertex $k$-nearly-embeddable graphs admits a $α$-approximation in time $O(n^β)$. The class of $k$-nearly-embeddable graphs contains graphs with at most $k$ apices, $k$ vortices of width at most $k$, and an underlying surface of either orientable or non-orientable genus at most $k$. Prior to our work, even the case of graphs with a single apex was open. Our algorithm combines tools from rounding the Held-Karp LP via thin trees with dynamic programming. We complement our upper bounds by showing that solving ATSP exactly on graphs of pathwidth $k$ (and hence on $k$-nearly embeddable graphs) requires time $n^{Ω(k)}$, assuming the Exponential-Time Hypothesis (ETH). This is surprising in light of the fact that both TSP on undirected graphs and Minimum Cost Hamiltonian Cycle on directed graphs are FPT parameterized by treewidth.
Area Spectral Efficiency Analysis and Energy Consumption Minimization in Multi-Antenna Poisson Distributed Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper aims at answering two fundamental questions: how area spectral efficiency (ASE) behaves with different system parameters; how to design an energy-efficient network. Based on stochastic geometry, we obtain the expression and a tight lower-bound for ASE of Poisson distributed networks considering multi-user MIMO (MU-MIMO) transmission. With the help of the lower-bound, some interesting results are observed. These results are validated via numerical results for the original expression. We find that ASE can be viewed as a concave function with respect to the number of antennas and active users. For the purpose of maximizing ASE, we demonstrate that the optimal number of active users is a fixed portion of the number of antennas. With optimal number of active users, we observe that ASE increases linearly with the number of antennas. Another work of this paper is joint optimization of the base station (BS) density, the number of antennas and active users to minimize the network energy consumption. It is discovered that the optimal combination of the number of antennas and active users is the solution that maximizes the energy-efficiency. Besides the optimal algorithm, we propose a suboptimal algorithm to reduce the computational complexity, which can achieve near optimal performance.
On the Search Algorithm for the Output Distribution that Achieves the Channel Capacity
Venue: arXiv cs.IT 2016
Year: 2016

We consider a search algorithm for the output distribution that achieves the channel capacity of a discrete memoryless channel. We will propose an algorithm by iterated projections of an output distribution onto affine subspaces in the set of output distributions. The problem of channel capacity has a similar geometric structure as that of smallest enclosing circle for a finite number of points in the Euclidean space. The metric in the Euclidean space is the Euclidean distance and the metric in the space of output distributions is the Kullback-Leibler divergence. We consider these two problems based on Amari's $α$-geometry. Then, we first consider the smallest enclosing circle in the Euclidean space and develop an algorithm to find the center of the smallest enclosing circle. Based on the investigation, we will apply the obtained algorithm to the problem of channel capacity.
Stochastic Dykstra Algorithms for Metric Learning on Positive Semi-Definite Cone
Venue: arXiv cs.CV 2016
Year: 2016

Recently, covariance descriptors have received much attention as powerful representations of set of points. In this research, we present a new metric learning algorithm for covariance descriptors based on the Dykstra algorithm, in which the current solution is projected onto a half-space at each iteration, and runs at O(n^3) time. We empirically demonstrate that randomizing the order of half-spaces in our Dykstra-based algorithm significantly accelerates the convergence to the optimal solution. Furthermore, we show that our approach yields promising experimental results on pattern recognition tasks.
Analysis of Differential Synchronisation's Energy Consumption on Mobile Devices
Venue: arXiv cs.NI 2016
Year: 2016

Synchronisation algorithms are central to collaborative editing software. As collaboration is increasingly mediated by mobile devices, the energy efficiency for such algorithms is interest to a wide community of application developers. In this paper we explore the differential synchronisation (diffsync) algorithm with respect to energy consumption on mobile devices. Discussions within this paper are based on real usage data of PDF annotations via the Mendeley iOS app, which requires realtime synchronisation. We identify three areas for optimising diffsync: a.) Empty cycles in which no changes need to be processed b.) tail energy by adapting cycle intervals and c.) computational complexity. Following these considerations, we propose a push-based diffsync strategy in which synchronisation cycles are triggered when a device connects to the network or when a device is notified of changes.