OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Growth is Necessary and (Sometimes) Sufficient to Self-Assemble Discrete Self-Similar Fractals
Venue: arXiv cs.ET 2018
Year: 2018

In this paper, we prove that in the abstract Tile Assembly Model (aTAM), an accretion-based model which only allows for a single tile to attach to a growing assembly at each step, there are no tile assembly systems capable of self-assembling the discrete self-similar fractals known as the "H" and "U" fractals. We then show that in a related model which allows for hierarchical self-assembly, the 2-Handed Assembly Model (2HAM), there does exist a tile assembly systems which self-assembles the "U" fractal and conjecture that the same holds for the "H" fractal. This is the first example of discrete self similar fractals which self-assemble in the 2HAM but not in the aTAM, providing a direct comparison of the models and greater understanding of the power of hierarchical assembly.
Novel Method for Multi-Dimensional Mapping of Higher Order Modulations for BICM-ID Over Rayleigh Fading Channels
Venue: arXiv cs.IT 2018
Year: 2018

Multi-dimensional (MD) mapping offers more flexibility in mapping design for bit-interleaved coded modulation with iterative decoding (BICM-ID) and potentially improves the bandwidth efficiency. However, for higher order signal constellations, finding suitable MD mappings is a very complicated task due to the large number of possible mappings. In this paper, a novel mapping method is introduced to construct efficient MD mappings to improve the error performance of BICM-ID over Rayleigh fading channels. We propose to break the MD mapping design problem into four distinct $2$-D mapping functions. The $2$-D mappings are designed such that the resulting MD mapping improves the BICM-ID error performance at low signal to noise ratios (SNRs). We also develop cost functions that can be optimized to improve the error performance at high SNRs. The proposed mapping method is very simple compared to well-known mapping methods, and it can achieve suitable MD mappings for different modulations including higher order modulations for BICM-ID. Simulation results show that our mappings significantly outperform the previously known mappings at a target bit error rate (BER) of $10^{-6}$. Our mappings also offer a lower error-floor compared to their well-known counterparts.
Robot human interface for housekepeer with wireless capabilities
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents the design and implementation of a Human Interface for a housekeeper robot. It bases on the idea of making the robot understand the human needs without making the human go through the details of robots work, for example, the way that the robot implements the work or the method that the robot uses to plan the path in order to reach the work area. The interface commands based on idioms of the natural human language and designed in a manner that the user gives the robot several commands with their execution date/time.
Perceptrons from Memristors
Venue: arXiv cs.ET 2018
Year: 2018

Memristors, resistors with memory whose outputs depend on the history of their inputs, have been used with success in neuromorphic architectures, particularly as synapses and non-volatile memories. However, to the best of our knowledge, no model for a network in which both the synapses and the neurons are implemented using memristors has been proposed so far. In the present work we introduce models for single and multilayer perceptrons based exclusively on memristors. We adapt the delta rule to the memristor-based single-layer perceptron and the backpropagation algorithm to the memristor-based multilayer perceptron. Our results show that both perform as expected for perceptrons, including satisfying Minsky-Papert's theorem. As a consequence of the Universal Approximation Theorem, they also show that memristors are universal function approximators. By using memristors for both the neurons and the synapses, our models pave the way for novel memristor-based neural network architectures and algorithms. A neural network based on memristors could show advantages in terms of energy conservation and open up possibilities for other learning systems to be adapted to a memristor-based paradigm, both in the classical and quantum learning realms.
Spectral Sparsification of Hypergraphs
Venue: arXiv cs.DS 2018
Year: 2018

