OpenRaiser/Intern-Atlas huggingface dataset:
ILP-based Local Search for Graph Partitioning
Venue: arXiv cs.DS 2018
Year: 2018

Computing high-quality graph partitions is a challenging problem with numerous applications. In this paper, we present a novel meta-heuristic for the balanced graph partitioning problem. Our approach is based on integer linear programs that solve the partitioning problem to optimality. However, since those programs typically do not scale to large inputs, we adapt them to heuristically improve a given partition. We do so by defining a much smaller model that allows us to use symmetry breaking and other techniques that make the approach scalable. For example, in Walshaw's well-known benchmark tables we are able to improve roughly half of all entries when the number of blocks is high.
The parameterized complexity of finding a 2-sphere in a simplicial complex
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^{o(sqrt(k))}) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).
Adaptive Sampling for Coarse Ranking
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of active coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications involving human raters and the approximate rank of every item is desired. Approximate or coarse ranking can significantly reduce the number of ratings required in comparison to the number needed to find an exact ranking. We propose a computationally efficient PAC algorithm LUCBRank for coarse ranking, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.
Leader-follower based Coalition Formation in Large-scale UAV Networks, A Quantum Evolutionary Approach
Venue: arXiv cs.MA 2018
Year: 2018

The problem of decentralized multiple Point of Interests (PoIs) detection and associated task completion in an unknown environment with multiple resource-constrained and self-interested Unmanned Aerial Vehicles (UAVs) is studied. The UAVs form several coalitions to efficiently complete the compound tasks which are impossible to be performed individually. The objectives of such coalition formation are to firstly minimize resource consumption in completing the encountered tasks on time, secondly to enhance the reliability of the coalitions, and lastly in segregating the most trusted UAVs amid the self interested of them. As many previous publications have merely focused on minimizing costs, this study considers a multi-objective optimization coalition formation problem that considers the three aforementioned objectives. In doing so, a leader-follower- inspired coalition formation algorithm amalgamating the three objectives to address the problem of the computational complexity of coalition formation in large-scale UAV networks is proposed. This algorithm attempts to form the coalitions with minimally exceeding the required resources for the encountered tasks while maximizing the number of completed tasks. The proposed algorithm is based on Quantum Evolutionary Algorithms(QEA) which are a combination of quantum computing and evolutionary algorithms. Results from simulations show that the proposed algorithm significantly outperforms the existing coalition formation algorithms such as merge-and-split and a famous multi-objective genetic algorithm called NSGA-II.
Actively Avoiding Nonsense in Generative Models
Venue: arXiv cs.LG 2018
Year: 2018

A generative model may generate utter nonsense when it is fit to maximize the likelihood of observed data. This happens due to "model error," i.e., when the true data generating distribution does not fit within the class of generative models being learned. To address this, we propose a model of active distribution learning using a binary invalidity oracle that identifies some examples as clearly invalid, together with random positive examples sampled from the true distribution. The goal is to maximize the likelihood of the positive examples subject to the constraint of (almost) never generating examples labeled invalid by the oracle. Guarantees are agnostic compared to a class of probability distributions. We show that, while proper learning often requires exponentially many queries to the invalidity oracle, improper distribution learning can be done using polynomially many queries.
Logic Programming Applications: What Are the Abstractions and Implementations?
Venue: arXiv cs.PL 2018
Year: 2018

This article presents an overview of applications of logic programming, classifying them based on the abstractions and implementations of logic languages that support the applications. The three key abstractions are join, recursion, and constraint. Their essential implementations are for-loops, fixed points, and backtracking, respectively. The corresponding kinds of applications are database queries, inductive analysis, and combinatorial search, respectively. We also discuss language extensions and programming paradigms, summarize example application problems by application areas, and touch on example systems that support variants of the abstractions with different implementations.
Developing a system for securely time-stamping and visualizing the changes made to online news content
Venue: arXiv cs.DL 2018
Year: 2018

