OpenRaiser/Intern-Atlas huggingface dataset:
A Decentralized Approach to Software-Defined Networks (SDNs)
Venue: arXiv cs.NI 2015
Year: 2015

Redistribution of the intelligence and management in the software defined networks (SDNs) is a potential approach to address the bottlenecks of scalability and integrity of these networks. We propose to revisit the routing concept based on the notion of regions. Using basic and consistent definition of regions, a region-based packet routing called SmartRegion Routing is presented. The flexibility of regions in terms of naming and addressing is then leveraged in the form of a region stack among other features placed in the associated packet header. In this way, most of complexity and dynamicity of a network is absorbed, and therefore highly fast and simplified routing at the inter-region level along with semi-autonomous intra-region routing will be feasible. In addition, multipath planning can be naturally realized at both inter and intra levels. A basic form of SmartRegion routing mechanism is provided. Simplicity, scalability, and manageability of the proposed approach would also bring future potentials to reduce energy consumption and environmental footprint associated to the SDNs. Finally, various applications, such as enabling seamless broadband access, providing beyond IP addressing mechanisms, and also address-equivalent naming mechanisms, are considered and discussed.
A Comparison of Approaches for Solving Hard Graph-Theoretic Problems
Venue: arXiv cs.DS 2015
Year: 2015

In order to formulate mathematical conjectures likely to be true, a number of base cases must be determined. However, many combinatorial problems are NP-hard and the computational complexity makes this research approach difficult using a standard brute force approach on a typical computer. One sample problem explored is that of finding a minimum identifying code. To work around the computational issues, a variety of methods are explored and consist of a parallel computing approach using Matlab, a quantum annealing approach using the D-Wave computer, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers. Each of these methods requires the problem to be formulated in a unique manner. In this paper, we address the challenges of computing solutions to this NP-hard problem with respect to each of these methods.
Fast R-CNN
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a Fast Region-based Convolutional Network method (Fast R-CNN) for object detection. Fast R-CNN builds on previous work to efficiently classify object proposals using deep convolutional networks. Compared to previous work, Fast R-CNN employs several innovations to improve training and testing speed while also increasing detection accuracy. Fast R-CNN trains the very deep VGG16 network 9x faster than R-CNN, is 213x faster at test-time, and achieves a higher mAP on PASCAL VOC 2012. Compared to SPPnet, Fast R-CNN trains VGG16 3x faster, tests 10x faster, and is more accurate. Fast R-CNN is implemented in Python and C++ (using Caffe) and is available under the open-source MIT License at https://github.com/rbgirshick/fast-rcnn.
Transparent Object Proxies for JavaScript
Venue: arXiv cs.PL 2015
Year: 2015

Proxies are the swiss army knives of object adaptation. They introduce a level of indirection to intercept select operations on a target object and divert them as method calls to a handler. Proxies have many uses like implementing access control, enforcing contracts, virtualizing resources. One important question in the design of a proxy API is whether a proxy object should inherit the identity of its target. Apparently proxies should have their own identity for security-related applications whereas other applications, in particular contract systems, require transparent proxies that compare equal to their target objects. We examine the issue with transparency in various use cases for proxies, discuss different approaches to obtain transparency, and propose two designs that require modest modifications in the JavaScript engine and cannot be bypassed by the programmer. We implement our designs in the SpiderMonkey JavaScript interpreter and bytecode compiler. Our evaluation shows that these modifications of have no statistically significant impact on the benchmark performance of the JavaScript engine. Furthermore, we demonstrate that contract systems based on wrappers require transparent proxies to avoid interference with program execution in realistic settings.
Average Convergence Rate of Evolutionary Algorithms
Venue: arXiv cs.NE 2015
Year: 2015

In evolutionary optimization, it is important to understand how fast evolutionary algorithms converge to the optimum per generation, or their convergence rate. This paper proposes a new measure of the convergence rate, called average convergence rate. It is a normalised geometric mean of the reduction ratio of the fitness difference per generation. The calculation of the average convergence rate is very simple and it is applicable for most evolutionary algorithms on both continuous and discrete optimization. A theoretical study of the average convergence rate is conducted for discrete optimization. Lower bounds on the average convergence rate are derived. The limit of the average convergence rate is analysed and then the asymptotic average convergence rate is proposed.
Texts in, meaning out: neural language models in semantic similarity task for Russian
Venue: arXiv cs.CL 2015
Year: 2015

