OpenRaiser/Intern-Atlas huggingface dataset:
Sum-rate Maximization in Sub-28 GHz Millimeter-Wave MIMO Interfering Networks
Venue: arXiv cs.IT 2018
Year: 2018

MIMO systems in the lower part of the millimeter-wave spectrum band (i.e., below 28 GHz) do not exhibit enough directivity and selectively, as their counterparts in higher bands of the spectrum (i.e., above 60 GHz), and thus still suffer from the detrimental effect of interference, on the system sum-rate. As such systems exhibit large numbers of antennas and short coherence times for the channel, traditional methods of distributed coordination are ill-suited, and the resulting communication overhead would offset the gains of coordination. In this work, we propose algorithms for tackling the sum-rate maximization problem, that are designed to address the above limitations. We derive a lower bound on the sum-rate, a so-called DLT bound (i.e., a difference of log and trace), shed light on its tightness, and highlight its decoupled nature at both the transmitters and receivers. Moreover, we derive the solution to each of the subproblems, that we dub non-homogeneous waterfilling (a variation on the MIMO waterfilling solution), and underline an inherent desirable feature: its ability to turn-off streams exhibiting low-SINR, and contribute to greatly speeding up the convergence of the proposed algorithm. We then show the convergence of the resulting algorithm, max-DLT, to a stationary point of the DLT bound. Finally, we rely on extensive simulations of various network configurations, to establish the fast-converging nature of our proposed schemes, and thus their suitability for addressing the short coherence interval, as well as the increased system dimensions, arising when managing interference in lower bands of the millimeter wave spectrum. Moreover, our results also suggest that interference management still brings about significant performance gains, especially in dense deployments.
Maximizing CNN Accelerator Efficiency Through Resource Partitioning
Venue: arXiv cs.AR 2018
Year: 2018

Convolutional neural networks (CNNs) are revolutionizing machine learning, but they present significant computational challenges. Recently, many FPGA-based accelerators have been proposed to improve the performance and efficiency of CNNs. Current approaches construct a single processor that computes the CNN layers one at a time; the processor is optimized to maximize the throughput at which the collection of layers is computed. However, this approach leads to inefficient designs because the same processor structure is used to compute CNN layers of radically varying dimensions. We present a new CNN accelerator paradigm and an accompanying automated design methodology that partitions the available FPGA resources into multiple processors, each of which is tailored for a different subset of the CNN convolutional layers. Using the same FPGA resources as a single large processor, multiple smaller specialized processors increase computational efficiency and lead to a higher overall throughput. Our design methodology achieves 3.8x higher throughput than the state-of-the-art approach on evaluating the popular AlexNet CNN on a Xilinx Virtex-7 FPGA. For the more recent SqueezeNet and GoogLeNet, the speedups are 2.2x and 2.0x.
Keyframe-based monocular SLAM: design, survey, and future directions
Venue: arXiv cs.CV 2018
Year: 2018

Extensive research in the field of monocular SLAM for the past fifteen years has yielded workable systems that found their way into various applications in robotics and augmented reality. Although filter-based monocular SLAM systems were common at some time, the more efficient keyframe-based solutions are becoming the de facto methodology for building a monocular SLAM system. The objective of this paper is threefold: first, the paper serves as a guideline for people seeking to design their own monocular SLAM according to specific environmental constraints. Second, it presents a survey that covers the various keyframe-based monocular SLAM systems in the literature, detailing the components of their implementation, and critically assessing the specific strategies made in each proposed solution. Third, the paper provides insight into the direction of future research in this field, to address the major limitations still facing monocular SLAM; namely, in the issues of illumination changes, initialization, highly dynamic motion, poorly textured scenes, repetitive textures, map maintenance, and failure recovery.
The sequential functionals of type $(ι\rightarrow ι)^n \rightarrow ι$ form a dcpo for all $n \in \Bbb N$
Venue: arXiv cs.LO 2018
Year: 2018

We prove that the sequential functionals of some fixed types at type level 2, taking finite sequences of unary functions as arguments, do form a directed complete partial ordering. This gives a full characterisation of for which types the partially ordered set of sequential functionals has this property. As a tool, we prove a normal form theorem for the finite sequential functionals of the types in question,
Qualitative Judgement of Research Impact: Domain Taxonomy as a Fundamental Framework for Judgement of the Quality of Research
Venue: arXiv cs.DL 2018
Year: 2018

