OpenRaiser/Intern-Atlas huggingface dataset:
A Probabilistic Dependent Type System based on Non-Deterministic Beta Reduction
Venue: arXiv cs.LO 2016
Year: 2016

We introduce Probabilistic Dependent Type Systems (PDTS) via a functional language based on a subsystem of intuitionistic type theory including dependent sums and products, which is expanded to include stochastic functions. We provide a sampling-based semantics for the language based on non-deterministic beta reduction. Further, we derive a probabilistic logic from the PDTS introduced as a direct result of the Curry-Howard isomorphism. The probabilistic logic derived is shown to provide a universal representation for finite discrete distributions.
IOTSim: a Cloud based Simulator for Analysing IoT Applications
Venue: arXiv cs.DC 2016
Year: 2016

A disruptive technology that is influencing not only computing paradigm but every other business is the rise of big data. Internet of Things (IoT) applications are considered to be a major source of big data. Such IoT applications are in general supported through clouds where data is stored and processed by big data processing systems. In order to improve the efficiency of cloud infrastructure so that they can efficiently support IoT big data applications, it is important to understand how these applications and the corresponding big data processing systems will perform in cloud computing environments. However, given the scalability and complex requirements of big data processing systems, an empirical evaluation on actual cloud infrastructure can hinder the development of timely and cost effective IoT solutions. Therefore, a simulator supporting IoT applications in cloud environment is highly demanded, but such work is still in its infancy. To fill this gap, we have designed and implemented IOTSim which supports and enables simulation of IoT big data processing using MapReduce model in cloud computing environment. A real case study validates the efficacy of the simulator.
Some Proof Derivations and Further Simulation Results for "Semidefinite Relaxation and Approximation Analysis of a Beamformed Alamouti Scheme for Relay Beamforming Networks"
Venue: arXiv cs.IT 2016
Year: 2016

This is a companion technical report of the main manuscript "Semidefinite Relaxation and Approximation Analysis of a Beamformed Alamouti Scheme for Relay Beamforming Networks". The report serves to give detailed derivations of Lemma 1-2 in the main manuscript, which are too long to be included in the latter. In addition, more simulation results are presented to verify the viability of the BF Alamouti AF schemes developed in the main manuscript.
The need for effective information security awareness practices in Oman higher educational institutions
Venue: arXiv cs.CR 2016
Year: 2016

The revolution of internet technology and its usage have led a significant increase in the number of online transactions and electronic data transfer, parallely increased the number of cybercrime incidents around the world. Steady economic growth in the Sultanate of Oman accelerated the volume of online utilization for e-commerce, banking, communication, education and so forth. Normally attackers target the users who ignore security practices due to the lack of information security awareness. Unawareness of information security practices, user negligence, lack of awareness programs and trainings are the root cause for information security threats. Earlier studies reveal there is a considerable and continuous cybercrime incident in Oman which compromises the security policy of the organizations, affecting the business continuity and the economic growth. In this study, a survey was performed among the educational institutions in Oman to investigate the level of information security awareness and based on the study, a security awareness model is proposed to enable information security practices in the educational institutions.
Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Venue: arXiv cs.CC 2016
Year: 2016

The Sensitivity Conjecture and the Log-rank Conjecture are among the most important and challenging problems in concrete complexity. Incidentally, the Sensitivity Conjecture is known to hold for monotone functions, and so is the Log-rank Conjecture for $f(x \wedge y)$ and $f(x\oplus y)$ with monotone functions $f$, where $\wedge$ and $\oplus$ are bit-wise AND and XOR, respectively. In this paper, we extend these results to functions $f$ which alternate values for a relatively small number of times on any monotone path from $0^n$ to $1^n$. These deepen our understandings of the two conjectures, and contribute to the recent line of research on functions with small alternating numbers.
Analysis of Multiple Flows using Different High Speed TCP protocols on a General Network
Venue: arXiv cs.NI 2016
Year: 2016

We develop analytical tools for performance analysis of multiple TCP flows (which could be using TCP CUBIC, TCP Compound, TCP New Reno) passing through a multi-hop network. We first compute average window size for a single TCP connection (using CUBIC or Compound TCP) under random losses. We then consider two techniques to compute steady state throughput for different TCP flows in a multi-hop network. In the first technique, we approximate the queues as M/G/1 queues. In the second technique, we use an optimization program whose solution approximates the steady state throughput of the different flows. Our results match well with ns2 simulations.
An Effective and Efficient Approach for Clusterability Evaluation
Venue: arXiv cs.LG 2016
Year: 2016

