OpenRaiser/Intern-Atlas huggingface dataset:
A Complexity Theory for Hard Enumeration Problems
Venue: arXiv cs.CC 2017
Year: 2017

Complexity theory provides a wealth of complexity classes for analyzing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, the tools provided by complexity theory for this important class of problems are very limited. In particular, complexity classes analogous to the polynomial hierarchy and an appropriate notion of problem reduction are missing. In this work, we lay the foundations for a complexity theory of hard enumeration problems by proposing a hierarchy of complexity classes and by investigating notions of reductions for enumeration problems.
Asymptotic expansions for moments of number of comparisons used by the randomized quick sort algorithm
Venue: arXiv cs.DS 2017
Year: 2017

We calculate asymptotic expansions for the moments of number of comparisons used by the randomized quick sort algorithm using the singularity analysis of certain generating functions.
Design Mining Microbial Fuel Cell Cascades
Venue: arXiv cs.NE 2017
Year: 2017

Microbial fuel cells (MFCs) perform wastewater treatment and electricity production through the conversion of organic matter using microorganisms. For practical applications, it has been suggested that greater efficiency can be achieved by arranging multiple MFC units into physical stacks in a cascade with feedstock flowing sequentially between units. In this paper, we investigate the use of computational intelligence to physically explore and optimise (potentially) heterogeneous MFC designs in a cascade, i.e. without simulation. Conductive structures are 3-D printed and inserted into the anodic chamber of each MFC unit, augmenting a carbon fibre veil anode and affecting the hydrodynamics, including the feedstock volume and hydraulic retention time, as well as providing unique habitats for microbial colonisation. We show that it is possible to use design mining to identify new conductive inserts that increase both the cascade power output and power density.
Small-footprint Highway Deep Neural Networks for Speech Recognition
Venue: arXiv cs.CL 2017
Year: 2017

State-of-the-art speech recognition systems typically employ neural network acoustic models. However, compared to Gaussian mixture models, deep neural network (DNN) based acoustic models often have many more model parameters, making it challenging for them to be deployed on resource-constrained platforms, such as mobile devices. In this paper, we study the application of the recently proposed highway deep neural network (HDNN) for training small-footprint acoustic models. HDNNs are a depth-gated feedforward neural network, which include two types of gate functions to facilitate the information flow through different layers. Our study demonstrates that HDNNs are more compact than regular DNNs for acoustic modeling, i.e., they can achieve comparable recognition accuracy with many fewer model parameters. Furthermore, HDNNs are more controllable than DNNs: the gate functions of an HDNN can control the behavior of the whole network using a very small number of model parameters. Finally, we show that HDNNs are more adaptable than DNNs. For example, simply updating the gate functions using adaptation data can result in considerable gains in accuracy. We demonstrate these aspects by experiments using the publicly available AMI corpus, which has around 80 hours of training data.
Learning Robust Video Synchronization without Annotations
Venue: arXiv cs.CV 2017
Year: 2017

Aligning video sequences is a fundamental yet still unsolved component for a broad range of applications in computer graphics and vision. Most classical image processing methods cannot be directly applied to related video problems due to the high amount of underlying data and their limit to small changes in appearance. We present a scalable and robust method for computing a non-linear temporal video alignment. The approach autonomously manages its training data for learning a meaningful representation in an iterative procedure each time increasing its own knowledge. It leverages on the nature of the videos themselves to remove the need for manually created labels. While previous alignment methods similarly consider weather conditions, season and illumination, our approach is able to align videos from data recorded months apart.
A 9.52 dB NCG FEC scheme and 164 bits/cycle low-complexity product decoder architecture
Venue: arXiv cs.AR 2017
Year: 2017

Powerful Forward Error Correction (FEC) schemes are used in optical communications to achieve bit-error rates below $10^{-15}$. These FECs follow one of two approaches: concatenation of simpler hard-decision codes or usage of inherently powerful soft-decision codes. The first approach yields lower Net Coding Gains (NCGs), but can usually work at higher code rates and have lower complexity decoders. In this work, we propose a novel FEC scheme based on a product code and a post-processing technique. It can achieve an NCG of 9.52~dB at a BER of $10^{-15}$ and 9.96~dB at a BER of $10^{-18}$, an error-correction performance that sits between that of current hard-decision and soft-decision FECs. A decoder architecture is designed, tested on FPGA and synthesized in 65 nm CMOS technology: its 164 bits/cycle worst-case information throughput can reach 100 Gb/s at the achieved frequency of 609~MHz. Its complexity is shown to be lower than that of hard-decision decoders in literature, and an order of magnitude lower than the estimated complexity of soft-decision decoders.
Improved constructions of nested code pairs
Venue: arXiv cs.IT 2017
Year: 2017

