OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Property Testing for Subgraph-Freeness Revisited
Venue: arXiv cs.DS 2017
Year: 2017

In the subgraph-freeness problem, we are given a constant-size graph $H$, and wish to determine whether the network contains $H$ as a subgraph or not. The \emph{property-testing} relaxation of the problem only requires us to distinguish graphs that are $H$-free from graphs that are $ε$-far from $H$-free, meaning an $ε$-fraction of their edges must be removed to obtain an $H$-free graph. Recently, Censor-Hillel et. al. and Fraigniaud et al. showed that in the property-testing regime it is possible to test $H$-freeness for any graph $H$ of size 4 in constant time, $O(1/ε^2)$ rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs $H$ of size 4 cannot test $5$-cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that $5$-cycle-freeness, and indeed $H$-freeness for many other graphs $H$ comprising more than 4 vertices, can be tested in constant time. We show that $C_k$-freeness can be tested in $O(1/ε)$ rounds for any cycle $C_k$, improving on the running time of $O(1/ε^2)$ of the previous algorithms for triangle-freeness and $C_4$-freeness. In the special case of triangles, we show that triangle-freeness can be solved in $O(1)$ rounds independently of $ε$, when $ε$ is not too small with respect to the number of nodes and edges. We also show that $T$-freeness for any constant-size tree $T$ can be tested in $O(1)$ rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in $O(1/ε)$ rounds. This class includes all graphs over 5 vertices except the 5-clique, $K_5$. For cliques $K_s$ over $s \geq 3$ nodes, we show that $K_s$-freeness can be tested in $O(m^{1/2-1/(s-2)}/ε^{1/2+1/(s-2)})$ rounds, where $m$ is the number of edges.
Phaseless compressive sensing using partial support information
Venue: arXiv cs.IT 2017
Year: 2017

We study the recovery conditions of weighted $\ell_1$ minimization for real-valued signal reconstruction from phaseless compressive sensing measurements when partial support information is available. A strong restricted isometry property condition is provided to ensure the stable recovery. Moreover, we present the weighted null space property as the sufficient and necessary condition for the success of $k$-sparse phaseless recovery via weighted $\ell_1$ minimization. Numerical experiments are conducted to illustrate our results.
Synthesis and Optimization of Multi-Objective Multi-Output QCA Circuit using Genetic Algorithm
Venue: arXiv cs.ET 2017
Year: 2017

The physical limitations of CMOS technology triggered several research for finding an alternative technology. QCA is one of the emerging nanotechnologies which is gaining attention as a substitute of CMOS. The main potential of QCA is its ultra low power consumption, less area overhead, and high speed. Majority and inverter gates are the basic gates in QCA,which together works as a universal logic gate to implement any QCA circuit. This paper proposes an efficient methodology for optimal QCA circuit synthesis of arbitrary multi-output boolean functions. A multi-objective genetic algorithm based approach is used to reduce worst case delay and gate count of a QCA circuit. Different importance is given to worst case delay, no. of majority and no. of inverter gates. Several efficient techniques are used in order to achieve the optimal result and reduce the computational complexity furthermore additional methodologies are used to eliminate redundancies from the final solution. Comparison of the obtained results with the existing best techniques indicates, the proposed technique outperforms in terms of worst case delay and gate count.
Joint Spectrum Allocation and Structure Optimization in Green Powered Heterogeneous Cognitive Radio Networks
Venue: arXiv cs.NI 2017
Year: 2017

We aim at maximizing the sum rate of secondary users (SUs) in OFDM-based Heterogeneous Cognitive Radio (CR) Networks using RF energy harvesting. Assuming SUs operate in a time switching fashion, each time slot is partitioned into three non-overlapping parts devoted for energy harvesting, spectrum sensing and data transmission. The general problem of joint resource allocation and structure optimization is formulated as a Mixed Integer Nonlinear Programming task which is NP-hard and intractable. Thus, we propose to tackle it by decomposing it into two subproblems. We first propose a sub-channel allocation scheme to approximately satisfy SUs' rate requirements and remove the integer constraints. For the second step, we prove that the general optimization problem is reduced to a convex optimization task. Considering the trade-off among fractions of each time slot, we focus on optimizing the time slot structures of SUs that maximize the total throughput while guaranteeing the rate requirements of both real-time and non-real-time SUs. Since the reduced optimization problem does not have a simple closed-form solution, we thus propose a near optimal closed-form solution by utilizing Lambert-W function. We also exploit iterative gradient method based on Lagrangian dual decomposition to achieve near optimal solutions. Simulation results are presented to validate the optimality of the proposed schemes.
Negative Results in Computer Vision: A Perspective
Venue: arXiv cs.CV 2017
Year: 2017