For an undirected/directed hypergraph $G=(V,E)$, its Laplacian $L_G\colon\mathbb{R}^V\to \mathbb{R}^V$ is defined such that its ``quadratic form'' $\boldsymbol{x}^\top L_G(\boldsymbol{x})$ captures the cut information of $G$. In particular, $\boldsymbol{1}_S^\top L_G(\boldsymbol{1}_S)$ coincides with the cut size of $S \subseteq V$, where $\boldsymbol{1}_S \in \mathbb{R}^V$ is the characteristic vector of $S$. A weighted subgraph $H$ of a hypergraph $G$ on a vertex set $V$ is said to be an $ε$-spectral sparsifier of $G$ if $(1-ε)\boldsymbol{x}^\top L_H(\boldsymbol{x}) \leq \boldsymbol{x}^\top L_G(\boldsymbol{x}) \leq (1+ε)\boldsymbol{x}^\top L_H(\boldsymbol{x})$ holds for every $\boldsymbol{x} \in \mathbb{R}^V$. In this paper, we present a polynomial-time algorithm that, given an undirected/directed hypergraph $G$ on $n$ vertices, constructs an $ε$-spectral sparsifier of $G$ with $O(n^3\log n/ε^2)$ hyperedges/hyperarcs. The proposed spectral sparsification can be used to improve the time and space complexities of algorithms for solving problems that involve the quadratic form, such as computing the eigenvalues of $L_G$, computing the effective resistance between a pair of vertices in $G$, semi-supervised learning based on $L_G$, and cut problems on $G$. In addition, our sparsification result implies that any submodular function $f\colon 2^V \to \mathbb{R}_+$ with $f(\emptyset)=f(V)=0$ can be concisely represented by a directed hypergraph. Accordingly, we show that, for any distribution, we can properly and agnostically learn submodular functions $f\colon 2^V \to [0,1]$ with $f(\emptyset)=f(V)=0$, with $O(n^4\log (n/ε) /ε^4)$ samples.
A Comprehensive Study of Pseudo-tested Methods
Venue: arXiv cs.SE 2018
Year: 2018

Pseudo-tested methods are defined as follows: they are covered by the test suite, yet no test case fails when the method body is removed, i.e., when all the effects of this method are suppressed. This intriguing concept was coined in 2016, by Niedermayr and colleagues, who showed that such methods are systematically present, even in well-tested projects with high statement coverage. This work presents a novel analysis of pseudo-tested methods. First, we run a replication of Niedermayr's study with 28K+ methods, enhancing its external validity thanks to the use of new tools and new study subjects. Second, we perform a systematic characterization of these methods, both quantitatively and qualitatively with an extensive manual analysis of 101 pseudo-tested methods. The first part of the study confirms Niedermayr's results: pseudo-tested methods exist in all our subjects. Our in-depth characterization of pseudotested methods leads to two key insights: pseudo-tested methods are significantly less tested than the other methods; yet, for most of them, the developers would not pay the testing price to fix this situation. This calls for future work on targeted test generation to specify those pseudo-tested methods without spending developer time.
AI Reasoning Systems: PAC and Applied Methods
Venue: arXiv cs.AI 2018
Year: 2018

Learning and logic are distinct and remarkable approaches to prediction. Machine learning has experienced a surge in popularity because it is robust to noise and achieves high performance; however, ML experiences many issues with knowledge transfer and extrapolation. In contrast, logic is easily intepreted, and logical rules are easy to chain and transfer between systems; however, inductive logic is brittle to noise. We then explore the premise of combining learning with inductive logic into AI Reasoning Systems. Specifically, we summarize findings from PAC learning (conceptual graphs, robust logics, knowledge infusion) and deep learning (DSRL, $\partial$ILP, DeepLogic) by reproducing proofs of tractability, presenting algorithms in pseudocode, highlighting results, and synthesizing between fields. We conclude with suggestions for integrated models by combining the modules listed above and with a list of unsolved (likely intractable) problems.
Cyber-Physical System for Energy-Efficient Stadium Operation: Methodology and Experimental Validation
Venue: arXiv cs.SY 2018
Year: 2018