Two new constructions of linear code pairs $C_2 \subset C_1$ are given for which the codimension and the relative minimum distances $M_1(C_1,C_2)$, $M_1(C_2^\perp,C_1^\perp)$ are good. By this we mean that for any two out of the three parameters the third parameter of the constructed code pair is large. Such pairs of nested codes are indispensable for the determination of good linear ramp secret sharing schemes [35]. They can also be used to ensure reliable communication over asymmetric quantum channels [47]. The new constructions result from carefully applying the Feng-Rao bounds [18,27] to a family of codes defined from multivariate polynomials and Cartesian product point sets.
Learning variable length units for SMT between related languages via Byte Pair Encoding
Venue: arXiv cs.CL 2017
Year: 2017

We explore the use of segments learnt using Byte Pair Encoding (referred to as BPE units) as basic units for statistical machine translation between related languages and compare it with orthographic syllables, which are currently the best performing basic units for this translation task. BPE identifies the most frequent character sequences as basic units, while orthographic syllables are linguistically motivated pseudo-syllables. We show that BPE units modestly outperform orthographic syllables as units of translation, showing up to 11% increase in BLEU score. While orthographic syllables can be used only for languages whose writing systems use vowel representations, BPE is writing system independent and we show that BPE outperforms other units for non-vowel writing systems too. Our results are supported by extensive experimentation spanning multiple language families and writing systems.
Partial Derivatives for Context-Free Languages: From $μ$-Regular Expressions to Pushdown Automata
Venue: arXiv cs.FL 2017
Year: 2017

We extend Antimirov's partial derivatives from regular expressions to $μ$-regular expressions that describe context-free languages. We prove the correctness of partial derivatives as well as the finiteness of the set of iterated partial derivatives. The latter are used as pushdown symbols in our construction of a nondeterministic pushdown automaton, which generalizes Antimirov's NFA construction.
A Polynomial Kernel for Distance-Hereditary Vertex Deletion
Venue: arXiv cs.DS 2017
Year: 2017

A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. The Distance-Hereditary Vertex Deletion problem asks, given a graph $G$ on $n$ vertices and an integer $k$, whether there is a set $S$ of at most $k$ vertices in $G$ such that $G-S$ is distance-hereditary. This problem is important due to its connection to the graph parameter rank-width that distance-hereditary graphs are exactly graphs of rank-width at most $1$. Eiben, Ganian, and Kwon (MFCS' 16) proved that Distance-Hereditary Vertex Deletion can be solved in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$, and asked whether it admits a polynomial kernelization. We show that this problem admits a polynomial kernel, answering this question positively. For this, we use a similar idea for obtaining an approximate solution for Chordal Vertex Deletion due to Jansen and Pilipczuk (SODA' 17) to obtain an approximate solution with $\mathcal{O}(k^3\log n)$ vertices when the problem is a YES-instance, and we exploit the structure of split decompositions of distance-hereditary graphs to reduce the total size.
Large-Scale Classification of IPv6-IPv4 Siblings with Variable Clock Skew
Venue: arXiv cs.NI 2017
Year: 2017

Linking the growing IPv6 deployment to existing IPv4 addresses is an interesting field of research, be it for network forensics, structural analysis, or reconnaissance. In this work, we focus on classifying pairs of server IPv6 and IPv4 addresses as siblings, i.e., running on the same machine. Our methodology leverages active measurements of TCP timestamps and other network characteristics, which we measure against a diverse ground truth of 682 hosts. We define and extract a set of features, including estimation of variable (opposed to constant) remote clock skew. On these features, we train a manually crafted algorithm as well as a machine-learned decision tree. By conducting several measurement runs and training in cross-validation rounds, we aim to create models that generalize well and do not overfit our training data. We find both models to exceed 99% precision in train and test performance. We validate scalability by classifying 149k siblings in a large-scale measurement of 371k sibling candidates. We argue that this methodology, thoroughly cross-validated and likely to generalize well, can aid comparative studies of IPv6 and IPv4 behavior in the Internet. Striving for applicability and replicability, we release ready-to-use source code and raw data from our study.
Learning a Probabilistic Latent Space of Object Shapes via 3D Generative-Adversarial Modeling
Venue: arXiv cs.CV 2017
Year: 2017