Clustering is an essential data mining tool that aims to discover inherent cluster structure in data. As such, the study of clusterability, which evaluates whether data possesses such structure, is an integral part of cluster analysis. Yet, despite their central role in the theory and application of clustering, current notions of clusterability fall short in two crucial aspects that render them impractical; most are computationally infeasible and others fail to classify the structure of real datasets. In this paper, we propose a novel approach to clusterability evaluation that is both computationally efficient and successfully captures the structure of real data. Our method applies multimodality tests to the (one-dimensional) set of pairwise distances based on the original, potentially high-dimensional data. We present extensive analyses of our approach for both the Dip and Silverman multimodality tests on real data as well as 17,000 simulations, demonstrating the success of our approach as the first practical notion of clusterability.
Erasure Schemes Using Generalized Polar Codes: Zero-Undetected-Error Capacity and Performance Trade-offs
Venue: arXiv cs.IT 2016
Year: 2016

We study the performance of generalized polar (GP) codes when they are used for coding schemes involving erasure. GP codes are a family of codes which contains, among others, the standard polar codes of Arıkan and Reed-Muller codes. We derive a closed formula for the zero-undetected-error capacity $I_0^{GP}(W)$ of GP codes for a given binary memoryless symmetric (BMS) channel $W$ under the low complexity successive cancellation decoder with erasure. We show that for every $R<I_0^{GP}(W)$, there exists a generalized polar code of blocklength $N$ and of rate at least $R$ where the undetected-error probability is zero and the erasure probability is less than $2^{-N^{\frac{1}{2}-ε}}$. On the other hand, for any GP code of rate $I_0^{GP}(W)<R<I(W)$ and blocklength $N$, the undetected error probability cannot be made less than $2^{-N^{\frac{1}{2}+ε}}$ unless the erasure probability is close to $1$.
Optimal Mode Selection in D2D-Enabled Multi-Base Station Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider device-to-device (D2D) communication underlaying uplink cellular networks with multiple base stations (BSs), where each user can switch between traditional cellular mode (through BS) and D2D mode (by connecting proximity user), namely mode selection. We impose load balancing constraints on BSs to efficient resource usage. The joint problem of mode selection and user association is formulated as a combinatorial problem and NP-complete. We adopt a graph-based approach to solve the problem globally optimally in polynomial time. To further reduce complexity, we also propose a distributed algorithm based on dual method. We show that the proposed distributed algorithm achieves nearly the same performance as the proposed optimal graph based algorithm.
Graph Regularized Low Rank Representation for Aerosol Optical Depth Retrieval
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we propose a novel data-driven regression model for aerosol optical depth (AOD) retrieval. First, we adopt a low rank representation (LRR) model to learn a powerful representation of the spectral response. Then, graph regularization is incorporated into the LRR model to capture the local structure information and the nonlinear property of the remote-sensing data. Since it is easy to acquire the rich satellite-retrieval results, we use them as a baseline to construct the graph. Finally, the learned feature representation is feeded into support vector machine (SVM) to retrieve AOD. Experiments are conducted on two widely used data sets acquired by different sensors, and the experimental results show that the proposed method can achieve superior performance compared to the physical models and other state-of-the-art empirical models.
Codes Correcting a Burst of Deletions or Insertions
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies codes that correct bursts of deletions. Namely, a code will be called a $b$-burst-deletion-correcting code if it can correct a deletion of any $b$ consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically $\log(n)+b-1$, the redundancy of the best code construction by Cheng et al. is $b(\log (n/b+1))$. In this paper we close on this gap and provide codes with redundancy at most $\log(n) + (b-1)\log(\log(n)) +b -\log(b)$. We also derive a non-asymptotic upper bound on the size of $b$-burst-deletion-correcting codes and extend the burst deletion model to two more cases: 1) A deletion burst of at most $b$ consecutive bits and 2) A deletion burst of size at most $b$ (not necessarily consecutive). We extend our code construction for the first case and study the second case for $b=3,4$. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.
Structured illumination microscopy image reconstruction algorithm
Venue: arXiv cs.CV 2016
Year: 2016

