OpenRaiser/Intern-Atlas huggingface dataset:
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Venue: arXiv cs.CC 2016
Year: 2016

We investigate the computational complexity of the problem of counting the maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain {0,1}. A satisfying assignment is maximal if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Gamma, #MaximalCSP(Gamma) denotes the problem of counting the maximal satisfying assignments, given an input CSP with constraints in Gamma. We give a complexity dichotomy for the problem of exactly counting the maximal satisfying assignments and a complexity trichotomy for the problem of approximately counting them. Relative to the problem #CSP(Gamma), which is the problem of counting all satisfying assignments, the maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.
Fundamental concepts in the Cyclus nuclear fuel cycle simulation framework
Venue: arXiv cs.SE 2016
Year: 2016

As nuclear power expands, technical, economic, political, and environmental analyses of nuclear fuel cycles by simulators increase in importance. To date, however, current tools are often fleet-based rather than discrete and restrictively licensed rather than open source. Each of these choices presents a challenge to modeling fidelity, generality, efficiency, robustness, and scientific transparency. The Cyclus nuclear fuel cycle simulator framework and its modeling ecosystem incorporate modern insights from simulation science and software architecture to solve these problems so that challenges in nuclear fuel cycle analysis can be better addressed. A summary of the Cyclus fuel cycle simulator framework and its modeling ecosystem are presented. Additionally, the implementation of each is discussed in the context of motivating challenges in nuclear fuel cycle simulation. Finally, the current capabilities of Cyclus are demonstrated for both open and closed fuel cycles.
A Higher-Order Abstract Syntax Approach to Verified Transformations on Functional Programs
Venue: arXiv cs.PL 2016
Year: 2016

We describe an approach to the verified implementation of transformations on functional programs that exploits the higher-order representation of syntax. In this approach, transformations are specified using the logic of hereditary Harrop formulas. On the one hand, these specifications serve directly as implementations, being programs in the language Lambda Prolog. On the other hand, they can be used as input to the Abella system which allows us to prove properties about them and thereby about the implementations. We argue that this approach is especially effective in realizing transformations that analyze binding structure. We do this by describing concise encodings in Lambda Prolog for transformations like typed closure conversion and code hoisting that are sensitive to such structure and by showing how to prove their correctness using Abella.
Regular expressions for decoding of neural network outputs
Venue: arXiv cs.NE 2016
Year: 2016

This article proposes a convenient tool for decoding the output of neural networks trained by Connectionist Temporal Classification (CTC) for handwritten text recognition. We use regular expressions to describe the complex structures expected in the writing. The corresponding finite automata are employed to build a decoder. We analyze theoretically which calculations are relevant and which can be avoided. A great speed-up results from an approximation. We conclude that the approximation most likely fails if the regular expression does not match the ground truth which is not harmful for many applications since the low probability will be even underestimated. The proposed decoder is very efficient compared to other decoding methods. The variety of applications reaches from information retrieval to full text recognition. We refer to applications where we integrated the proposed decoder successfully.
A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers unconstrained convex optimization problems with time-varying objective functions. We propose algorithms with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and correction steps, while sampling the problem data at a constant rate of $1/h$, where $h$ is the length of the sampling interval. The prediction step is derived by analyzing the iso-residual dynamics of the optimality conditions. The correction step adjusts for the distance between the current prediction and the optimizer at each time step, and consists either of one or multiple gradient steps or Newton steps, which respectively correspond to the gradient trajectory tracking (GTT) or Newton trajectory tracking (NTT) algorithms. Under suitable conditions, we establish that the asymptotic error incurred by both proposed methods behaves as $O(h^2)$, and in some cases as $O(h^4)$, which outperforms the state-of-the-art error bound of $O(h)$ for correction-only methods in the gradient-correction step. Moreover, when the characteristics of the objective function variation are not available, we propose approximate gradient and Newton tracking algorithms (AGT and ANT, respectively) that still attain these asymptotical error bounds. Numerical simulations demonstrate the practical utility of the proposed methods and that they improve upon existing techniques by several orders of magnitude.
Wearable Computing for Health and Fitness: Exploring the Relationship between Data and Human Behaviour
Venue: arXiv cs.CY 2016
Year: 2016