We study the problem of 3D object generation. We propose a novel framework, namely 3D Generative Adversarial Network (3D-GAN), which generates 3D objects from a probabilistic space by leveraging recent advances in volumetric convolutional networks and generative adversarial nets. The benefits of our model are three-fold: first, the use of an adversarial criterion, instead of traditional heuristic criteria, enables the generator to capture object structure implicitly and to synthesize high-quality 3D objects; second, the generator establishes a mapping from a low-dimensional probabilistic space to the space of 3D objects, so that we can sample objects without a reference image or CAD models, and explore the 3D object manifold; third, the adversarial discriminator provides a powerful 3D shape descriptor which, learned without supervision, has wide applications in 3D object recognition. Experiments demonstrate that our method generates high-quality 3D objects, and our unsupervisedly learned features achieve impressive performance on 3D object recognition, comparable with those of supervised learning methods.
Bounding Average-energy Games
Venue: arXiv cs.LO 2017
Year: 2017

We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) remained open; in particular, so far there was no known upper bound on the memory that is required for winning strategies. By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the density of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove EXPSPACE-hardness of this problem. Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions.
Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
Venue: arXiv cs.SI 2017
Year: 2017

Percolation threshold of a network is the critical value such that when nodes or edges are randomly selected with probability below the value, the network is fragmented but when the probability is above the value, a giant component connecting large portion of the network would emerge. Assessing the percolation threshold of networks has wide applications in network reliability, information spread, epidemic control, etc. The theoretical approach so far to assess the percolation threshold is mainly based on spectral radius of adjacency matrix or non-backtracking matrix, which is limited to dense graphs or locally treelike graphs, and is less effective for sparse networks with non-negligible amount of triangles and loops. In this paper, we study high-order non-backtracking matrices and their application to assessing percolation threshold. We first define high-order non-backtracking matrices and study the properties of their spectral radii. Then we focus on 2nd-order non-backtracking matrix and demonstrate analytically that the reciprocal of its spectral radius gives a tighter lower bound than those of adjacency and standard non-backtracking matrices. We further build a smaller size matrix with the same largest eigenvalue as the 2nd-order non-backtracking matrix to improve computation efficiency. Finally, we use both synthetic networks and 42 real networks to illustrate that the use of 2nd-order non-backtracking matrix does give better lower bound for assessing percolation threshold than adjacency and standard non-backtracking matrices.
Intelligent Time-Adaptive Transient Stability Assessment System
Venue: arXiv cs.SY 2017
Year: 2017

Online identification of post-contingency transient stability is essential in power system control, as it facilitates the grid operator to decide and coordinate system failure correction control actions. Utilizing machine learning methods with synchrophasor measurements for transient stability assessment has received much attention recently with the gradual deployment of wide-area protection and control systems. In this paper, we develop a transient stability assessment system based on the long short-term memory network. By proposing a temporal self-adaptive scheme, our proposed system aims to balance the trade-off between assessment accuracy and response time, both of which may be crucial in real-world scenarios. Compared with previous work, the most significant enhancement is that our system learns from the temporal data dependencies of the input data, which contributes to better assessment accuracy. In addition, the model structure of our system is relatively less complex, speeding up the model training process. Case studies on three power systems demonstrate the efficacy of the proposed transient stability assessment system.
Buffer-Aided Relaying For The Two-Hop Full-Duplex Relay Channel With Self-Interference
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the two-hop full-duplex (FD) relay channel with self-interference and fading, which is comprised of a source, an FD relay, and a destination, where a direct source-destination link does not exist and the FD relay is impaired by self-interference. For this channel, we propose three buffer-aided relaying schemes with adaptive reception-transmission at the FD relay for the cases when the source and the relay both perform adaptive-power allocation, fixed-power allocation, and fixed-rate transmission, respectively. The proposed buffer-aided relaying schemes significantly improve the achievable rate and the throughput of the considered relay channel by enabling the FD relay to adaptively select to either receive, transmit, or simultaneously receive and transmit in a given time slot based on the qualities of the receiving, transmitting, and self-interference channels. Our numerical results show that significant performance gains are achieved using the proposed buffer-aided relaying schemes compared to conventional FD relaying, where the FD relay is forced to always simultaneously receive and transmit, and to buffer-aided half-duplex relaying, where the half-duplex relay cannot simultaneously receive and transmit.
On the Expressive Power of User-Defined Effects: Effect Handlers, Monadic Reflection, Delimited Control
Venue: arXiv cs.LO 2017
Year: 2017