The appeal of metric evaluation of research impact has attracted considerable interest in recent times. Although the public at large and administrative bodies are much interested in the idea, scientists and other researchers are much more cautious, insisting that metrics are but an auxiliary instrument to the qualitative peer-based judgement. The goal of this article is to propose availing of such a well positioned construct as domain taxonomy as a tool for directly assessing the scope and quality of research. We first show how taxonomies can be used to analyse the scope and perspectives of a set of research projects or papers. Then we proceed to define a research team or researcher's rank by those nodes in the hierarchy that have been created or significantly transformed by the results of the researcher. An experimental test of the approach in the data analysis domain is described. Although the concept of taxonomy seems rather simplistic to describe all the richness of a research domain, its changes and use can be made transparent and subject to open discussions.
Robust algorithms with polynomial loss for near-unanimity CSPs
Venue: arXiv cs.DS 2018
Year: 2018

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a $(1-g(\varepsilon))$-fraction of constraints on any $(1-\varepsilon)$-satisfiable instance, where the loss function $g$ is such that $g(\varepsilon)\rightarrow 0$ as $\varepsilon\rightarrow 0$. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some $g$) have been characterised by Barto and Kozik, with the general bound on the loss $g$ being doubly exponential, specifically $g(\varepsilon)=O((\log\log(1/\varepsilon))/\log(1/\varepsilon))$. It is natural to ask when a better loss can be achieved: in particular, polynomial loss $g(\varepsilon)=O(\varepsilon^{1/k})$ for some constant $k$. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter $k$ in the loss depends on the size of the domain and the arity of the relations in $Γ$, while the other works for a special ternary near-unanimity operation called dual discriminator with $k=2$ for any domain size. In the latter case, the CSP is a common generalisation of Unique Games with a fixed domain and 2-SAT. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for CSP.
On Ring Learning with Errors over the Tensor Product of Number Fields
Venue: arXiv cs.CR 2018
Year: 2018

The "Ring Learning with Errors" (RLWE) problem was formulated as a variant of the "Learning with Errors" (LWE) problem, with the purpose of taking advantage of an additional algebraic structure in the underlying considered lattices; this enables improvements on the efficiency and cipher expansion on those cryptographic applications which were previously based on the LWE problem. In Eurocrypt 2010, Lyubashevsky et al. introduced this hardness problem and showed its relation to some known hardness problems over lattices with a special structure. In this work, we generalize these results and the problems presented by Lyubashevsky et al. to the more general case of multivariate rings, highlighting the main differences with respect to the security proof for the RLWE counterpart. This hardness problem is denoted as "Multivariate Ring Learning with Errors" ($m$-RLWE or multivariate RLWE) and we show its relation to hardness problems over the tensor product of ideal lattices. Additionally, the $m$-RLWE problem is more adequate than its univariate version for cryptographic applications dealing with multidimensional structures.
Learning Nominal Automata
Venue: arXiv cs.FL 2018
Year: 2018

We present an Angluin-style algorithm to learn nominal automata, which are acceptors of languages over infinite (structured) alphabets. The abstract approach we take allows us to seamlessly extend known variations of the algorithm to this new setting. In particular we can learn a subclass of nominal non-deterministic automata. An implementation using a recently developed Haskell library for nominal computation is provided for preliminary experiments.
Complexity of Token Swapping and its Variants
Venue: arXiv cs.CC 2018
Year: 2018

In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is $W[1]$-hard parameterized by the length $k$ of a shortest sequence of swaps. In fact, we prove that, for any computable function $f$, it cannot be solved in time $f(k)n^{o(k / \log k)}$ where $n$ is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial $n^{O(k)}$-time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have different colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.
An Efficient Representation for Filtrations of Simplicial Complexes
Venue: arXiv cs.CG 2018
Year: 2018