The environmental impacts of medium to large scale buildings receive substantial attention in research, industry, and media. This paper studies the energy savings potential of a commercial soccer stadium during day-to-day operation. Buildings of this kind are characterized by special purpose system installations like grass heating systems and by event-driven usage patterns. This work presents a methodology to holistically analyze the stadiums characteristics and integrate its existing instrumentation into a Cyber-Physical System, enabling to deploy different control strategies flexibly. In total, seven different strategies for controlling the studied stadiums grass heating system are developed and tested in operation. Experiments in winter season 2014/2015 validated the strategies impacts within the real operational setup of the Commerzbank Arena, Frankfurt, Germany. With 95% confidence, these experiments saved up to 66% of median daily weather-normalized energy consumption. Extrapolated to an average heating season, this corresponds to savings of 775 MWh and 148 t of CO2 emissions. In winter 2015/2016 an additional predictive nighttime heating experiment targeted lower temperatures, which increased the savings to up to 85%, equivalent to 1 GWh (197 t CO2) in an average winter. Beyond achieving significant energy savings, the different control strategies also met the target temperature levels to the satisfaction of the stadiums operational staff. While the case study constitutes a significant part, the discussions dedicated to the transferability of this work to other stadiums and other building types show that the concepts and the approach are of general nature. Furthermore, this work demonstrates the first successful application of Deep Belief Networks to regress and predict the thermal evolution of building systems.
Characterising AT-free Graphs with BFS
Venue: arXiv cs.DM 2018
Year: 2018

An asteroidal triple free graph is a graph such that for every independent triple of vertices no path between any two avoids the third. In a recent result from Corneil and Stacho, these graphs were characterised through a linear vertex ordering called an AT-free order. Here, we use techniques from abstract convex geometry to improve on this result by giving a vertex order characterisation with stronger structural properties and thus resolve an open question by Corneil and Stacho. These orderings are generated by a modification of BFS which runs in polynomial time. Furthermore, we give a linear time algorithm which employs multiple applications of (L)BFS to compute AT-free orders in claw-free AT-free graphs and a generalisation of these.
Newton-Krylov PDE-constrained LDDMM in the space of band-limited vector fields
Venue: arXiv cs.CV 2018
Year: 2018

PDE-constrained Large Deformation Diffeomorphic Metric Mapping is a particularly interesting framework of physically meaningful diffeomorphic registration methods. Newton-Krylov optimization has shown an excellent numerical accuracy and an extraordinarily fast convergence rate in this framework. However, the most significant limitation of PDE-constrained LDDMM is the huge computational complexity, that hinders the extensive use in Computational Anatomy applications. In this work, we propose two PDE-constrained LDDMM methods parameterized in the space of band-limited vector fields and we evaluate their performance with respect to the most related state of the art methods. The parameterization in the space of band-limited vector fields dramatically alleviates the computational burden avoiding the computation of the high-frequency components of the velocity fields that would be suppressed by the action of the low-pass filters involved in the computation of the gradient and the Hessian-vector products. Besides, the proposed methods have shown an improved accuracy with respect to the benchmark methods.
Improving 3D NAND Flash Memory Lifetime by Tolerating Early Retention Loss and Process Variation
Venue: arXiv cs.AR 2018
Year: 2018

Compared to planar (i.e., two-dimensional) NAND flash memory, 3D NAND flash memory uses a new flash cell design, and vertically stacks dozens of silicon layers in a single chip. This allows 3D NAND flash memory to increase storage density using a much less aggressive manufacturing process technology than planar NAND flash memory. The circuit-level and structural changes in 3D NAND flash memory significantly alter how different error sources affect the reliability of the memory. In this paper, through experimental characterization of real, state-of-the-art 3D NAND flash memory chips, we find that 3D NAND flash memory exhibits three new error sources that were not previously observed in planar NAND flash memory: (1) layer-to-layer process variation, where the average error rate of each 3D-stacked layer in a chip is significantly different; (2) early retention loss, a new phenomenon where the number of errors due to charge leakage increases quickly within several hours after programming; and (3) retention interference, a new phenomenon where the rate at which charge leaks from a flash cell is dependent on the data value stored in the neighboring cell. Based on our experimental results, we develop new analytical models of layer-to-layer process variation and retention loss in 3D NAND flash memory. Motivated by our new findings and models, we develop four new techniques to mitigate process variation and early retention loss in 3D NAND flash memory. These four techniques are complementary, and can be combined together to significantly improve flash memory reliability. Compared to a state-of-the-art baseline, our techniques, when combined, improve flash memory lifetime by 1.85x. Alternatively, if a NAND flash vendor wants to keep the lifetime of the 3D NAND flash memory device constant, our techniques reduce the storage overhead required to hold error correction information by 78.9%.
Information-Theoretic Limits of Strategic Communication
Venue: arXiv cs.IT 2018
Year: 2018