A negative result is when the outcome of an experiment or a model is not what is expected or when a hypothesis does not hold. Despite being often overlooked in the scientific community, negative results are results and they carry value. While this topic has been extensively discussed in other fields such as social sciences and biosciences, less attention has been paid to it in the computer vision community. The unique characteristics of computer vision, particularly its experimental aspect, call for a special treatment of this matter. In this paper, I will address what makes negative results important, how they should be disseminated and incentivized, and what lessons can be learned from cognitive vision research in this regard. Further, I will discuss issues such as computer vision and human vision interaction, experimental design and statistical hypothesis testing, explanatory versus predictive modeling, performance evaluation, model comparison, as well as computer vision research culture.
Adaptive Feature Representation for Visual Tracking
Venue: arXiv cs.CV 2017
Year: 2017

Robust feature representation plays significant role in visual tracking. However, it remains a challenging issue, since many factors may affect the experimental performance. The existing method which combine different features by setting them equally with the fixed weight could hardly solve the issues, due to the different statistical properties of different features across various of scenarios and attributes. In this paper, by exploiting the internal relationship among these features, we develop a robust method to construct a more stable feature representation. More specifically, we utilize a co-training paradigm to formulate the intrinsic complementary information of multi-feature template into the efficient correlation filter framework. We test our approach on challenging se- quences with illumination variation, scale variation, deformation etc. Experimental results demonstrate that the proposed method outperforms state-of-the-art methods favorably.
Self-Committee Approach for Image Restoration Problems using Convolutional Neural Network
Venue: arXiv cs.CV 2017
Year: 2017

There have been many discriminative learning methods using convolutional neural networks (CNN) for several image restoration problems, which learn the mapping function from a degraded input to the clean output. In this letter, we propose a self-committee method that can find enhanced restoration results from the multiple trial of a trained CNN with different but related inputs. Specifically, it is noted that the CNN sometimes finds different mapping functions when the input is transformed by a reversible transform and thus produces different but related outputs with the original. Hence averaging the outputs for several different transformed inputs can enhance the results as evidenced by the network committee methods. Unlike the conventional committee approaches that require several networks, the proposed method needs only a single network. Experimental results show that adding an additional transform as a committee always brings additional gain on image denoising and single image supre-resolution problems.
Sprinkler: Maximizing Resource Utilization in Many-Chip Solid State Disks
Venue: arXiv cs.AR 2017
Year: 2017

Resource utilization is one of the emerging problems in many-chip SSDs. In this paper, we propose Sprinkler, a novel device-level SSD controller, which targets maximizing resource utilization and achieving high performance without additional NAND flash chips. Specifically, Sprinkler relaxes parallelism dependency by scheduling I/O requests based on internal resource layout rather than the order imposed by the device-level queue. In addition, Sprinkler improves flash-level parallelism and reduces the number of transactions (i.e., improves transactional-locality) by over-committing flash memory requests to specific resources. Our extensive experimental evaluation using a cycle-accurate large-scale SSD simulation framework shows that a many-chip SSD equipped with our Sprinkler provides at least 56.6% shorter latency and 1.8 ~ 2.2 times better throughput than the state-of-the-art SSD controllers. Further, it improves overall resource utilization by 68.8% under different I/O request patterns and provides, on average, 80.2% more flash-level parallelism by reducing half of the flash memory requests at runtime.
A Formal Characterization of the Local Search Topology of the Gap Heuristic
Venue: arXiv cs.AI 2017
Year: 2017

The pancake puzzle is a classic optimization problem that has become a standard benchmark for heuristic search algorithms. In this paper, we provide full proofs regarding the local search topology of the gap heuristic for the pancake puzzle. First, we show that in any non-goal state in which there is no move that will decrease the number of gaps, there is a move that will keep the number of gaps constant. We then classify any state in which the number of gaps cannot be decreased in a single action into two groups: those requiring 2 actions to decrease the number of gaps, and those which require 3 actions to decrease the number of gaps.
Intensionality, Definability and Computation
Venue: arXiv cs.LO 2017
Year: 2017

We look at intensionality from the perspective of computation. In particular, we review how game semantics has been used to characterize the sequential functional processes, leading to powerful and flexible methods for constructing fully abstract models of programming languages, with applications in program analysis and verification. In a broader context, we can regard game semantics as a first step towards developing a positive theory of intensional structures with a robust mathematical structure, and finding the right notions of invariance for these structures.
Gabor Filter Assisted Energy Efficient Fast Learning Convolutional Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