A filtration over a simplicial complex $K$ is an ordering of the simplices of $K$ such that all prefixes in the ordering are subcomplexes of $K$. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. In order to represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica '14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. In this paper, we propose a new data structure called the Critical Simplex Diagram (CSD) which is a variant of the Simplex Array List (SAL) [Algorithmica '17]. Our data structure allows one to store in a compact way the filtration of a simplicial complex, and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Finally, we show that the CSD representation admits fast construction algorithms for Flag complexes and relaxed Delaunay complexes.
Scientific Auditing Firms
Venue: arXiv cs.CY 2018
Year: 2018

The "crisis of reproducibility" has been a significant source of controversy, heated debate, and calls for reform to institutional science in recent years. As a long-term solution to address both the present crisis and future obstacles, I propose the creation of a new form of research organization whose purpose would be to conduct random audits of the scientific literature. I suggest that data analytics of a digitized scientific corpus may play a critical role in allowing broadly educated scientists to identify linchpin results to investigate in further detail across all disciplines. I argue that a simple "mock" trial run of a simplified auditing firm consisting of several researchers over a short time period would provide valuable insight into the feasibility of this proposal.
Making Caches Work for Graph Analytics
Venue: arXiv cs.DC 2018
Year: 2018

Modern hardware systems are heavily underutilized when running large-scale graph applications. While many in-memory graph frameworks have made substantial progress in optimizing these applications, we show that it is still possible to achieve up to 4 $\times$ speedups over the fastest frameworks by greatly improving cache utilization. Previous systems have applied out-of-core processing techniques from the memory/disk boundary to the cache/DRAM boundary. However, we find that blindly applying such techniques is ineffective because of the much smaller performance gap between DRAM and cache. We present two techniques that take advantage of the cache with minimal or no instruction overhead. The first, frequency based clustering, groups together frequently accessed vertices to improve the utilization of each cache line with no runtime overhead. The second, CSR segmenting, partitions the graph to restrict all random accesses to the cache, makes all DRAM access sequential, and merges partition results using a very low overhead cache-aware merge. Both techniques can be easily implemented on top of optimized graph frameworks. Our techniques combined give speedups of up to 4 $\times$ for PageRank, Label Propagation and Collaborative Filtering, and 2 $\times$ for Betweenness Centrality over the best published results
Saliency Integration: An Arbitrator Model
Venue: arXiv cs.CV 2018
Year: 2018

Saliency integration has attracted much attention on unifying saliency maps from multiple saliency models. Previous offline integration methods usually face two challenges: 1. if most of the candidate saliency models misjudge the saliency on an image, the integration result will lean heavily on those inferior candidate models; 2. an unawareness of the ground truth saliency labels brings difficulty in estimating the expertise of each candidate model. To address these problems, in this paper, we propose an arbitrator model (AM) for saliency integration. Firstly, we incorporate the consensus of multiple saliency models and the external knowledge into a reference map to effectively rectify the misleading by candidate models. Secondly, our quest for ways of estimating the expertise of the saliency models without ground truth labels gives rise to two distinct online model-expertise estimation methods. Finally, we derive a Bayesian integration framework to reconcile the saliency models of varying expertise and the reference map. To extensively evaluate the proposed AM model, we test twenty-seven state-of-the-art saliency models, covering both traditional and deep learning ones, on various combinations over four datasets. The evaluation results show that the AM model improves the performance substantially compared to the existing state-of-the-art integration methods, regardless of the chosen candidate saliency models.
Sparse Filtered SIRT for Electron Tomography
Venue: arXiv cs.CV 2018
Year: 2018

Electron tomographic reconstruction is a method for obtaining a three-dimensional image of a specimen with a series of two dimensional microscope images taken from different viewing angles. Filtered backprojection, one of the most popular tomographic reconstruction methods, does not work well under the existence of image noises and missing wedges. This paper presents a new approach to largely mitigate the effect of noises and missing wedges. We propose a novel filtered backprojection that optimizes the filter of the backprojection operator in terms of a reconstruction error. This data-dependent filter adaptively chooses the spectral domains of signals and noises, suppressing the noise frequency bands, so it is very effective in denoising. We also propose the new filtered backprojection embedded within the simultaneous iterative reconstruction iteration for mitigating the effect of missing wedges. Our numerical study is presented to show the performance gain of the proposed approach over the state-of-the-art.
Local rewiring algorithms to increase clustering and grow a small world
Venue: arXiv cs.SI 2018
Year: 2018