We compare the expressive power of three programming abstractions for user-defined computational effects: Bauer and Pretnar's effect handlers, Filinski's monadic reflection, and delimited control without answer-type-modification. This comparison allows a precise discussion about the relative expressiveness of each programming abstraction. It also demonstrates the sensitivity of the relative expressiveness of user-defined effects to seemingly orthogonal language features. We present three calculi, one per abstraction, extending Levy's call-by-push-value. For each calculus, we present syntax, operational semantics, a natural type-and-effect system, and, for effect handlers and monadic reflection, a set-theoretic denotational semantics. We establish their basic meta-theoretic properties: safety, termination, and, where applicable, soundness and adequacy. Using Felleisen's notion of a macro translation, we show that these abstractions can macro-express each other, and show which translations preserve typeability. We use the adequate finitary set-theoretic denotational semantics for the monadic calculus to show that effect handlers cannot be macro-expressed while preserving typeability either by monadic reflection or by delimited control. We supplement our development with a mechanised Abella formalisation.
Generalized I-MMSE for K-User Gaussian Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we generalize the fundamental relation between the mutual information and the minimum mean squared error (MMSE) by Guo, Shamai, and Verdu [1] to K-User Gaussian channels. We prove that the derivative of the multiuser mutual information with respect to the signal to noise ratio (SNR) is equal to the total MMSE plus a covariance term with respect to the cross correlation of the multiuser input estimates, the channels and the precoding matrices. We shed light that such relation is a generalized I-MMSE with one step lookahead and lookback, applied to the Successive Interference Cancellation (SIC) in the decoding process.
Partition-based Caching in Large-Scale SIC-Enabled Wireless Networks
Venue: arXiv cs.IT 2017
Year: 2017

Existing designs for content dissemination do not fully explore and exploit potential caching and computation capabilities in advanced wireless networks. In this paper, we propose two partition-based caching designs, i.e., a coded caching design based on Random Linear Network Coding and an uncoded caching design. We consider the analysis and optimization of the two caching designs in a large-scale successive interference cancelation (SIC)-enabled wireless network. First, under each caching design, by utilizing tools from stochastic geometry and adopting appropriate approximations, we derive a tractable expression for the successful transmission probability in the general file size regime. To further obtain design insights, we also derive closed-form expressions for the successful transmission probability in the small and large file size regimes, respectively. Then, under each caching design, we consider the successful transmission probability maximization in the general file size regime, which is an NP-hard problem. By exploring structural properties, we successfully transform the original optimization problem into a Multiple-Choice Knapsack Problem (MCKP), and obtain a near optimal solution with 1/2 approximation guarantee and polynomial complexity. We also obtain closed-form asymptotically optimal solutions. The analysis and optimization results show the advantage of the coded caching design over the uncoded caching design, and reveal the impact of caching and SIC capabilities. Finally, by numerical results, we show that the two proposed caching designs achieve significant performance gains over some baseline caching designs.
Understanding and Exploiting Design-Induced Latency Variation in Modern DRAM Chips
Venue: arXiv cs.AR 2017
Year: 2017

Variation has been shown to exist across the cells within a modern DRAM chip. We empirically demonstrate a new form of variation that exists within a real DRAM chip, induced by the design and placement of different components in the DRAM chip. Our goals are to understand design-induced variation that exists in real, state-of-the-art DRAM chips, exploit it to develop low-cost mechanisms that can dynamically find and use the lowest latency at which to operate a DRAM chip reliably, and, thus, improve overall system performance while ensuring reliable system operation. To this end, we first experimentally demonstrate and analyze designed-induced variation in modern DRAM devices by testing and characterizing 96 DIMMs (768 DRAM chips). Our characterization identifies DRAM regions that are vulnerable to errors, if operated at lower latency, and finds consistency in their locations across a given DRAM chip generation, due to design-induced variation. Based on our extensive experimental analysis, we develop two mechanisms that reliably reduce DRAM latency. First, DIVA Profiling uses runtime profiling to dynamically identify the lowest DRAM latency that does not introduce failures. DIVA Profiling exploits design-induced variation and periodically profiles only the vulnerable regions to determine the lowest DRAM latency at low cost. Our second mechanism, DIVA Shuffling, shuffles data such that values stored in vulnerable regions are mapped to multiple error-correcting code (ECC) codewords. Combined together, our two mechanisms reduce read/write latency by 40.0%/60.5%, which translates to an overall system performance improvement of 14.7%/13.7%/13.8% (in 2-/4-/8-core systems) across a variety of workloads, while ensuring reliable operation.
Termination of Monotone Programs
Venue: arXiv cs.LO 2017
Year: 2017

We present an efficient approach to prove termination of monotone programs with integer variables, an expressive class of loops that is often encountered in computer programs. Our approach is based on a lightweight static analysis method and takes advantage of simple %nice properties of monotone functions. Our preliminary implementation %beats shows that our tool has an advantage over existing tools and can prove termination for a high percentage of loops for a class of benchmarks.