Convolutional Neural Networks (CNN) are being increasingly used in computer vision for a wide range of classification and recognition problems. However, training these large networks demands high computational time and energy requirements; hence, their energy-efficient implementation is of great interest. In this work, we reduce the training complexity of CNNs by replacing certain weight kernels of a CNN with Gabor filters. The convolutional layers use the Gabor filters as fixed weight kernels, which extracts intrinsic features, with regular trainable weight kernels. This combination creates a balanced system that gives better training performance in terms of energy and time, compared to the standalone CNN (without any Gabor kernels), in exchange for tolerable accuracy degradation. We show that the accuracy degradation can be mitigated by partially training the Gabor kernels, for a small fraction of the total training cycles. We evaluated the proposed approach on 4 benchmark applications. Simple tasks like face detection and character recognition (MNIST and TiCH), were implemented using LeNet architecture. While a more complex task of object recognition (CIFAR10) was implemented on a state of the art deep CNN (Network in Network) architecture. The proposed approach yields 1.31-1.53x improvement in training energy in comparison to conventional CNN implementation. We also obtain improvement up to 1.4x in training time, up to 2.23x in storage requirements, and up to 2.2x in memory access energy. The accuracy degradation suffered by the approximate implementations is within 0-3% of the baseline.
Bias and variance in the social structure of gender
Venue: arXiv cs.SI 2017
Year: 2017

The observation that individuals tend to be friends with people who are similar to themselves, commonly known as homophily, is a prominent and well-studied feature of social networks. Many machine learning methods exploit homophily to predict attributes of individuals based on the attributes of their friends. Meanwhile, recent work has shown that gender homophily can be weak or nonexistent in practice, making gender prediction particularly challenging. In this work, we identify another useful structural feature for predicting gender, an overdispersion of gender preferences introduced by individuals who have extreme preferences for a particular gender, regardless of their own gender. We call this property monophily for "love of one," and jointly characterize the statistical structure of homophily and monophily in social networks in terms of preference bias and preference variance. For prediction, we find that this pattern of extreme gender preferences introduces friend-of-friend correlations, where individuals are similar to their friends-of-friends without necessarily being similar to their friends. We analyze a population of online friendship networks in U.S. colleges and offline friendship networks in U.S. high schools and observe a fundamental difference between the success of prediction methods based on friends, "the company you keep," compared to methods based on friends-of-friends, "the company you're kept in." These findings offer an alternative perspective on attribute prediction in general and gender in particular, complicating the already difficult task of protecting attribute privacy.
Aiming to Detect a malware of GSM frequency
Venue: arXiv cs.CR 2017
Year: 2017

In order to find a specific type of malware which is related to GSM frequency, we propose an algorithm according to the most essential characteristics of this malware. At first, detect whether or not there exists a specific thread in the memory. And then, the generated binary strings will be tried to be matched with the one in the target computer. At last, determine whether this threat occurs or not. Furthermore, we study the effective of the new method via some simulations.
Deep neural networks on graph signals for brain imaging analysis
Venue: arXiv cs.CV 2017
Year: 2017

Brain imaging data such as EEG or MEG are high-dimensional spatiotemporal data often degraded by complex, non-Gaussian noise. For reliable analysis of brain imaging data, it is important to extract discriminative, low-dimensional intrinsic representation of the recorded data. This work proposes a new method to learn the low-dimensional representations from the noise-degraded measurements. In particular, our work proposes a new deep neural network design that integrates graph information such as brain connectivity with fully-connected layers. Our work leverages efficient graph filter design using Chebyshev polynomial and recent work on convolutional nets on graph-structured data. Our approach exploits graph structure as the prior side information, localized graph filter for feature extraction and neural networks for high capacity learning. Experiments on real MEG datasets show that our approach can extract more discriminative representations, leading to improved accuracy in a supervised classification task.
Extending the Metasploit Framework to Implement an Evasive Attack Infrastructure
Venue: arXiv cs.CR 2017
Year: 2017

Given a desired goal of testing the capabilities of mainstream antivirus software against evasive malicious payloads delivered via drive-by download, this work aims to extend the functionality of Metasploit--the penetration testing suite of choice--in a three-fold manner: (1) to allow it to dynamically generate evasive forms of Metasploit-packaged malicious binaries, (2) to provide an evasive means of delivering said executables through a drive-by download-derived attack vector, and (3) to coordinate the previous two functionalities in a manner which can be used to produce reproducible tests within the SPICE framework
Awareness improves problem-solving performance
Venue: arXiv cs.AI 2017
Year: 2017