Structured illumination microscopy (SIM) is a very important super-resolution microscopy technique, which provides high speed super-resolution with about two-fold spatial resolution enhancement. Several attempts aimed at improving the performance of SIM reconstruction algorithm have been reported. However, most of these highlight only one specific aspect of the SIM reconstruction -- such as the determination of the illumination pattern phase shift accurately -- whereas other key elements -- such as determination of modulation factor, estimation of object power spectrum, Wiener filtering frequency components with inclusion of object power spectrum information, translocating and the merging of the overlapping frequency components -- are usually glossed over superficially. In addition, most of the work reported lie scattered throughout the literature and a comprehensive review of the theoretical background is found lacking. The purpose of the present work is two-fold: 1) to collect the essential theoretical details of SIM algorithm at one place, thereby making them readily accessible to readers for the first time; and 2) to provide an open source SIM reconstruction code (named OpenSIM), which enables users to interactively vary the code parameters and study it's effect on reconstructed SIM image.
Complexity of Manipulating Sequential Allocation
Venue: arXiv cs.GT 2016
Year: 2016

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns and each agents gets the most preferred item that is still available. It has long been known that sequential allocation is not strategyproof. Bouveret and Lang (2014) presented a polynomial-time algorithm to compute a best response of an agent with respect to additively separable utilities and claimed that (1) their algorithm correctly finds a best response, and (2) each best response results in the same allocation for the manipulator. We show that both claims are false via an example. We then show that in fact the problem of computing a best response is NP-complete. On the other hand, the insights and results of Bouveret and Lang (2014) for the case of two agents still hold.
Computer Aided Restoration of Handwritten Character Strokes
Venue: arXiv cs.GR 2016
Year: 2016

This work suggests a new variational approach to the task of computer aided restoration of incomplete characters, residing in a highly noisy document. We model character strokes as the movement of a pen with a varying radius. Following this model, a cubic spline representation is being utilized to perform gradient descent steps, while maintaining interpolation at some initial (manually sampled) points. The proposed algorithm was utilized in the process of restoring approximately 1000 ancient Hebrew characters (dating to ca. 8th-7th century BCE), some of which are presented herein and show that the algorithm yields plausible results when applied on deteriorated documents.
Multipath streaming: fundamental limits and efficient algorithms
Venue: arXiv cs.NI 2016
Year: 2016

We investigate streaming over multiple links. A file is split into small units called chunks that may be requested on the various links according to some policy, and received after some random delay. After a start-up time called pre-buffering time, received chunks are played at a fixed speed. There is starvation if the chunk to be played has not yet arrived. We provide lower bounds (fundamental limits) on the starvation probability of any policy. We further propose simple, order-optimal policies that require no feedback. For general delay distributions, we provide tractable upper bounds for the starvation probability of the proposed policies, allowing to select the pre-buffering time appropriately. We specialize our results to: (i) links that employ CSMA or opportunistic scheduling at the packet level, (ii) links shared with a primary user (iii) links that use fair rate sharing at the flow level. We consider a generic model so that our results give insight into the design and performance of media streaming over (a) wired networks with several paths between the source and destination, (b) wireless networks featuring spectrum aggregation and (c) multi-homed wireless networks.
Car Type Recognition with Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we study automatic recognition of cars of four types: Bus, Truck, Van and Small car. For this problem we consider two data driven frameworks: a deep neural network and a support vector machine using SIFT features. The accuracy of the methods is validated with a database of over 6500 images, and the resulting prediction accuracy is over 97 %. This clearly exceeds the accuracies of earlier studies that use manually engineered feature extraction pipelines.
Corrections to A Menagerie of Timed Automata
Venue: arXiv cs.FL 2016
Year: 2016

This note corrects a technical error in the ACM Computing Surveys paper mentioned in the title. The flaw involved constructions for showing that timed automata with urgent locations have the same expressiveness as timed automata that allow false location invariants. Corrected con- structions are presented in this note, and the affected results are reproved.
Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers
Venue: arXiv cs.CG 2016
Year: 2016