Health and fitness wearable technology has recently advanced, making it easier for an individual to monitor their behaviours. Previously self generated data interacts with the user to motivate positive behaviour change, but issues arise when relating this to long term mention of wearable devices. Previous studies within this area are discussed. We also consider a new approach where data is used to support instead of motivate, through monitoring and logging to encourage reflection. Based on issues highlighted, we then make recommendations on the direction in which future work could be most beneficial.
The Shortest Path Problem with Edge Information Reuse is NP-Complete
Venue: arXiv cs.CC 2016
Year: 2016

We show that the following variation of the single-source shortest path problem is NP-complete. Let a weighted, directed, acyclic graph $G=(V,E,w)$ with source and sink vertices $s$ and $t$ be given. Let in addition a mapping $f$ on $E$ be given that associates information with the edges (e.g., a pointer), such that $f(e)=f(e')$ means that edges $e$ and $e'$ carry the same information; for such edges it is required that $w(e)=w(e')$. The length of a simple $st$ path $U$ is the sum of the weights of the edges on $U$ but edges with $f(e)=f(e')$ are counted only once. The problem is to determine a shortest such $st$ path. We call this problem the \emph{edge information reuse shortest path problem}. It is NP-complete by reduction from 3SAT.
Subgraph-based filterbanks for graph signals
Venue: arXiv cs.IT 2016
Year: 2016

We design a critically-sampled compact-support biorthogonal transform for graph signals, via graph filterbanks. Instead of partitioning the nodes in two sets so as to remove one every two nodes in the filterbank downsampling operations, the design is based on a partition of the graph in connected subgraphs. Coarsening is achieved by defining one "supernode" for each subgraph and the edges for this coarsened graph derives from the connectivity between the subgraphs. Unlike the "one every two nodes" downsampling on bipartite graphs, this coarsening operation does not have an exact formulation in the graph Fourier domain. Instead, we rely on the local Fourier bases of each subgraph to define filtering operations. We apply successfully this method to decompose graph signals, and show promising performance on compression and denoising.
The adaptation of Shamir's protocol for increasing the security of a mobile environment
Venue: arXiv cs.CR 2016
Year: 2016

The aim of the paper is to provide a solution which increases the security of a mobile environment for both individuals and for workers in an enterprise. The proposed solution adapts Shamir's approach for sharing a secret for encryption key management. One part of the key is stored on a Bluetooth (or NFC) wristband or on an enterprise server, while a mobile device is used to store all the rest. The approach can be applied for both securing documents and voice data. The solution is supported by a mathematical formality which is missing in the currently known advice within cryptographic folklore.
Energy Harvesting Wireless Sensor Networks: Delay Analysis Considering Energy Costs of Sensing and Transmission
Venue: arXiv cs.IT 2016
Year: 2016

Energy harvesting (EH) provides a means of greatly enhancing the lifetime of wireless sensor nodes. However, the randomness inherent in the EH process may cause significant delay for performing sensing operation and transmitting the sensed information to the sink. Unlike most existing studies on the delay performance of EH sensor networks, where only the energy consumption of transmission is considered, we consider the energy costs of both sensing and transmission. Specifically, we consider an EH sensor that monitors some status environmental property and adopts a harvest-then-use protocol to perform sensing and transmission. To comprehensively study the delay performance, we consider two complementary metrics and analytically derive their statistics: (i) update age - measuring the time taken from when information is obtained by the sensor to when the sensed information is successfully transmitted to the sink, i.e., how timely the updated information at the sink is, and (ii) update cycle - measuring the time duration between two consecutive successful transmissions, i.e., how frequently the information at the sink is updated. Our results show that the consideration of sensing energy cost leads to an important tradeoff between the two metrics: more frequent updates result in less timely information available at the sink.
A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration
Venue: arXiv cs.NA 2016
Year: 2016

We describe a subdivision algorithm for isolating the complex roots of a polynomial $F\in\mathbb{C}[x]$. Given an oracle that provides approximations of each of the coefficients of $F$ to any absolute error bound and given an arbitrary square $\mathcal{B}$ in the complex plane containing only simple roots of $F$, our algorithm returns disjoint isolating disks for the roots of $F$ in $\mathcal{B}$. Our complexity analysis bounds the absolute error to which the coefficients of $F$ have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square $\mathcal{B}$, namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the \emph{benchmark problem}, namely, to isolate all the roots of a polynomial of degree $n$ with integer coefficients of bit size less than $τ$, our algorithm needs $\tilde O(n^3+n^2τ)$ bit operations, which is comparable to the record bound of Pan (2002). It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a "soft-test" to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.
Deep Boltzmann Machines in Estimation of Distribution Algorithms for Combinatorial Optimization
Venue: arXiv cs.NE 2016
Year: 2016

Estimation of Distribution Algorithms (EDAs) require flexible probability models that can be efficiently learned and sampled. Deep Boltzmann Machines (DBMs) are generative neural networks with these desired properties. We integrate a DBM into an EDA and evaluate the performance of this system in solving combinatorial optimization problems with a single objective. We compare the results to the Bayesian Optimization Algorithm. The performance of DBM-EDA was superior to BOA for difficult additively decomposable functions, i.e., concatenated deceptive traps of higher order. For most other benchmark problems, DBM-EDA cannot clearly outperform BOA, or other neural network-based EDAs. In particular, it often yields optimal solutions for a subset of the runs (with fewer evaluations than BOA), but is unable to provide reliable convergence to the global optimum competitively. At the same time, the model building process is computationally more expensive than that of other EDAs using probabilistic models from the neural network family, such as DAE-EDA.
A Review of Features for the Discrimination of Twitter Users: Application to the Prediction of Offline Influence
Venue: arXiv cs.CL 2016
Year: 2016

Many works related to Twitter aim at characterizing its users in some way: role on the service (spammers, bots, organizations, etc.), nature of the user (socio-professional category, age, etc.), topics of interest , and others. However, for a given user classification problem, it is very difficult to select a set of appropriate features, because the many features described in the literature are very heterogeneous, with name overlaps and collisions, and numerous very close variants. In this article, we review a wide range of such features. In order to present a clear state-of-the-art description, we unify their names, definitions and relationships, and we propose a new, neutral, typology. We then illustrate the interest of our review by applying a selection of these features to the offline influence detection problem. This task consists in identifying users which are influential in real-life, based on their Twitter account and related data. We show that most features deemed efficient to predict online influence, such as the numbers of retweets and followers, are not relevant to this problem. However, We propose several content-based approaches to label Twitter users as Influencers or not. We also rank them according to a predicted influence level. Our proposals are evaluated over the CLEF RepLab 2014 dataset, and outmatch state-of-the-art methods.
Optimal Rate-Diverse Wireless Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes an encoding/decoding framework for achieving the optimal channel capacities of the two-user broadcast channel where each user (receiver) has the message targeted for the other user (receiver) as side information. Since the link qualities of the channels from the base station to the two users are different, their respective single-user non-broadcast channel capacities are also different. A goal is to simultaneously achieve/approach the single-user non-broadcast channel capacities of the two users with a single broadcast transmission by applying network coding. This is referred to as the \emph{rate-diverse wireless network coding} problem. For this problem, this paper presents a capacity-achieving framework based on linear- structured nested lattice codes. The significance of the proposed framework, besides its theoretical optimality, is that it suggests a general design principle for linear rate-diverse wireless network coding going beyond the use of lattice codes. We refer to this design principle as the \emph{principle of virtual single-user channels}. Guided by this design principle, we propose two implementations of our encoding/decoding framework using practical linear codes amenable to decoding with affordable complexities: the first implementation is based on Low Density Lattice Codes (LDLC) and the second implementation is based on Bit-interleaved Coded Modulation (BICM). These two implementations demonstrate the validity and performance advantage of our framework.
Fractional coverings, greedy coverings, and rectifier networks
Venue: arXiv cs.CC 2016
Year: 2016

A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix $M$ that has a $1$ in the entry $(i,j)$ iff there is a path from the $j$th source to the $i$th sink. The smallest number of edges in a rectifier network computing $M$ is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two well-known techniques that have hitherto found little to no applications in this theory. Both of them build on a basic fact that depth-$2$ rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. We obtain new results by using fractional and greedy coverings (defined in the standard way). First, we show that all fractional coverings of the so-called full triangular matrix have cost at least $n\log n$. This provides (a fortiori) a new proof of the tight lower bound on its depth-$2$ complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-$2$ complexity of the Kneser-Sierpiński (disjointness) matrix. The previous upper bound is $O(n^{1.28})$, and we improve it to $O(n^{1.17})$, while the best known lower bound is $Ω(n^{1.16})$. Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
A Survey on Legacy and Emerging Technologies for Public Safety Communications
Venue: arXiv cs.NI 2016
Year: 2016

Effective emergency and natural disaster management depend on the efficient mission-critical voice and data communication between first responders and victims. Land Mobile Radio System (LMRS) is a legacy narrowband technology used for critical voice communications with limited use for data applications. Recently Long Term Evolution (LTE) emerged as a broadband communication technology that has a potential to transform the capabilities of public safety technologies by providing broadband, ubiquitous, and mission-critical voice and data support. For example, in the United States, FirstNet is building a nationwide coast-to-coast public safety network based of LTE broadband technology. This paper presents a comparative survey of legacy and the LTE-based public safety networks, and discusses the LMRS-LTE convergence as well as mission-critical push-to-talk over LTE. A simulation study of LMRS and LTE band class 14 technologies is provided using the NS-3 open source tool. An experimental study of APCO-25 and LTE band class 14 is also conducted using software-defined radio, to enhance the understanding of the public safety systems. Finally, emerging technologies that may have strong potential for use in public safety networks are reviewed.
A Sound and Complete Hoare Logic for Dynamically-Typed, Object-Oriented Programs -- Extended Version --
Venue: arXiv cs.PL 2016
Year: 2016

A simple dynamically-typed, (purely) object-oriented language is defined. A structural operational semantics as well as a Hoare-style program logic for reasoning about programs in the language in multiple notions of correctness are given. The Hoare logic is proved to be both sound and (relative) complete and is -- to the best of our knowledge -- the first such logic presented for a dynamically-typed language.
Yield, Area and Energy Optimization in Stt-MRAMs using failure aware ECC
Venue: arXiv cs.OH 2016
Year: 2016

Spin Transfer Torque MRAMs are attractive due to their non-volatility, high density and zero leakage. However, STT-MRAMs suffer from poor reliability due to shared read and write paths. Additionally, conflicting requirements for data retention and write-ability (both related to the energy barrier height of the magnet) makes design more challenging. Furthermore, the energy barrier height depends on the physical dimensions of the free layer. Any variations in the dimensions of the free layer lead to variations in the energy barrier height. In order to address poor reliability of STT-MRAMs, usage of Error Correcting Codes (ECC) have been proposed. Unlike traditional CMOS memory technologies, ECC is expected to correct both soft and hard errors in STT_MRAMs. To achieve acceptable yield with low write power, stronger ECC is required, resulting in increased number of encoded bits and degraded memory efficiency. In this paper, we propose Failure aware ECC (FaECC), which masks permanent faults while maintaining the same correction capability for soft errors without increased encoded bits. Furthermore, we investigate the impact of process variations on run-time reliability of STT-MRAMs. We provide an analysis on the impact of process variations on the life-time of the free layer and retention failures. In order to analyze the effectiveness of our methodology, we developed a cross-layer simulation framework that consists of device, circuit and array level analysis of STT-MRAM memory arrays. Our results show that using FaECC relaxes the requirements on the energy barrier height, which reduces the write energy and results in smaller access transistor size and memory array area. Keywords: STT-MRAM, reliability, Error Correcting Codes, ECC, magnetic memory
VLSI Implementation of Deep Neural Network Using Integral Stochastic Computing
Venue: arXiv cs.NE 2016
Year: 2016

The hardware implementation of deep neural networks (DNNs) has recently received tremendous attention: many applications in fact require high-speed operations that suit a hardware implementation. However, numerous elements and complex interconnections are usually required, leading to a large area occupation and copious power consumption. Stochastic computing has shown promising results for low-power area-efficient hardware implementations, even though existing stochastic algorithms require long streams that cause long latencies. In this paper, we propose an integer form of stochastic computation and introduce some elementary circuits. We then propose an efficient implementation of a DNN based on integral stochastic computing. The proposed architecture has been implemented on a Virtex7 FPGA, resulting in 45% and 62% average reductions in area and latency compared to the best reported architecture in literature. We also synthesize the circuits in a 65 nm CMOS technology and we show that the proposed integral stochastic architecture results in up to 21% reduction in energy consumption compared to the binary radix implementation at the same misclassification rate. Due to fault-tolerant nature of stochastic architectures, we also consider a quasi-synchronous implementation which yields 33% reduction in energy consumption w.r.t. the binary radix implementation without any compromise on performance.