In this article, we investigate strategic information transmission over a noisy channel. This problem has been widely investigated in Economics, when the communication channel is perfect. Unlike in Information Theory, both encoder and decoder have distinct objectives and choose their encoding and decoding strategies accordingly. This approach radically differs from the conventional Communication paradigm, which assumes transmitters are of two types: either they have a common goal, or they act as opponent, e.g. jammer, eavesdropper. We formulate a point-to-point source-channel coding problem with state information, in which the encoder and the decoder choose their respective encoding and decoding strategies in order to maximize their long-run utility functions. This strategic coding problem is at the interplay between Wyner-Ziv's scenario and the Bayesian persuasion game of Kamenica-Gentzkow. We characterize a single-letter solution and we relate it to the previous results by using the concavification method. This confirms the benefit of sending encoded data bits even if the decoding process is not supervised, e.g. when the decoder is an autonomous device. Our solution has two interesting features: it might be optimal not to use all channel resources; the informational content impacts the encoding process, since utility functions capture preferences on source symbols.
New/s/leak 2.0 - Multilingual Information Extraction and Visualization for Investigative Journalism
Venue: arXiv cs.CL 2018
Year: 2018

Investigative journalism in recent years is confronted with two major challenges: 1) vast amounts of unstructured data originating from large text collections such as leaks or answers to Freedom of Information requests, and 2) multi-lingual data due to intensified global cooperation and communication in politics, business and civil society. Faced with these challenges, journalists are increasingly cooperating in international networks. To support such collaborations, we present the new version of new/s/leak 2.0, our open-source software for content-based searching of leaks. It includes three novel main features: 1) automatic language detection and language-dependent information extraction for 40 languages, 2) entity and keyword visualization for efficient exploration, and 3) decentral deployment for analysis of confidential data from various formats. We illustrate the new analysis capabilities with an exemplary case study.
On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
Venue: arXiv cs.DS 2018
Year: 2018

We show that for any regular matroid on $m$ elements and any $α\geq 1$, the number of $α$-minimum circuits, or circuits whose size is at most an $α$-multiple of the minimum size of a circuit in the matroid is bounded by $m^{O(α^2)}$. This generalizes a result of Karger for the number of $α$-minimum cuts in a graph. As a consequence, we obtain similar bounds on the number of $α$-shortest vectors in "totally unimodular" lattices and on the number of $α$-minimum weight codewords in "regular" codes.
Extending the D-Wave with support for Higher Precision Coefficients
Venue: arXiv cs.ET 2018
Year: 2018

D-Wave only guarantees to support coefficients with 4 to 5 bits of resolution or precision. This paper describes a method to extend the functionality of the D-Wave to solve problems that require the support of higher precision coefficients.
Domain-Specific Human-Inspired Binarized Statistical Image Features for Iris Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Binarized statistical image features (BSIF) have been successfully used for texture analysis in many computer vision tasks, including iris recognition and biometric presentation attack detection. One important point is that all applications of BSIF in iris recognition have used the original BSIF filters, which were trained on image patches extracted from natural images. This paper tests the question of whether domain-specific BSIF can give better performance than the default BSIF. The second important point is in the selection of image patches to use in training for BSIF. Can image patches derived from eye-tracking experiments, in which humans perform an iris recognition task, give better performance than random patches? Our results say that (1) domain-specific BSIF features can out-perform the default BSIF features, and (2) selecting image patches in a task-specific manner guided by human performance can out-perform selecting random patches. These results are important because BSIF is often regarded as a generic texture tool that does not need any domain adaptation, and human-task-guided selection of patches for training has never (to our knowledge) been done. This paper follows the reproducible research requirements, and the new iris-domain-specific BSIF filters, the patches used in filter training, the database used in testing and the source codes of the designed iris recognition method are made available along with this paper to facilitate applications of this concept.
QR2: A Third-party Query Reranking Service Over Web Databases
Venue: arXiv cs.DB 2018
Year: 2018