The brain's self-monitoring of activities, including internal activities -- a functionality that we refer to as awareness -- has been suggested as a key element of consciousness. Here we investigate whether the presence of an inner-eye-like process (monitor) that supervises the activities of a number of subsystems (operative agents) engaged in the solution of a problem can improve the problem-solving efficiency of the system. The problem is to find the global maximum of a NK fitness landscape and the performance is measured by the time required to find that maximum. The operative agents explore blindly the fitness landscape and the monitor provides them with feedback on the quality (fitness) of the proposed solutions. This feedback is then used by the operative agents to bias their searches towards the fittest regions of the landscape. We find that a weak feedback between the monitor and the operative agents improves the performance of the system, regardless of the difficulty of the problem, which is gauged by the number of local maxima in the landscape. For easy problems (i.e., landscapes without local maxima), the performance improves monotonically as the feedback strength increases, but for difficult problems, there is an optimal value of the feedback strength beyond which the system performance degrades very rapidly.
Gland Segmentation in Histopathology Images Using Random Forest Guided Boundary Construction
Venue: arXiv cs.CV 2017
Year: 2017

Grading of cancer is important to know the extent of its spread. Prior to grading, segmentation of glandular structures is important. Manual segmentation is a time consuming process and is subject to observer bias. Hence, an automated process is required to segment the gland structures. These glands show a large variation in shape size and texture. This makes the task challenging as the glands cannot be segmented using mere morphological operations and conventional segmentation mechanisms. In this project we propose a method which detects the boundary epithelial cells of glands and then a novel approach is used to construct the complete gland boundary. The region enclosed within the boundary can then be obtained to get the segmented gland regions.
Big Data: Challenges, Opportunities and Realities
Venue: arXiv cs.DB 2017
Year: 2017

With the advent of Internet of Things (IoT) and Web 2.0 technologies, there has been a tremendous growth in the amount of data generated. This chapter emphasizes on the need for big data, technological advancements, tools and techniques being used to process big data are discussed. Technological improvements and limitations of existing storage techniques are also presented. Since, the traditional technologies like Relational Database Management System (RDBMS) have their own limitations to handle big data, new technologies have been developed to handle them and to derive useful insights. This chapter presents an overview of big data analytics, its application, advantages, and limitations. Few research issues and future directions are presented in this chapter.
Enriched closure spaces as a novel framework for domain theory
Venue: arXiv cs.LO 2017
Year: 2017

We propose a generalization of continuous lattices and domains through the concept of enriched closure space, defined as a closure space equipped with a preclosure operator satisfying some compatibility conditions. In this framework we are able to define a notion of way-below relation; an appropriate definition of continuity then naturally follows. Characterizations of continuity of the enriched closure space and necessary and sufficient conditions for the interpolation property are proved. We also draw a link between continuity and the possibility for the subsets that are open with respect to the preclosure operator to form a topology.
Statistical Timing Analysis and Criticality Computation for Circuits with Post-Silicon Clock Tuning Elements
Venue: arXiv cs.AR 2017
Year: 2017

Post-silicon clock tuning elements are widely used in high-performance designs to mitigate the effects of process variations and aging. Located on clock paths to flip-flops, these tuning elements can be configured through the scan chain so that clock skews to these flip-flops can be adjusted after man- ufacturing. Owing to the delay compensation across consecutive register stages enabled by the clock tuning elements, higher yield and enhanced robustness can be achieved. These benefits are, nonetheless, attained by increasing die area due to the inserted clock tuning elements. For balancing performance improvement and area cost, an efficient timing analysis algorithm is needed to evaluate the performance of such a circuit. So far this evaluation is only possible by Monte Carlo simulation which is very timing- consuming. In this paper, we propose an alternative method using graph transformation, which computes a parametric minimum clock period and is more than 10 4 times faster than Monte Carlo simulation while maintaining a good accuracy. This method also identifies the gates that are critical to circuit performance, so that a fast analysis-optimization flow becomes possible.
Irregular Recovery and Unequal Locality for Locally Recoverable Codes with Availability
Venue: arXiv cs.IT 2017
Year: 2017

A code is said to be a Locally Recoverable Code (LRC) with availability if every coordinate can be recovered from multiple disjoint sets of other coordinates called recovering sets. The vector of sizes of recovering sets of a coordinate is called its recovery profile. In this work, we consider LRCs with availability under two different settings: (1) irregular recovery: non-constant recovery profile that remains fixed for all coordinates, (2) unequal locality: regular recovery profile that can vary with coordinates. For each setting, we derive bounds for the minimum distance that generalize previously known bounds to the cases of irregular or varying recovery profiles. For the case of regular and fixed recovery profile, we show that a specific Tamo-Barg polynomial-evaluation construction is optimal for all-symbol locality, and we provide parity-check matrix constructions for information locality with availability.
Minimax Risk for Missing Mass Estimation
Venue: arXiv cs.IT 2017
Year: 2017

The problem of estimating the missing mass or total probability of unseen elements in a sequence of $n$ random samples is considered under the squared error loss function. The worst-case risk of the popular Good-Turing estimator is shown to be between $0.6080/n$ and $0.6179/n$. The minimax risk is shown to be lower bounded by $0.25/n$. This appears to be the first such published result on minimax risk for estimation of missing mass, which has several practical and theoretical applications.