Distributed vector representations for natural language vocabulary get a lot of attention in contemporary computational linguistics. This paper summarizes the experience of applying neural network language models to the task of calculating semantic similarity for Russian. The experiments were performed in the course of Russian Semantic Similarity Evaluation track, where our models took from the 2nd to the 5th position, depending on the task. We introduce the tools and corpora used, comment on the nature of the shared task and describe the achieved results. It was found out that Continuous Skip-gram and Continuous Bag-of-words models, previously successfully applied to English material, can be used for semantic modeling of Russian as well. Moreover, we show that texts in Russian National Corpus (RNC) provide an excellent training material for such models, outperforming other, much larger corpora. It is especially true for semantic relatedness tasks (although stacking models trained on larger corpora on top of RNC models improves performance even more). High-quality semantic vectors learned in such a way can be used in a variety of linguistic tasks and promise an exciting field for further study.
Rural Wireless Mesh Network: A Design Methodology
Venue: arXiv cs.NI 2015
Year: 2015

Wireless Mesh Network is presented as an appealing solution for bridging the digital divide between developed and under-developed regions. But the planning and deployment of these networks are not just a technical matter, since the success depends on many other factors tied to the related region. Although we observe some deployments, to ensure usefulness and sustainability, there is still a need of concrete design process model and proper network planning approach for rural regions, especially in Sub-Saharan Africa. This paper presents a design methodology to provide network connectivity from a landline node in a rural region at very low cost. We propose a methodology composed of ten steps, starting by a deep analysis of the region in order to identify relevant constraints and useful applications to sustain local activities and communication. Approach for planning the physical architecture of the network is based on an indoor-outdoor deployment for reducing the overall cost of the network.
Efficient Image-Space Extraction and Representation of 3D Surface Topography
Venue: arXiv cs.CV 2015
Year: 2015