Nowadays, the Internet is indispensable when it comes to information dissemination. People rely on the Internet to inform themselves on current news events, as well as to verify facts. We, as a community, are quickly approaching an 'electronic information age' where the majority of information will be distributed electronically and tools to preserve this information will become essential. While archiving online digital information is a good way to preserve online information for future generations, it has many disadvantages including the easy manipulation of archived information, e.g. by the archiving authority. Online information is also prone to getting hacked or being taken offline. Therefore, it is necessary that archived online news information is securely time-stamped with the date and time when it was first archived in a way that cannot be manipulated. The process of 'trusted timestamping' is an established approach for claiming that particular digital information existed at a particular 'point in time' in the past. However, traditional approaches for trusted timestamping depend on the time-stamping authority's fidelity. Directly embedding the hash of a digital file into the blockchain of a cryptocurrency is a more recent method that allows for secure time-stamping, since digital information is stored as part of the transaction information in, e.g. Bitcoin's, blockchain, and not stored at a centralized time-stamping authority. However, there is no system yet available, which uses this approach for archiving and time-stamping online news articles. Therefore, the aim of this thesis is to develop a system that 1) enables decentralized trusted time-stamping of web and news articles as a means of making future manipulation of online information identifiable, and 2) allows users to determine the authenticity of articles by checking different versions of the same article online.
Statistical Software for Psychology: Comparing Development Practices Between CRAN and Other Communities
Venue: arXiv cs.SE 2018
Year: 2018

Different communities rely heavily on software, but use quite different software development practices. {\bf Objective}: We wanted to measure the state of the practice in the area of statistical software for psychology to understand how it compares to best practices. {\bf Method}: We compared and ranked 30 software tools with respect to adherence to best software engineering practices on items that could be measured by end-users. {\bf Results} We found that R packages use quite good practices, that while commercial packages were quite usable, many aspects of their development is too opaque to be measures, and that research projects vary a lot in their practices. {\bf Conclusion} We recommend that more organizations adopt practices similar to those used by CRAN to facilitate success, even for small teams. We also recommend close coupling of source code and documentation, to improve verifiability.
Reduced Transmission in Multi-Server Coded Caching
Venue: arXiv cs.IT 2018
Year: 2018

Coded caching has been widely used in the wireless network for shifting the some transmissions during the peak traffic times to the off-peak traffic times. Multi-server coded caching, which can share responsibility for the total amount of transmission in the wireless network during the peak traffic times by means of the collaboration among these servers, can be seen everywhere in our life. The three servers setting (two data servers and one parity check server) is used in practice, e.g. redundant array of independent disks-4. In this scenario, there are total $N$ files which are equally stored in two data servers respectively and $K$ users each of which has the memory size of $M$ files. Each server connects to users by an independently channel. During the off-peak traffic times, two data servers place some parts of each files in each user's cache. In that time, servers do not know users' requests in future. During the peak traffic times each user just requests one file from $N$ files. Luo et al. in 2016 proposed the first coded caching scheme for this setting. In this paper, we proposed some method that further reduces the amount of transmission in each channel when $\frac{KM}{N}$ is odd. This method also improves the transmission rate for systems with general multiply servers.
Angle constrained path to cluster multiple manifolds
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a method to cluster multiple intersected manifolds. The algorithm chooses several landmark nodes randomly and then checks whether there is an angle constrained path between each landmark node and every other node in the neighborhood graph. When the points lie on different manifolds with intersection they should not be connected using a smooth path, thus the angle constraint is used to prevent connecting points from one cluster to another one. The resulting algorithm is implemented as a simple variation of Dijkstras algorithm used in Isomap. However, Isomap was specifically designed for dimensionality reduction in the single-manifold setting, and in particular, can-not handle intersections. Our method is simpler than the previous proposals in the literature and performs comparably to the best methods, both on simulated and some real datasets.
Slocalization: Sub-μW Ultra Wideband Backscatter Localization
Venue: arXiv cs.NI 2018
Year: 2018

Ultra wideband technology has shown great promise for providing high-quality location estimation, even in complex indoor multipath environments, but existing ultra wideband systems require tens to hundreds of milliwatts during operation. Backscatter communication has demonstrated the viability of astonishingly low-power tags, but has thus far been restricted to narrowband systems with low localization resolution. The challenge to combining these complimentary technologies is that they share a compounding limitation, constrained transmit power. Regulations limit ultra wideband transmissions to just -41.3 dBm/MHz, and a backscatter device can only reflect the power it receives. The solution is long-term integration of this limited power, lifting the initially imperceptible signal out of the noise. This integration only works while the target is stationary. However, stationary describes the vast majority of objects, especially lost ones. With this insight, we design Slocalization, a sub-microwatt, decimeter-accurate localization system that opens a new tradeoff space in localization systems and realizes an energy, size, and cost point that invites the localization of every thing. To evaluate this concept, we implement an energy-harvesting Slocalization tag and find that Slocalization can recover ultra wideband backscatter in under fifteen minutes across thirty meters of space and localize tags with a mean 3D Euclidean error of only 30 cm.
Optimal Base Station Antenna Downtilt in Downlink Cellular Networks
Venue: arXiv cs.NI 2018
Year: 2018

