OpenRaiser/Intern-Atlas huggingface dataset:
Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling
Venue: arXiv cs.DS 2015
Year: 2015

We give a randomized $2^{n+o(n)}$-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic $\widetilde{O}(4^n)$-time and $\widetilde{O}(2^n)$-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample $2^{n/2}$ vectors from the discrete Gaussian distribution at any parameter in $2^{n+o(n)}$ time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. We also show that our DGS algorithm implies a $2^{n + o(n)}$-time algorithm that approximates the Closest Vector Problem to within a factor of $1.97$. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate $2^{n/2}$ discrete Gaussian samples in just $2^{n/2+o(n)}$ time and space. Among other things, this implies a $2^{n/2+o(n)}$-time and space algorithm for $1.93$-approximate decision SVP.
Fast, simple and accurate handwritten digit classification by training shallow neural network classifiers with the 'extreme learning machine' algorithm
Venue: arXiv cs.NE 2015
Year: 2015

Recent advances in training deep (multi-layer) architectures have inspired a renaissance in neural network use. For example, deep convolutional networks are becoming the default option for difficult tasks on large datasets, such as image and speech recognition. However, here we show that error rates below 1% on the MNIST handwritten digit benchmark can be replicated with shallow non-convolutional neural networks. This is achieved by training such networks using the 'Extreme Learning Machine' (ELM) approach, which also enables a very rapid training time (~10 minutes). Adding distortions, as is common practise for MNIST, reduces error rates even further. Our methods are also shown to be capable of achieving less than 5.5% error rates on the NORB image database. To achieve these results, we introduce several enhancements to the standard ELM algorithm, which individually and in combination can significantly improve performance. The main innovation is to ensure each hidden-unit operates only on a randomly sized and positioned patch of each image. This form of random `receptive field' sampling of the input ensures the input weight matrix is sparse, with about 90% of weights equal to zero. Furthermore, combining our methods with a small number of iterations of a single-batch backpropagation method can significantly reduce the number of hidden-units required to achieve a particular performance. Our close to state-of-the-art results for MNIST and NORB suggest that the ease of use and accuracy of the ELM algorithm for designing a single-hidden-layer neural network classifier should cause it to be given greater consideration either as a standalone method for simpler problems, or as the final classification stage in deep neural networks applied to more difficult problems.
Wireless Information and Energy Transfer for Decode-and-Forward Relaying MIMO-OFDM Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the system achievable rate and optimization for the multiple-input multiple-output (MIMO)-orthogonal frequency division multiplexing (OFDM) system with an energy harvesting (EH) relay. Firstly we propose a time switchingbased relaying (TSR) protocol to enable the simultaneous information processing and energy harvesting at the relay. Then, we discuss its achievable rate performance theoretically and formulated an optimization problem to maximize the system achievable rate. As the problem is difficult to solve, we design an Augmented Lagrangian Penalty Function (ALPF) method for it. Extensive simulation results are provided to demonstrate the accuracy of the analytical results and the effectiveness of the ALPF method.
Active Community Detection in Massive Graphs
Venue: arXiv cs.SI 2015
Year: 2015

A canonical problem in graph mining is the detection of dense communities. This problem is exacerbated for a graph with a large order and size -- the number of vertices and edges -- as many community detection algorithms scale poorly. In this work we propose a novel framework for detecting active communities that consist of the most active vertices in massive graphs. The framework is applicable to graphs having billions of vertices and hundreds of billions of edges. Our framework utilizes a parallelizable trimming algorithm based on a locality statistic to filter out inactive vertices, and then clusters the remaining active vertices via spectral decomposition on their similarity matrix. We demonstrate the validity of our method with synthetic Stochastic Block Model graphs, using Adjusted Rand Index as the performance metric. We further demonstrate its practicality and efficiency on a most recent real-world Hyperlink Web graph consisting of over 3.5 billion vertices and 128 billion edges.
On Randomized Algorithms for Matching in the Online Preemptive Model
Venue: arXiv cs.DS 2015
Year: 2015

We investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded. The complexity of the problem is settled for deterministic algorithms. Almost nothing is known for randomized algorithms. A lower bound of $1.693$ is known for MCM with a trivial upper bound of $2$. An upper bound of $5.356$ is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. For this class of (unweighted) graphs we present a randomized algorithm which is $\frac{28}{15}$-competitive. The analysis is a considerable extension of the (simple) primal-dual analysis for the deterministic case. The key new technique is that the distribution of primal charge to dual variables depends on the "neighborhood" and needs to be done after having seen the entire input. The assignment is asymmetric: in that edges may assign different charges to the two end-points. Also the proof depends on a non-trivial structural statement on the performance of the algorithm on the input tree. The other main result of this paper is an extension of the deterministic lower bound of Varadaraja to a natural class of randomized algorithms which decide whether to accept a new edge or not using independent random choices.
Achieving Non-Zero Information Velocity in Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

In wireless networks, where each node transmits independently of other nodes in the network (the ALOHA protocol), the expected delay experienced by a packet until it is successfully received at any other node is known to be infinite for signal-to-interference-plus-noise-ratio (SINR) model with node locations distributed according to a Poisson point process. Consequently, the information velocity, defined as the limit of the ratio of the distance to the destination and the time taken for a packet to successfully reach the destination over multiple hops, is zero, as the distance tends to infinity. A nearest neighbor distance based power control policy is proposed to show that the expected delay required for a packet to be successfully received at the nearest neighbor can be made finite. Moreover, the information velocity is also shown to be non-zero with the proposed power control policy. The condition under which these results hold does not depend on the intensity of the underlying Poisson point process.
Quantitative Function and Algorithm for Community Detection in Bipartite Networks
Venue: arXiv cs.SI 2015
Year: 2015

Community detection in complex networks is a topic of high interest in many fields. Bipartite networks are a special type of complex networks in which nodes are decomposed into two disjoint sets, and only nodes between the two sets can be connected. Bipartite networks represent diverse interaction patterns in many real-world systems, such as predator-prey networks, plant-pollinator networks, and drug-target networks. While community detection in unipartite networks has been extensively studied in the past decade, identification of modules or communities in bipartite networks is still in its early stage. Several quantitative functions proposed for evaluating the quality of bipartite network divisions are based on null models and have distinct resolution limits. In this paper, we propose a new quantitative function for community detection in bipartite networks, and demonstrate that this quantitative function is superior to the widely used Barber's bipartite modularity and other functions. Based on the new quantitative function, the bipartite network community detection problem is formulated into an integer programming model. Bipartite networks can be partitioned into reasonable overlapping communities by maximizing the quantitative function. We further develop a heuristic and adapted label propagation algorithm (BiLPA) to optimize the quantitative function in large-scale bipartite networks. BiLPA does not require any prior knowledge about the number of communities in the networks. We apply BiLPA to both artificial networks and real-world networks and demonstrate that this method can successfully identify the community structures of bipartite networks.
Computational Feasibility of Clustering under Clusterability Assumptions
Venue: arXiv cs.CC 2015
Year: 2015

It is well known that most of the common clustering objectives are NP-hard to optimize. In practice, however, clustering is being routinely carried out. One approach for providing theoretical understanding of this seeming discrepancy is to come up with notions of clusterability that distinguish realistically interesting input data from worst-case data sets. The hope is that there will be clustering algorithms that are provably efficient on such 'clusterable' instances. In other words, hope that "Clustering is difficult only when it does not matter" (CDNM thesis, for short). We believe that to some extent this may indeed be the case. This paper provides a survey of recent papers along this line of research and a critical evaluation their results. Our bottom line conclusion is that that CDNM thesis is still far from being formally substantiated. We start by discussing which requirements should be met in order to provide formal support the validity of the CDNM thesis. In particular, we list some implied requirements for notions of clusterability. We then examine existing results in view of those requirements and outline some research challenges and open questions.
Defining and composing big state machines
Venue: arXiv cs.FL 2015
Year: 2015

A sequence function alternative representation of state machines.
Self-Repairing Disk Arrays
Venue: arXiv cs.DC 2015
Year: 2015

As the prices of magnetic storage continue to decrease, the cost of replacing failed disks becomes increasingly dominated by the cost of the service call itself. We propose to eliminate these calls by building disk arrays that contain enough spare disks to operate without any human intervention during their whole lifetime. To evaluate the feasibility of this approach, we have simulated the behavior of two-dimensional disk arrays with n parity disks and n(n-1)/2 data disks under realistic failure and repair assumptions. Our conclusion is that having n(n+1)/2 spare disks is more than enough to achieve a 99.999 percent probability of not losing data over four years. We observe that the same objectives cannot be reached with RAID level 6 organizations and would require RAID stripes that could tolerate triple disk failures.
Department Management System for Departments of Sri Lankan Universities
Venue: arXiv cs.CY 2015
Year: 2015

This paper proposes a new method of data handling as well as implementation of management system for an academic department. Management system is a proven framework for managing and continually improving the organizations policies, procedures and processes. Department of Sri Lankan Universities is a division within a faculty comprising one subject area or a number of related subject areas. The time consumption and error rate of producing information is extremely high. This paper describes how to do the data handling in a department of Sri Lankan Universities using the management system. The efficiency of the management system measured with the amount of data handled by the department. Experiment results shows that this method of data handling increase the efficiency of the department in terms of processing information and the reduction of risks involved with the department activities.
Prioritized Random MAC Optimization via Graph-based Analysis
Venue: arXiv cs.IT 2015
Year: 2015

Motivated by the analogy between successive interference cancellation and iterative belief-propagation on erasure channels, irregular repetition slotted ALOHA (IRSA) strategies have received a lot of attention in the design of medium access control protocols. The IRSA schemes have been mostly analyzed for theoretical scenarios for homogenous sources, where they are shown to substantially improve the system performance compared to classical slotted ALOHA protocols. In this work, we consider generic systems where sources in different importance classes compete for a common channel. We propose a new prioritized IRSA algorithm and derive the probability to correctly resolve collisions for data from each source class. We then make use of our theoretical analysis to formulate a new optimization problem for selecting the transmission strategies of heterogenous sources. We optimize both the replication probability per class and the source rate per class, in such a way that the overall system utility is maximized. We then propose a heuristic-based algorithm for the selection of the transmission strategy, which is built on intrinsic characteristics of the iterative decoding methods adopted for recovering from collisions. Experimental results validate the accuracy of the theoretical study and show the gain of well-chosen prioritized transmission strategies for transmission of data from heterogenous classes over shared wireless channels.
Optimized Implementation of Memristor-Based Full Adder by Material Implication Logic
Venue: arXiv cs.ET 2015
Year: 2015

Recently memristor-based applications and circuits are receiving an increased attention. Furthermore, memristors are also applied in logic circuit design. Material implication logic is one of the main areas with memristors. In this paper an optimized memristor-based full adder design by material implication logic is presented. This design needs 27 memristors and less area in comparison with typical CMOS-based 8-bit full adders. Also the presented full adder needs only 184 computational steps which enhance former full adder design speed by 20 percent.
Outage Probability of Overhearing Amplify-and-Forward Cooperative Relaying
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the outage performance of overhearing amplify-and-forward (AF) cooperative relaying, where a source transmits information to its destination through multiple helping overhearing AF relays with space-time network coding (STNC) employed. Firstly, the transmission protocol of such a relaying system, i.e., cooperative relaying with overhearing AF relays based on STNC (STNC-OHAF) is presented. Then, the instantaneous end-to-end SNR expression of STNC-OHAF is analysed. Based on this, an explicit expression of the outage probability for STNC-OHAF over independent but not necessarily identically distributed (i.n.i.d) Rayleigh fading channels is theoretically derived. Numerical results validate our theoretical analysis and show that by introducing overhearing among relays, the outage performance of the system can be greatly improved. It also shows that there is a trade-off between system sum outage capacity and the transmitted number of symbols.
A New Method for Signal and Image Analysis: The Square Wave Method
Venue: arXiv cs.NA 2015
Year: 2015

A brief review is provided of the use of the Square Wave Method (SWM) in the field of signal and image analysis and it is specified how results thus obtained are expressed using the Square Wave Transform (SWT), in the frequency domain. To illustrate the new approach introduced in this field, the results of two cases are analyzed: a) a sequence of samples (that is, measured values) of an electromyographic recording; and b) the classic image of Lenna.
Detecting Malicious Content on Facebook
Venue: arXiv cs.SI 2015
Year: 2015

Online Social Networks (OSNs) witness a rise in user activity whenever an event takes place. Malicious entities exploit this spur in user-engagement levels to spread malicious content that compromises system reputation and degrades user experience. It also generates revenue from advertisements, clicks, etc. for the malicious entities. Facebook, the world's biggest social network, is no exception and has recently been reported to face much abuse through scams and other type of malicious content, especially during news making events. Recent studies have reported that spammers earn $200 million just by posting malicious links on Facebook. In this paper, we characterize malicious content posted on Facebook during 17 events, and discover that existing efforts to counter malicious content by Facebook are not able to stop all malicious content from entering the social graph. Our findings revealed that malicious entities tend to post content through web and third party applications while legitimate entities prefer mobile platforms to post content. In addition, we discovered a substantial amount of malicious content generated by Facebook pages. Through our observations, we propose an extensive feature set based on entity profile, textual content, metadata, and URL features to identify malicious content on Facebook in real time and at zero-hour. This feature set was used to train multiple machine learning models and achieved an accuracy of 86.9%. The intent is to catch malicious content that is currently evading Facebook's detection techniques. Our machine learning model was able to detect more than double the number of malicious posts as compared to existing malicious content detection techniques. Finally, we built a real world solution in the form of a REST based API and a browser plug-in to identify malicious Facebook posts in real time.
Two-Level Rectilinear Steiner Trees
Venue: arXiv cs.CG 2015
Year: 2015

Given a set $P$ of terminals in the plane and a partition of $P$ into $k$ subsets $P_1, ..., P_k$, a two-level rectilinear Steiner tree consists of a rectilinear Steiner tree $T_i$ connecting the terminals in each set $P_i$ ($i=1,...,k$) and a top-level tree $T_{top}$ connecting the trees $T_1, ..., T_k$. The goal is to minimize the total length of all trees. This problem arises naturally in the design of low-power physical implementations of parity functions on a computer chip. For bounded $k$ we present a polynomial time approximation scheme (PTAS) that is based on Arora's PTAS for rectilinear Steiner trees after lifting each partition into an extra dimension. For the general case we propose an algorithm that predetermines a connection point for each $T_i$ and $T_{top}$ ($i=1,...,k$). Then, we apply any approximation algorithm for minimum rectilinear Steiner trees in the plane to compute each $T_i$ and $T_{top}$ independently. This gives us a $2.37$-factor approximation with a running time of $\mathcal{O}(|P|\log|P|)$ suitable for fast practical computations. The approximation factor reduces to $1.63$ by applying Arora's approximation scheme in the plane.
Enhanced Slotted Aloha Mechanism by Introducing ZigZag Decoding
Venue: arXiv cs.IT 2015
Year: 2015

Various random access mechanisms, such as Aloha protocol and its corresponding variants have been widely studied as efficient methods to coordinate the medium access among competing users. But when two or more wireless users transmit packets at the same time over the same channel a collisions occur. When this happens, the received packets are discarded and retransmissions are required, which is a waste of power and bandwidth. In such a situation one of the most important objectives is to find techniques to improve these protocols to reduce the number of collisions or to avoid them. Several studies have contributed to this problem. In this paper, we propose a new approach named ZigZag decoding to enhance slotted Aloha mechanism by reducing the loss rate of packets colliding. We model the system by a Markov chain witch the number of backlogged packets is taken as the system state. We use a stochastic game to achieve our objective. We evaluate and compare the performances parameters of the proposed approach with those of slotted Aloha mechanism. All found results show that our approach is more efficient than the slotted Aloha mechanism.
Skincure: An Innovative Smart Phone-Based Application To Assist In Melanoma Early Detection And Prevention
Venue: arXiv cs.CV 2015
Year: 2015

Melanoma spreads through metastasis, and therefore it has been proven to be very fatal. Statistical evidence has revealed that the majority of deaths resulting from skin cancer are as a result of melanoma. Further investigations have shown that the survival rates in patients depend on the stage of the infection; early detection and intervention of melanoma implicates higher chances of cure. Clinical diagnosis and prognosis of melanoma is challenging since the processes are prone to misdiagnosis and inaccuracies due to doctors subjectivity. This paper proposes an innovative and fully functional smart-phone based application to assist in melanoma early detection and prevention. The application has two major components; the first component is a real-time alert to help users prevent skin burn caused by sunlight; a novel equation to compute the time for skin to burn is thereby introduced. The second component is an automated image analysis module which contains image acquisition, hair detection and exclusion, lesion segmentation, feature extraction, and classification. The proposed system exploits PH2 Dermoscopy image database from Pedro Hispano Hospital for development and testing purposes. The image database contains a total of 200 dermoscopy images of lesions, including normal, atypical, and melanoma cases. The experimental results show that the proposed system is efficient, achieving classification of the normal, atypical and melanoma images with accuracy of 96.3%, 95.7% and 97.5%, respectively.
Object localization in ImageNet by looking out of the window
Venue: arXiv cs.CV 2015
Year: 2015

We propose a method for annotating the location of objects in ImageNet. Traditionally, this is cast as an image window classification problem, where each window is considered independently and scored based on its appearance alone. Instead, we propose a method which scores each candidate window in the context of all other windows in the image, taking into account their similarity in appearance space as well as their spatial relations in the image plane. We devise a fast and exact procedure to optimize our scoring function over all candidate windows in an image, and we learn its parameters using structured output regression. We demonstrate on 92000 images from ImageNet that this significantly improves localization over recent techniques that score windows in isolation.