Surface topography refers to the geometric micro-structure of a surface and defines its tactile characteristics (typically in the sub-millimeter range). High-resolution 3D scanning techniques developed recently enable the 3D reconstruction of surfaces including their surface topography. In his paper, we present an efficient image-space technique for the extraction of surface topography from high-resolution 3D reconstructions. Additionally, we filter noise and enhance topographic attributes to obtain an improved representation for subsequent topography classification. Comprehensive experiments show that the our representation captures well topographic attributes and significantly improves classification performance compared to alternative 2D and 3D representations.
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness
Venue: arXiv cs.CC 2015
Year: 2015

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-ε$, requires $n^{\tilde Ω(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an additive PTAS for Densest $k$-Subgraph. We further strengthen this result by showing that our lower bound continues to hold when, in the soundness case, even subgraphs smaller by a near-polynomial factor ($k' = k 2^{-\tilde Ω(log n)}$) are assumed to be at most ($1-ε$)-dense. Our reduction is inspired by recent applications of the "birthday repetition" technique [AIM14,BKW15]. Our analysis relies on information theoretical machinery and is similar in spirit to analyzing a parallel repetition of two-prover games in which the provers may choose to answer some challenges multiple times, while completely ignoring other challenges.
Transforming NP to P: An Approach to Solve NP Complete Problems
Venue: arXiv cs.CC 2015
Year: 2015

NP complete problem is one of the most challenging issues. The question of whether all problems in NP are also in P is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, computer science, biology, philosophy and cryptography. There are intensive research on proving `NP not equal to P' and `NP equals to P'. However, none of the `proved' results is commonly accepted by the research community up to now. In this paper, instead of proving either one, we aim to provide new perspective: transforming two typical NP complete problems to exactly solvable P problems in polynomial time. This approach helps to solve originally NP complete problems with practical applications. It may shine light on solving other NP complete problems in similar way.
Context-Free Language Theory Formalization
Venue: arXiv cs.FL 2015
Year: 2015

Proof assistants are software-based tools that are used in the mechanization of proof construction and validation in mathematics and computer science, and also in certified program development. Different tools are being increasingly used in order to accelerate and simplify proof checking. Context-free language theory is a well-established area of mathematics, relevant to computer science foundations and technology. This proposal aims at formalizing parts of context-free language theory in the Coq proof assistant. This report presents the underlying theory and general characteristics of proof assistants, including Coq itself, discusses its use in relevant formalization projects, presents the current status of the implementation, addresses related projects and the contributions of this work. The results obtained so far include the formalization of closure properties for context-free grammars (under union, concatenation and closure) and the formalization of grammar simplification. Grammar simplification is a subject of high importance in computer language processing technology as well as in formal language theory, and the formalization refers to the fact that general context-free grammars generate languages that can be also generated by simpler and equivalent context-free grammars. Namely, useless symbol elimination, inaccessible symbol elimination, unit rules elimination and empty rules elimination operations were described and proven correct with respect to the preservation of the language generated by the original grammar.
Multi-probe consistent hashing
Venue: arXiv cs.DS 2015
Year: 2015

We describe a consistent hashing algorithm which performs multiple lookups per key in a hash table of nodes. It requires no additional storage beyond the hash table, and achieves a peak-to-average load ratio of 1 + epsilon with just 1 + 1/epsilon lookups per key.
A Cooperative Framework for Fireworks Algorithm
Venue: arXiv cs.NE 2015
Year: 2015

This paper presents a cooperative framework for fireworks algorithm (CoFFWA). A detailed analysis of existing fireworks algorithm (FWA) and its recently developed variants has revealed that (i) the selection strategy lead to the contribution of the firework with the best fitness (core firework) for the optimization overwhelms the contributions of the rest of fireworks (non-core fireworks) in the explosion operator, (ii) the Gaussian mutation operator is not as effective as it is designed to be. To overcome these limitations, the CoFFWA is proposed, which can greatly enhance the exploitation ability of non-core fireworks by using independent selection operator and increase the exploration capacity by crowdness-avoiding cooperative strategy among the fireworks. Experimental results on the CEC2013 benchmark functions suggest that CoFFWA outperforms the state-of-the-art FWA variants, artificial bee colony, differential evolution, the standard particle swarm optimization (SPSO) in 2007 and the most recent SPSO in 2011 in term of convergence performance.
The Cross-Depiction Problem: Computer Vision Algorithms for Recognising Objects in Artwork and in Photographs
Venue: arXiv cs.CV 2015
Year: 2015

The cross-depiction problem is that of recognising visual objects regardless of whether they are photographed, painted, drawn, etc. It is a potentially significant yet under-researched problem. Emulating the remarkable human ability to recognise objects in an astonishingly wide variety of depictive forms is likely to advance both the foundations and the applications of Computer Vision. In this paper we benchmark classification, domain adaptation, and deep learning methods; demonstrating that none perform consistently well in the cross-depiction problem. Given the current interest in deep learning, the fact such methods exhibit the same behaviour as all but one other method: they show a significant fall in performance over inhomogeneous databases compared to their peak performance, which is always over data comprising photographs only. Rather, we find the methods that have strong models of spatial relations between parts tend to be more robust and therefore conclude that such information is important in modelling object classes regardless of appearance details.
Device-Relaying in Cellular D2D Networks: A Fairness Perspective
Venue: arXiv cs.IT 2015
Year: 2015

Device-to-Device (D2D) communication is envisioned to be an integral component of 5G networks, and a technique for meeting the demand for high data rates. In a cellular network, D2D allows not only direct communication between users, but also device relaying. In this paper, a simple instance of device-relaying is investigated, and the impact of D2D on fairness among users is studied. Namely, a cellular network consisting of two D2D-enabled users and a base-station (BS) is considered. Thus, the users who want to establish communication with the BS can act as relays for each other's signals. While this problem is traditionally considered in the literature as a multiple-access channel with cooperation in the uplink, and a broadcast channel with cooperation in the downlink, we propose a different treatment of the problem as a multi-way channel. A simple communication scheme is proposed, and is shown to achieve significant gain in terms of fairness (measured by the symmetric rate supported) in comparison to the aforementioned traditional treatment.
Joint Wireless Information and Power Transfer for an Autonomous Multiple Antenna Relay System
Venue: arXiv cs.IT 2015
Year: 2015

Considering a three-node multiple antenna relay system, this paper proposes a two-phase amplify-and-forward (AF) relaying protocol, which enables the autonomous relay to simultaneously harvest wireless power from the source information signal and from an energy signal conveyed by the destination. We first study this energy-flow-assisted (EFA) relaying in a single-input single-output (SISO) relay system and aim at maximizing the rate. By transforming the optimization problem into an equivalent convex form, a global optimum can be found. We then extend the protocol to a multiple antenna relay system. The relay processing matrix is optimized to maximize the rate. The optimization problem can be efficiently solved by eigenvalue decomposition, after linear algebra manipulation. It is observed that the benefits of the energy flow are interestingly shown only in the multiple antenna case, and it is revealed that the received information signal and the energy leakage at the relay can be nearly separated by making use of the signal space, such that the desired signal can be amplified with a larger coefficient.
SynthCam3D: Semantic Understanding With Synthetic Indoor Scenes
Venue: arXiv cs.CV 2015
Year: 2015

We are interested in automatic scene understanding from geometric cues. To this end, we aim to bring semantic segmentation in the loop of real-time reconstruction. Our semantic segmentation is built on a deep autoencoder stack trained exclusively on synthetic depth data generated from our novel 3D scene library, SynthCam3D. Importantly, our network is able to segment real world scenes without any noise modelling. We present encouraging preliminary results.
On Repeated-Root Constacyclic Codes of Length $2^amp^r$ over Finite Fields
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we investigate the structure of repeated root constacyclic codes of length $2^amp^r$ over $\mathbb{F}_{p^s}$ with $a\geq1$ and $(m,p)=1$. We characterize the codes in terms of their generator polynomials. This provides simple conditions on the existence of self-dual negacyclic codes. Further, we gave cases where the constacyclic codes are equivalent to cyclic codes.
A New Selection Operator for the Discrete Empirical Interpolation Method -- improved a priori error bound and extensions
Venue: arXiv cs.NA 2015
Year: 2015

This paper introduces a new framework for constructing the Discrete Empirical Interpolation Method DEIM projection operator. The interpolation node selection procedure is formulated using the QR factorization with column pivoting, and it enjoys a sharper error bound for the DEIM projection error. Furthermore, for a subspace $\mathcal{U}$ given as the range of an orthonormal $U$, the DEIM projection does not change if $U$ is replaced by $U Ω$ with arbitrary unitary matrix $Ω$. In a large-scale setting, the new approach allows modifications that use only randomly sampled rows of $U$, but with the potential of producing good approximations with corresponding probabilistic error bounds. Another salient feature of the new framework is that robust and efficient software implementation is easily developed, based on readily available high performance linear algebra packages.
Order-Revealing Encryption and the Hardness of Private Learning
Venue: arXiv cs.CR 2015
Year: 2015

An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient $(ε, δ)$-differentially private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially private. This answers a question of Kasiviswanathan et al. (FOCS '08, SIAM J. Comput. '11). To prove our result, we give a generic transformation from an order-revealing encryption scheme into one with strongly correct comparison, which enables the consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.
Electron Neutrino Classification in Liquid Argon Time Projection Chamber Detector
Venue: arXiv cs.CV 2015
Year: 2015

Neutrinos are one of the least known elementary particles. The detection of neutrinos is an extremely difficult task since they are affected only by weak sub-atomic force or gravity. Therefore large detectors are constructed to reveal neutrino's properties. Among them the Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for studying neutrinos. The computerized methods for automatic reconstruction and identification of particles are needed to fully exploit the potential of the LAr-TPC technique. Herein, the novel method for electron neutrino classification is presented. The method constructs a feature descriptor from images of observed event. It characterizes the signal distribution propagated from vertex of interest, where the particle interacts with the detector medium. The classifier is learned with a constructed feature descriptor to decide whether the images represent the electron neutrino or cascade produced by photons. The proposed approach assumes that the position of primary interaction vertex is known. The method's performance in dependency to the noise in a primary vertex position and deposited energy of particles is studied.
Some Theoretical Properties of a Network of Discretely Firing Neurons
Venue: arXiv cs.NE 2015
Year: 2015

The problem of optimising a network of discretely firing neurons is addressed. An objective function is introduced which measures the average number of bits that are needed for the network to encode its state. When this is minimised, it is shown that this leads to a number of results, such as topographic mappings, piecewise linear dependence on the input of the probability of a neuron firing, and factorial encoder networks.
A Gaussian Scale Space Approach For Exudates Detection, Classification And Severity Prediction
Venue: arXiv cs.CV 2015
Year: 2015

In the context of Computer Aided Diagnosis system for diabetic retinopathy, we present a novel method for detection of exudates and their classification for disease severity prediction. The method is based on Gaussian scale space based interest map and mathematical morphology. It makes use of support vector machine for classification and location information of the optic disc and the macula region for severity prediction. It can efficiently handle luminance variation and it is suitable for varied sized exudates. The method has been probed in publicly available DIARETDB1V2 and e-ophthaEX databases. For exudate detection the proposed method achieved a sensitivity of 96.54% and prediction of 98.35% in DIARETDB1V2 database.