Many real-world networks have high clustering among vertices: vertices that share neighbors are often also directly connected to each other. A network's clustering can be a useful indicator of its connectedness and community structure. Algorithms for generating networks with high clustering have been developed, but typically rely on adding or removing edges and nodes, sometimes from a completely empty network. Here, we introduce algorithms that create a highly clustered network by starting with an existing network and rearranging edges, without adding or removing them; these algorithms can preserve other network properties even as the clustering increases. They rely on local rewiring rules, in which a single edge changes one of its vertices in a way that is guaranteed to increase clustering. This greedy step can be applied iteratively to transform a random network into a form with much higher clustering. Additionally, the algorithms presented grow a network's clustering faster than they increase its path length, meaning that network enters a regime of comparatively high clustering and low path length: a small world. These algorithms may be a basis for how real-world networks rearrange themselves organically to achieve or maintain high clustering and small-world structure.
On Information-Theoretic Characterizations of Markov Random Fields and Subfields
Venue: arXiv cs.DM 2018
Year: 2018

Let $X_i, i \in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$, and $V'$ be a subset of $V$. We determine the smallest graph that can always represent the subfield $X_i, i \in V'$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_i, i \in V$ form a Markov chain, it is known that the $I$-Measure is always nonnegative and the information diagram assumes a very special structure Kawabata and Yeung (1992). We prove that Markov chain is essentially the only MRF such that the $I$-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF in Yeung, Lee, and Ye (2002).
Visualizing and Understanding Sum-Product Networks
Venue: arXiv cs.LG 2018
Year: 2018

Sum-Product Networks (SPNs) are recently introduced deep tractable probabilistic models by which several kinds of inference queries can be answered exactly and in a tractable time. Up to now, they have been largely used as black box density estimators, assessed only by comparing their likelihood scores only. In this paper we explore and exploit the inner representations learned by SPNs. We do this with a threefold aim: first we want to get a better understanding of the inner workings of SPNs; secondly, we seek additional ways to evaluate one SPN model and compare it against other probabilistic models, providing diagnostic tools to practitioners; lastly, we want to empirically evaluate how good and meaningful the extracted representations are, as in a classic Representation Learning framework. In order to do so we revise their interpretation as deep neural networks and we propose to exploit several visualization techniques on their node activations and network outputs under different types of inference queries. To investigate these models as feature extractors, we plug some SPNs, learned in a greedy unsupervised fashion on image datasets, in supervised classification learning tasks. We extract several embedding types from node activations by filtering nodes by their type, by their associated feature abstraction level and by their scope. In a thorough empirical comparison we prove them to be competitive against those generated from popular feature extractors as Restricted Boltzmann Machines. Finally, we investigate embeddings generated from random probabilistic marginal queries as means to compare other tractable probabilistic models on a common ground, extending our experiments to Mixtures of Trees.
Empirical Evaluation of the Heat-Diffusion Collection Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2018
Year: 2018

Heat-Diffusion (HD) routing is our recently-developed queue-aware routing policy for multi-hop wireless networks inspired by Thermodynamics. In the prior theoretical studies, we have shown that HD routing guarantees throughput optimality, minimizes a quadratic routing cost, minimizes queue congestion on the network, and provides a trade-off between routing cost and queueing delay that is Pareto-Optimal. While striking, these guarantees are based on idealized assumptions (including global synchronization, centralized control, and infinite buffers) and heretofore have only been evaluated through simplified numerical simulations. We present here the first practical decentralized version of HD algorithm, which we refer to as Heat-Diffusion Collection Protocol (HDCP), for wireless sensor networks. We present a thorough evaluation of HDCP based on real testbed experiments, including a comparative analysis of its performance with respect to the state of the art Collection Tree Protocol (CTP) and Backpressure Collection Protocol (BCP) for wireless sensor networks. We find that HDCP has a significantly higher throughput region and greater resilience to interference compared to CTP. However, we also find that the best performance of HDCP is comparable to the best performance of BCP, due to the similarity in their neighbor rankings, which we verify through a Kendall's-Tau test.