The ranked retrieval model has rapidly become the de-facto way for search query processing in web databases. Despite the extensive efforts on designing better ranking mechanisms, in practice, many such databases fail to address the diverse and sometimes contradicting preferences of users. In this paper, we present QR2, a third-party service that uses nothing but the public search interface of a web database and enables the on-the-fly processing of queries with any user-specified ranking functions, no matter if the ranking function is supported by the database or not.
Beyond Data and Model Parallelism for Deep Neural Networks
Venue: arXiv cs.DC 2018
Year: 2018

The computational requirements for training deep neural networks (DNNs) have grown to the point that it is now standard practice to parallelize training. Existing deep learning systems commonly use data or model parallelism, but unfortunately, these strategies often result in suboptimal parallelization performance. In this paper, we define a more comprehensive search space of parallelization strategies for DNNs called SOAP, which includes strategies to parallelize a DNN in the Sample, Operation, Attribute, and Parameter dimensions. We also propose FlexFlow, a deep learning framework that uses guided randomized search of the SOAP space to find a fast parallelization strategy for a specific parallel machine. To accelerate this search, FlexFlow introduces a novel execution simulator that can accurately predict a parallelization strategy's performance and is three orders of magnitude faster than prior approaches that have to execute each strategy. We evaluate FlexFlow with six real-world DNN benchmarks on two GPU clusters and show that FlexFlow can increase training throughput by up to 3.8x over state-of-the-art approaches, even when including its search time, and also improves scalability.
Fast Block Structure Determination in AV1-based Multiple Resolutions Video Encoding
Venue: arXiv cs.MM 2018
Year: 2018

The widely used adaptive HTTP streaming requires an efficient algorithm to encode the same video to different resolutions. In this paper, we propose a fast block structure determination algorithm based on the AV1 codec that accelerates high resolution encoding, which is the bottle-neck of multiple resolutions encoding. The block structure similarity across resolutions is modeled by the fineness of frame detail and scale of object motions, this enables us to accelerate high resolution encoding based on low resolution encoding results. The average depth of a block's co-located neighborhood is used to decide early termination in the RDO process. Encoding results show that our proposed algorithm reduces encoding time by 30.1%-36.8%, while keeping BD-rate low at 0.71%-1.04%. Comparing to the state-of-the-art, our method halves performance loss without sacrificing time savings.
Motion Planning for Multiple Unit-Ball Robots in $\mathbb{R}^d$
Venue: arXiv cs.CG 2018
Year: 2018

We present a decoupled algorithm for motion planning for a collection of unit-balls moving among polyhedral obstacles in $\mathbb{R}^d$, for any $d \ge 2$. We assume that the robots have revolving areas in the vicinity of their start and target positions: Revolving areas are regions where robots can maneuver in order to give way to another moving robot. Given that this assumption is fulfilled, the algorithm is complete, namely it is guaranteed to find a solution or report that none exists. A key goal in our design is to make the revolving areas as economical as possible and in particular to allow different revolving areas to overlap. This makes the analysis rather involved but in return makes the algorithm conceptually fairly simple. We show that for the case of $m$ unit-discs moving among polygonal obstacles of total complexity $n$ in $\mathbb{R}^2$, the algorithm can be executed in $O(n^2m + m(m+n)\log(m+n))$ time. We implemented the algorithm for this case and tested it on several scenarios, for which we show experimental results for up to $1000$ robots. Finally, we address the problem of choosing the order of execution of the paths in decoupled algorithms that locally solve interferences and show that finding the optimal order of execution is NP-hard. This motivated us to develop a heuristic for choosing the order; we describe the heuristic and demonstrate its effectiveness in certain scenarios.