The d-dimensional Catalan numbers form a well-known sequence of numbers which count balanced bracket expressions over an alphabet of size d. In this paper, we introduce and study what we call d-dimensional prime Catalan numbers, a sequence of numbers which count only a very specific subset of indecomposable balanced bracket expressions. We further introduce the notion of a trapezoidal diagram of a crossing-free geometric graph, such as a triangulation or a crossing-free perfect matching. In essence, such a diagram is obtained by augmenting the geometric graph in question with its trapezoidal decomposition, and then forgetting about the precise coordinates of individual vertices while preserving the vertical visibility relations between vertices and segments. We note that trapezoidal diagrams of triangulations are closely related to abstract upward triangulations. We study the numbers of such diagrams in the cases of (i) perfect matchings and (ii) triangulations. We give bijective proofs which establish relations with 3-dimensional (prime) Catalan numbers. This allows us to determine the corresponding exponential growth rates exactly as (i) 5.196^n and (ii) 23.459^n (bases are rounded to 3 decimal places). Finally, we give lower bounds for the maximum number of embeddings of a trapezoidal diagram on any given point set.
Approximate Hamming distance in a stream
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of computing a $(1+ε)$-approximation of the Hamming distance between a pattern of length $n$ and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem, giving Alice the first half of the stream and Bob the second half. We show the following: (1) If Alice and Bob both share the pattern then there is an $O(ε^{-4} \log^2 n)$ bit randomised one-way communication protocol. (2) If only Alice has the pattern then there is an $O(ε^{-2}\sqrt{n}\log n)$ bit randomised one-way communication protocol. We then go on to develop small space streaming algorithms for $(1+ε)$-approximate Hamming distance which give worst case running time guarantees per arriving symbol. (1) For binary input alphabets there is an $O(ε^{-3} \sqrt{n} \log^{2} n)$ space and $O(ε^{-2} \log{n})$ time streaming $(1+ε)$-approximate Hamming distance algorithm. (2) For general input alphabets there is an $O(ε^{-5} \sqrt{n} \log^{4} n)$ space and $O(ε^{-4} \log^3 {n})$ time streaming $(1+ε)$-approximate Hamming distance algorithm.
Computing Pretropisms for the Cyclic n-Roots Problem
Venue: arXiv cs.CG 2016
Year: 2016

The cyclic n-roots problem is an important benchmark problem for polynomial system solvers. We consider the pruning of cone intersections for a polyhedral method to compute series for the solution curves.
On Study of the Binarized Deep Neural Network for Image Classification
Venue: arXiv cs.NE 2016
Year: 2016

Recently, the deep neural network (derived from the artificial neural network) has attracted many researchers' attention by its outstanding performance. However, since this network requires high-performance GPUs and large storage, it is very hard to use it on individual devices. In order to improve the deep neural network, many trials have been made by refining the network structure or training strategy. Unlike those trials, in this paper, we focused on the basic propagation function of the artificial neural network and proposed the binarized deep neural network. This network is a pure binary system, in which all the values and calculations are binarized. As a result, our network can save a lot of computational resource and storage. Therefore, it is possible to use it on various devices. Moreover, the experimental results proved the feasibility of the proposed network.
The Myopia of Crowds: A Study of Collective Evaluation on Stack Exchange
Venue: arXiv cs.HC 2016
Year: 2016

Crowds can often make better decisions than individuals or small groups of experts by leveraging their ability to aggregate diverse information. Question answering sites, such as Stack Exchange, rely on the "wisdom of crowds" effect to identify the best answers to questions asked by users. We analyze data from 250 communities on the Stack Exchange network to pinpoint factors affecting which answers are chosen as the best answers. Our results suggest that, rather than evaluate all available answers to a question, users rely on simple cognitive heuristics to choose an answer to vote for or accept. These cognitive heuristics are linked to an answer's salience, such as the order in which it is listed and how much screen space it occupies. While askers appear to depend more on heuristics, compared to voting users, when choosing an answer to accept as the most helpful one, voters use acceptance itself as a heuristic: they are more likely to choose the answer after it is accepted than before that very same answer was accepted. These heuristics become more important in explaining and predicting behavior as the number of available answers increases. Our findings suggest that crowd judgments may become less reliable as the number of answers grow.
Spectral Efficiency of MIMO Millimeter-Wave Links with Single-Carrier Modulation for 5G Networks
Venue: arXiv cs.IT 2016
Year: 2016

Future wireless networks will extensively rely upon bandwidths centered on carrier frequencies larger than 10GHz. Indeed, recent research has shown that, despite the large path-loss, millimeter wave (mmWave) frequencies can be successfully exploited to transmit very large data-rates over short distances to slowly moving users. Due to hardware complexity and cost constraints, single-carrier modulation schemes, as opposed to the popular multi-carrier schemes, are being considered for use at mmWave frequencies. This paper presents preliminary studies on the achievable spectral efficiency on a wireless MIMO link operating at mmWave in a typical 5G scenario. Two different single-carrier modem schemes are considered, i.e. a traditional modulation scheme with linear equalization at the receiver, and a single-carrier modulation with cyclic prefix, frequency-domain equalization and FFT-based processing at the receiver. Our results show that the former achieves a larger spectral efficiency than the latter. Results also confirm that the spectral efficiency increases with the dimension of the antenna array, as well as that performance gets severely degraded when the link length exceeds 100 meters and the transmit power falls below 0dBW. Nonetheless, mmWave appear to be very suited for providing very large data-rates over short distances.