From very recent studies, the area spectral efficiency (ASE) performance of downlink (DL) cellular networks will continuously decrease and finally to zero with the network densification in a fully loaded ultra-dense network (UDN) when the absolute height difference between a base station (BS) antenna and a user equipment (UE) antenna is larger than zero, which is referred as the ASE Crash. We revisit this issue by considering the impact of the BS antenna downtilt on the downlink network capacity. In general, there exists a height difference between a BS and a UE in practical networks. It is common to utilize antenna downtilt to adjust the direction of the vertical antenna pattern, and thus increase received signal power or reduce inter-cell interference power to improve network performance. This paper focuses on investigating the relationship between the base station antenna downtilt and the downlink network capacity in terms of the coverage probability and the ASE. The analytical results of the coverage probability and the ASE are derived, and we find that there exists an optimal antenna downtilt to achieve the maximal coverage probability for each base station density. Moreover, we derive numerically solvable expressions for the optimal antenna downtilt, which is a function of the base station density. Our theoretical and numerical results show that after applying the optimal antenna downtilt, the network performance can be improved significantly. Specifically, with the optimal antenna downtilt, the ASE crash can be delayed by nearly one order of magnitude in terms of the base station density.
Approximation Algorithms for Road Coverage Using Wireless Sensor Networks for Moving Objects Monitoring
Venue: arXiv cs.CG 2018
Year: 2018

Coverage problem in wireless sensor networks measures how well a region or parts of it is sensed by the deployed sensors. Definition of coverage metric depends on its applications for which sensors are deployed. In this paper, we introduce a new quality control metric/measure called road coverage. It will be used for measuring efficiency of a sensor network, which is deployed for tracking moving/mobile objects in a road network. A road segment is a sub-part of a road network. A road segment is said to be road covered if an object travels through the entire road segment then it must be detected somewhere on the road segment by a sensor. First, we propose different definitions of road coverage metrics. Thereafter, algorithms are proposed to measure those proposed road coverage metrics. It is shown that the problem of deploying minimum number of sensors to road cover a set of road segments is NP-hard. Constant factor approximation algorithms are proposed for road covering axis-parallel road segments. Experimental performance analysis of our algorithms are evaluated through simulations.
A framework for cost-constrained genome rearrangement under Double Cut and Join
Venue: arXiv cs.DS 2018
Year: 2018

The study of genome rearrangement has many flavours, but they all are somehow tied to edit distances on variations of a multi-graph called the breakpoint graph. We study a weighted 2-break distance on Eulerian 2-edge-colored multi-graphs, which generalizes weighted versions of several Double Cut and Join problems, including those on genomes with unequal gene content. We affirm the connection between cycle decompositions and edit scenarios first discovered with the Sorting By Reversals problem. Using this we show that the problem of finding a parsimonious scenario of minimum cost on an Eulerian 2-edge-colored multi-graph - with a general cost function for 2-breaks - can be solved by decomposing the problem into independent instances on simple alternating cycles. For breakpoint graphs, and a more constrained cost function, based on coloring the vertices, we give a polynomial-time algorithm for finding a parsimonious 2-break scenario of minimum cost, while showing that finding a non-parsimonious 2-break scenario of minimum cost is NP-Hard.
DeepASL: Enabling Ubiquitous and Non-Intrusive Word and Sentence-Level Sign Language Translation
Venue: arXiv cs.CV 2018
Year: 2018

