OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
Venue: arXiv cs.CC 2018
Year: 2018

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetildeΩ(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions of the form $f\colon\{0,1\}^n\to \{0,1\}$: $\bullet$Tolerant $k$-junta testing with \emph{non-adaptive} queries requires $\widetildeΩ(k^2)$ queries. $\bullet$Tolerant unateness testing requires $\widetildeΩ(n)$ queries. $\bullet$Tolerant unateness testing with \emph{non-adaptive} queries requires $\widetildeΩ(n^{3/2})$ queries. Given the $\widetilde{O}(k^{3/2})$-query non-adaptive junta tester of Blais \cite{B08}, we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the $\widetilde{O}(n^{3/4})$-query unateness tester of Chen, Waingarten, and Xie \cite{CWX17b} and the $\widetilde{O}(n)$-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri \cite{BCPRS17}, we conclude that tolerant unateness testing requires more queries than non-tolerant unateness testing, in both adaptive and non-adaptive settings. These lower bounds provide the first separation between tolerant and non-tolerant testing for a natural property of Boolean functions.
LedgerGuard: Improving Blockchain Ledger Dependability
Venue: arXiv cs.DC 2018
Year: 2018

The rise of crypto-currencies has spawned great interest in their underlying technology, namely, Blockchain. The central component in a Blockchain is a shared distributed ledger. A ledger comprises series of blocks, which in turns contains a series of transactions. An identical copy of the ledger is stored on all nodes in a blockchain network. Maintaining ledger integrity and security is one of the crucial design aspects of any blockchain platform. Thus, there are typically built-in validation mechanisms leveraging cryptography to ensure the validity of incoming blocks before committing them into the ledger. However, a blockchain node may run over an extended period of time, during which the blocks on the disk can may become corrupted due to software or hardware failures, or due to malicious activity. This paper proposes LedgerGuard, a tool to maintain ledger integrity by detecting corrupted blocks and recovering these blocks by synchronizing with rest of the network. The experimental implementation of LedgerGuard is based on Hyperledger Fabric, which is a popular open source permissioned blockchain platform.
The feasibility of automated identification of six algae types using neural networks and fluorescence-based spectral-morphological features
Venue: arXiv cs.CV 2018
Year: 2018

Harmful algae blooms (HABs), which produce lethal toxins, are a growing global concern since they negatively affect the quality of drinking water and have major negative impact on wildlife, the fishing industry, as well as tourism and recreational water use. In this study, we investigate the feasibility of leveraging machine learning and fluorescence-based spectral-morphological features to enable the identification of six different algae types in an automated fashion. More specifically, a custom multi-band fluorescence imaging microscope is used to capture fluorescence imaging data of a water sample at six different excitation wavelengths ranging from 405 nm - 530 nm. A number of morphological and spectral fluorescence features are then extracted from the isolated micro-organism imaging data, and used to train neural network classification models designed for the purpose of identification of the six algae types given an isolated micro-organism. Experimental results using three different neural network classification models showed that the use of either fluorescence-based spectral features or fluorescence-based spectral-morphological features to train neural network classification models led to statistically significant improvements in identification accuracy when compared to the use of morphological features (with average identification accuracies of 95.7%+/-3.5% and 96.1%+/-1.5%, respectively). These preliminary results are quite promising, given that the identification accuracy of human taxonomists are typically between the range of 67% and 83%, and thus illustrates the feasibility of leveraging machine learning and fluorescence-based spectral-morphological features as a viable method for automated identification of different algae types.
A Robust Algorithm for Online Switched System Identification
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we consider the problem of online identification of Switched AutoRegressive eXogenous (SARX) systems, where the goal is to estimate the parameters of each subsystem and identify the switching sequence as data are obtained in a streaming fashion. Previous works in this area are sensitive to initialization and lack theoretical guarantees. We overcome these drawbacks with our two-step algorithm: (i) every time we receive new data, we first assign this data to one candidate subsystem based on a novel robust criterion that incorporates both the residual error and an upper bound of subsystem estimation error, and (ii) we use a randomized algorithm to update the parameter estimate of chosen candidate. We provide a theoretical guarantee on the local convergence of our algorithm. Though our theory only guarantees convergence with a good initialization, simulation results show that even with random initialization, our algorithm still has excellent performance. Finally, we show, through simulations, that our algorithm outperforms existing methods and exhibits robust performance.
Upper Bounds via Lamination on the Constrained Secrecy Capacity of Hypergraphical Sources
Venue: arXiv cs.IT 2018
Year: 2018

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this work, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree packing protocol.
Detecting Parkinson's Disease from interactions with a search engine: Is expert knowledge sufficient?
Venue: arXiv cs.IR 2018
Year: 2018

Parkinson's disease (PD) is a slowly progressing neurodegenerative disease with early manifestation of motor signs. Recently, there has been a growing interest in developing automatic tools that can assess motor function in PD patients. Here we show that mouse tracking data collected during people's interaction with a search engine can be used to distinguish PD patients from similar, non-diseased users and present a methodology developed for the diagnosis of PD from these data. A main challenge we address is the extraction of informative features from raw mouse tracking data. We do so in two complementary ways: First, we manually construct expert-recommended informative features, aiming to identify abnormalities in motor behaviors. Second, we use an unsupervised representation learning technique to map these raw data to high-level features. Using all the extracted features, a Random Forest classifier is then used to distinguish PD patients from controls, achieving an AUC of 0.92, while results using only expert-generated or auto-generated features are 0.87 and 0.83, respectively. Our results indicate that mouse tracking data can help in detecting users at early stages of the disease, and that both expert-generated features and unsupervised techniques for feature generation are required to achieve the best possible performance
Secure Routing with Power Optimization for Ad-hoc Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we consider the problem of joint secure routing and transmit power optimization for a multi-hop ad-hoc network under the existence of randomly distributed eavesdroppers following a Poisson point process (PPP). Secrecy messages are delivered from a source to a destination through a multi-hop route connected by multiple legitimate relays in the network. Our goal is to minimize the end-to-end connection outage probability (COP) under the constraint of a secrecy outage probability (SOP) threshold, by optimizing the routing path and the transmit power of each hop jointly. We show that the globally optimal solution could be obtained by a two-step procedure where the optimal transmit power has a closed-form and the optimal routing path can be found by Dijkstra's algorithm. Then a friendly jammer with multiple antennas is applied to enhance the secrecy performance further, and the optimal transmit power of the jammer and each hop of the selected route is investigated. This problem can be solved optimally via an iterative outer polyblock approximation with one-dimension search algorithm. Furthermore, suboptimal transmit powers can be derived using the successive convex approximation (SCA) method with a lower complexity. Simulation results show the performance improvement of the proposed algorithms for both non-jamming and jamming scenarios, and also reveal a non-trivial trade-off between the numbers of hops and the transmit power of each hop for secure routing.
Semantic segmentation of mFISH images using convolutional networks
Venue: arXiv cs.CV 2018
Year: 2018

Multicolor in situ hybridization (mFISH) is a karyotyping technique used to detect major chromosomal alterations using fluorescent probes and imaging techniques. Manual interpretation of mFISH images is a time consuming step that can be automated using machine learning; in previous works, pixel or patch wise classification was employed, overlooking spatial information which can help identify chromosomes. In this work, we propose a fully convolutional semantic segmentation network for the interpretation of mFISH images, which uses both spatial and spectral information to classify each pixel in an end-to-end fashion. The semantic segmentation network developed was tested on samples extracted from a public dataset using cross validation. Despite having no labeling information of the image it was tested on our algorithm yielded an average correct classification ratio (CCR) of 87.41%. Previously, this level of accuracy was only achieved with state of the art algorithms when classifying pixels from the same image in which the classifier has been trained. These results provide evidence that fully convolutional semantic segmentation networks may be employed in the computer aided diagnosis of genetic diseases with improved performance over the current methods of image analysis.
A Data-Aided Channel Estimation Scheme for Decoupled Systems in Heterogeneous Networks
Venue: arXiv cs.IT 2018
Year: 2018

Uplink/downlink (UL/DL) decoupling promises more flexible cell association and higher throughput in heterogeneous networks (HetNets), however, it hampers the acquisition of DL channel state information (CSI) in time-division-duplex (TDD) systems due to different base stations (BSs) connected in UL/DL. In this paper, we propose a novel data-aided (DA) channel estimation scheme to address this problem by utilizing decoded UL data to exploit CSI from received UL data signal in decoupled HetNets where a massive multiple-input multiple-output BS and dense small cell BSs are deployed. We analytically estimate BER performance of UL decoded data, which are used to derive an approximated normalized mean square error (NMSE) expression of the DA minimum mean square error (MMSE) estimator. Compared with the conventional least square (LS) and MMSE, it is shown that NMSE performances of all estimators are determined by their signal-to-noise ratio (SNR)-like terms and there is an increment consisting of UL data power, UL data length and BER values in the SNR-like term of DA method, which suggests DA method outperforms the conventional ones in any scenarios. Higher UL data power, longer UL data length and better BER performance lead to more accurate estimated channels with DA method. Numerical results verify that the analytical BER and NMSE results are close to the simulated ones and a remarkable gain in both NMSE and DL rate can be achieved by DA method in multiple scenarios with different modulations.
Smart contracts that are smart and can function as legal contracts - A Review of Semantic Blockchain and Distributed Ledger Technologies
Venue: arXiv cs.DC 2018
Year: 2018

Blockchain and Distributed ledger Technologies are increasingly becoming key enablers for vital innovation in financial services, manufacturing, government and other industries. One of the biggest challenges though is the level of support for semantics by most of the Block Chain and Distributed Ledger technologies. This paper reviews and categorises common block chain and DLT approaches and introduces a new approach to Blockchain / DLT promising to resolve the semantic problems inherent in other Blockchain / DLT approaches
Generation of Infra sound to replicate a wind turbine
Venue: arXiv cs.SD 2018
Year: 2018

We have successfully produced infrasound, as a duplicate of that produced by Industrial Wind Turbines. We have been able to produce this Infrasound inside a research chamber, capable of accommodating a human test subject. It is our vision that this project will permit others, with appropriate medical training and ethical oversight, to research human thresholds and the effects of this infrasound on humans. Our role has focused on producing the tools, systems, and hardware required, to permit this research to go forward. This paper describes the evolution of our project from the original vision, through the construction of proof of concept prototypes, a series of improved models and their associated accessories /operating systems, to the final test chamber as it stands now ready to deploy. Also included are the mathematical and computational data supporting our claim that infrasound conditions inside the chamber can be made to duplicate those from actual Industrial wind turbines at approved setback distances.
How to Secure Matchings Against Edge Failures
Venue: arXiv cs.DS 2018
Year: 2018

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum cost edge-set to the graph, such that the adversary never wins. We provide efficient exact and approximation algorithms. In particular, for the unit-cost problem, we provide a $\log_2 n$-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general non-negative weights we settle the approximability of the problem and show a close relation to the Directed Steiner Forest Problem. Additionally we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. Our methods rely on a close relationship to the classical strong connectivity augmentation problem and directed Steiner problems.
Noise constrained least mean absolute third algorithm
Venue: arXiv cs.SY 2018
Year: 2018

The learning speed of an adaptive algorithm can be improved by properly constraining the cost function of the adaptive algorithm. Besides, the stabilization of the NCLMF algorithm is more complicated, whose stability depends solely on the input power of the adaptive filter and the NCLMF algorithm with unbounded repressors is not mean square stability even for a small value of the step-size. So, in this paper, a noise variance constrained least mean absolute third (LMAT) algorithm is investigated. The noise constrained LMAT (NCLMAT) algorithm is obtained by constraining the cost function of the standard LMAT algorithm to the third-order moment of the additive noise. And it can eliminate a variety of non-Gaussian distribution of noise, such as Rayleigh noise, Binary noise and so on. The NCLMAT algorithm is a type of variable step-size LMAT algorithm where the step-size rule arises naturally from the constraints. The main aim of this work is first time to derive the NCLMAT adaptive algorithm, analyze its convergence behavior, mean square error (MSE), mean-square deviation (MSD) and assess its performance in different noise environments. Finally, the experimental results in system identification applications presented here illustrate the principle and efficiency of the NCLMAT algorithm.
How good are Popular Matchings?
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (MinBP) and minimum number of blocking residents (MinBR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi (ISAAC 2017) recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi's algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents. In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems.
Intense Competition can Drive Selfish Explorers to Optimize Coverage
Venue: arXiv cs.GT 2018
Year: 2018

We consider a game-theoretic setting in which selfish individuals compete over resources of varying quality. The motivating example is a group of animals that disperse over patches of food of different abundances. In such scenarios, individuals are biased towards selecting the higher quality patches, while, at the same time, aiming to avoid costly collisions or overlaps. Our goal is to investigate the impact of collision costs on the parallel coverage of resources by the whole group. Consider M sites, where a site x has value f(x). We think of f(x) as the reward associated with site x, and assume that if a single individual visits x exclusively, it receives this exact reward. Typically, we assume that if > 1 individuals visit x then each receives at most f(x). In particular, when competition costs are high, each individual might receive an amount strictly less than f(x), which could even be negative. Conversely, modeling cooperation at a site, we also consider cases where each one gets more than f(x). There are k identical players that compete over the rewards. They independently act in parallel, in a one-shot scenario, each specifying a single site to visit, without knowing which sites are explored by others. The group performance is evaluated by the expected coverage, defined as the sum of f(x) over all sites that are explored by at least one player. Since we assume that players cannot coordinate before choosing their site we focus on symmetric strategies. The main takeaway message of this paper is that the optimal symmetric coverage is expected to emerge when collision costs are relatively high, so that the following "Judgment of Solomon" type of rule holds: If a single player explores a site x then it gains its full reward f(x), but if several players explore it, then neither one receives any reward. Under this policy, it turns out that there exists a unique symmetric Nash Equilibrium strategy, which is, in fact, evolutionary stable. Moreover, this strategy yields the best possible coverage among all symmetric strategies. Viewing the coverage measure as the social welfare, this policy thus enjoys a (Symmetric) Price of Anarchy of precisely 1, whereas, in fact, any other congestion policy has a price strictly greater than 1. Our model falls within the scope of mechanism design, and more precisely in the area of incentivizing exploration. It finds relevance in evolutionary ecology, and further connects to studies on Bayesian parallel search algorithms.
What we learn from learning - Understanding capabilities and limitations of machine learning in botnet attacks
Venue: arXiv cs.CR 2018
Year: 2018

With a growing increase in botnet attacks, computer networks are constantly under threat from attacks that cripple cyber-infrastructure. Detecting these attacks in real-time proves to be a difficult and resource intensive task. One of the pertinent methods to detect such attacks is signature based detection using machine learning models. This paper explores the efficacy of these models at detecting botnet attacks, using data captured from large-scale network attacks. Our study provides a comprehensive overview of performance characteristics two machine learning models --- Random Forest and Multi-Layer Perceptron (Deep Learning) in such attack scenarios. Using Big Data analytics, the study explores the advantages, limitations, model/feature parameters, and overall performance of using machine learning in botnet attacks / communication. With insights gained from the analysis, this work recommends algorithms/models for specific attacks of botnets instead of a generalized model.
Open Source Development Around the World: A Comparative Study
Venue: arXiv cs.SE 2018
Year: 2018

Open source software has an increasing importance in our modern society, providing basic services to other software systems and also supporting the rapid development of a variety of end-user applications. Recently, world-wide code sharing platforms, like GitHub, are also contributing to open source's growth. However, little is known on how this growth is distributed around the world and about the characteristics of the projects developed in different countries. In this article, we provide a characterization of 2,648 open source projects developed in 20 countries. We reveal the number of projects per country, the popularity and programming language of each country's project and also show how the number of projects in a country correlates to its GDP. Finally, we assess the maintainability and internal code quality of the studied projects, using a tool called BetterCodeHub.