There is an undeniable communication barrier between deaf people and people with normal hearing ability. Although innovations in sign language translation technology aim to tear down this communication barrier, the majority of existing sign language translation systems are either intrusive or constrained by resolution or ambient lighting conditions. Moreover, these existing systems can only perform single-sign ASL translation rather than sentence-level translation, making them much less useful in daily-life communication scenarios. In this work, we fill this critical gap by presenting DeepASL, a transformative deep learning-based sign language translation technology that enables ubiquitous and non-intrusive American Sign Language (ASL) translation at both word and sentence levels. DeepASL uses infrared light as its sensing mechanism to non-intrusively capture the ASL signs. It incorporates a novel hierarchical bidirectional deep recurrent neural network (HB-RNN) and a probabilistic framework based on Connectionist Temporal Classification (CTC) for word-level and sentence-level ASL translation respectively. To evaluate its performance, we have collected 7,306 samples from 11 participants, covering 56 commonly used ASL words and 100 ASL sentences. DeepASL achieves an average 94.5% word-level translation accuracy and an average 8.2% word error rate on translating unseen ASL sentences. Given its promising performance, we believe DeepASL represents a significant step towards breaking the communication barrier between deaf people and hearing majority, and thus has the significant potential to fundamentally change deaf people's lives.
Building Efficient ConvNets using Redundant Feature Pruning
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an efficient technique to prune deep and/or wide convolutional neural network models by eliminating redundant features (or filters). Previous studies have shown that over-sized deep neural network models tend to produce a lot of redundant features that are either shifted version of one another or are very similar and show little or no variations; thus resulting in filtering redundancy. We propose to prune these redundant features along with their connecting feature maps according to their differentiation and based on their relative cosine distances in the feature space, thus yielding smaller network size with reduced inference costs and competitive performance. We empirically show on select models and CIFAR-10 dataset that inference costs can be reduced by 40% for VGG-16, 27% for ResNet-56, and 39% for ResNet-110.
Learning Multiple Categories on Deep Convolution Networks
Venue: arXiv cs.CV 2018
Year: 2018

Deep convolution networks have proved very successful with big datasets such as the 1000-classes ImageNet. Results show that the error rate increases slowly as the size of the dataset increases. Experiments presented here may explain why these networks are very effective in solving big recognition problems. If the big task is made up of multiple smaller tasks, then the results show the ability of deep convolution networks to decompose the complex task into a number of smaller tasks and to learn them simultaneously. The results show that the performance of solving the big task on a single network is very close to the average performance of solving each of the smaller tasks on a separate network. Experiments also show the advantage of using task specific or category labels in combination with class labels.
Can Microsoft Academic assess the early citation impact of in-press articles? A multi-discipline exploratory analysis
Venue: arXiv cs.DL 2018
Year: 2018

Many journals post accepted articles online before they are formally published in an issue. Early citation impact evidence for these articles could be helpful for timely research evaluation and to identify potentially important articles that quickly attract many citations. This article investigates whether Microsoft Academic can help with this task. For over 65,000 Scopus in-press articles from 2016 and 2017 across 26 fields, Microsoft Academic found 2-5 times as many citations as Scopus, depending on year and field. From manual checks of 1,122 Microsoft Academic citations not found in Scopus, Microsoft Academic's citation indexing was faster but not much wider than Scopus for journals. It achieved this by associating citations to preprints with their subsequent in-press versions and by extracting citations from in-press articles. In some fields its coverage of scholarly digital libraries, such as arXiv.org, was also an advantage. Thus, Microsoft Academic seems to be a more comprehensive automatic source of citation counts for in-press articles than Scopus.
A New Hybrid Half-Duplex/Full-Duplex Relaying System with Antenna Diversity
Venue: arXiv cs.IT 2018
Year: 2018

The hybrid half-duplex/full-duplex (HD/FD) relaying scheme is an effective paradigm to overcome the negative effects of the self-interference incurred by the full-duplex (FD) mode. However, traditional hybrid HD/FD scheme does not consider the diversity gain incurred by the multiple antennas of the FD node when the system works in the HD mode, leading to the waste of the system resources. In this paper, we propose a new hybrid HD/FD relaying scheme, which utilizes both the antennas of the FD relay node for reception and transmission when the system works in the HD mode. With multiple antennas, the maximum ratio combining/maximum ratio transmission is adopted to process the signals at the relay node. Based on this scheme, we derive the exact closed-form system outage probability and conduct various numerical simulations. The results show that the proposed scheme remarkably improves the system outage performance over the traditional scheme, and demonstrate that the proposed scheme can more effectively alleviate the adverse effects of the residual self-interference.