OpenRaiser/Intern-Atlas huggingface dataset:
An Illustrated Introduction to the Truncated Fourier Transform
Venue: arXiv cs.SC 2016
Year: 2016

The Truncated Fourier Transform (TFT) is a variation of the Discrete Fourier Transform (DFT/FFT) that allows for input vectors that do NOT have length $2^n$ for $n$ a positive integer. We present the univariate version of the TFT, originally due to Joris van der Hoeven, heavily illustrating the presentation in order to make these methods accessible to a broader audience.
Conflict Resolution: a First-Order Resolution Calculus with Decision Literals and Conflict-Driven Clause Learning
Venue: arXiv cs.LO 2016
Year: 2016

This paper defines the (first-order) conflict resolution calculus: an extension of the resolution calculus inspired by techniques used in modern SAT-solvers. The resolution inference is restricted to (first-order) unit-propagation and the calculus is extended with a mechanism for assuming decision literals and a new inference rule for clause learning, which is a first-order generalization of the propositional conflict-driven clause learning (CDCL) procedure. The calculus is sound (because it can be simulated by natural deduction) and refutationally complete (because it can simulate resolution), and these facts are proven in detail here.
A Framework for the Adoption of Biometric ATM Authentication in the Kenyan Banks
Venue: arXiv cs.CY 2016
Year: 2016

The use of ATMs has become fundamental in the banking industry owing to the values transacted using these systems and their 24/7 usage. Although several researchers have studied the role of biometrics in security applications for financial institutions, no systematic empirical research has been applied to studying the role of organizational characteristics and contextual factors in the Kenyan financial sector. This study sought to develop a framework for the adoption of biometric ATMs in the Kenyan banking sector, apply the developed framework to study factors influencing adoption of biometric ATM authentication and validate the developed conceptual framework. A survey was used to collect quantitative data from the ATM users which was then analysed using factor analysis and multiple regression analysis. The study established that performance expectancy, effort expectancy, social influence and user privacy were key determinants for biometric ATMs acceptance, adoption and usage. The study further demonstrated that age, gender and experience were moderating factors on effort expectancy with experience further moderating performance expectancy, effort expectancy, social influence and user privacy. Key words: Key words: framework, adoption, authentication, financial institutions
Modeling of technological performance trends using design theory
Venue: arXiv cs.CY 2016
Year: 2016

Functional technical performance usually follows an exponential dependence on time but the rate of change (the exponent) varies greatly among technological domains. This paper presents a simple model that provides an explanatory foundation for these phenomena based upon the inventive design process. The model assumes that invention - novel and useful design- arises through probabilistic analogical transfers that combine existing knowledge by combining existing individual operational ideas to arrive at new individual operating ideas. The continuing production of individual operating ideas relies upon injection of new basic individual operating ideas that occurs through coupling of science and technology simulations. The individual operational ideas that result from this process are then modeled as being assimilated in components of artifacts characteristic of a technological domain. According to the model, two effects (differences in interactions among components for different domains and differences in scaling laws for different domains) account for the differences found in improvement rates among domains whereas the analogical transfer process is the source of the exponential behavior. The model is supported by a number of known empirical facts: further empirical research is suggested to independently assess further predictions made by the model.
Secure symmetric ciphers over the real field
Venue: arXiv cs.CR 2016
Year: 2016

Most cryptosystems are defined over finite algebraic structures where arithmetic operations are performed modulo natural numbers. This applies to private key as well as to public key ciphers. No secure cryptosystems defined over the field of real numbers are known. In this work, we demonstrate the feasibility of constructing secure symmetric key ciphers defined over the field of real numbers. We consider the security of ciphers introduced in a previous work and based on solving linear and non-linear equations numerically. We complement the design of those ciphers to satisfy the requirements of secure systems and, consequently, extend them into composite ciphers with multiple encryptions. We show security enhancements by estimating the uncertainty in finding the keys using a measure based on Shannon's entropy function.
High-Quality, Low-Delay Music Coding in the Opus Codec
Venue: arXiv cs.MM 2016
Year: 2016

The IETF recently standardized the Opus codec as RFC6716. Opus targets a wide range of real-time Internet applications by combining a linear prediction coder with a transform coder. We describe the transform coder, with particular attention to the psychoacoustic knowledge built into the format. The result out-performs existing audio codecs that do not operate under real-time constraints.
Deep Feature-based Face Detection on Mobile Devices
Venue: arXiv cs.CV 2016
Year: 2016

We propose a deep feature-based face detector for mobile devices to detect user's face acquired by the front facing camera. The proposed method is able to detect faces in images containing extreme pose and illumination variations as well as partial faces. The main challenge in developing deep feature-based algorithms for mobile devices is the constrained nature of the mobile platform and the non-availability of CUDA enabled GPUs on such devices. Our implementation takes into account the special nature of the images captured by the front-facing camera of mobile devices and exploits the GPUs present in mobile devices without CUDA-based frameorks, to meet these challenges.
Fast DGT Based Receivers for GFDM in Broadband Channels
Venue: arXiv cs.IT 2016
Year: 2016

Generalized frequency division multiplexing (GFDM) is a recent multicarrier 5G waveform candidate with flexibility of pulse shaping filters. However, the flexibility of choosing a pulse shaping filter may result in inter carrier interference (ICI) and inter symbol interference (ISI), which becomes more severe in a broadband channel. In order to eliminate the ISI and ICI, based on discrete Gabor transform (DGT), in this paper, a transmit GFDM signal is first treated as an inverse DGT (IDGT), and then a frequency-domain DGT is formulated to recover (as a receiver) the GFDM signal. Furthermore, to reduce the complexity, a suboptimal frequency-domain DGT called local DGT (LDGT) is developed. Some analyses are also given for the proposed DGT based receivers.
Kinsey Reporter: Citizen Science for Sex Research
Venue: arXiv cs.CY 2016
Year: 2016

Kinsey Reporter is a global mobile app to share, explore, and visualize anonymous data about sex. Reports are submitted via smartphone, then visualized on a website or downloaded for offline analysis. In this paper we present the major features of the Kinsey Reporter citizen science platform designed to preserve the anonymity of its contributors, and preliminary data analyses that suggest questions for future research.
Simulation Results of User Behavior-Aware Scheduling Based on Time-Frequency Resource Conversion
Venue: arXiv cs.NI 2016
Year: 2016

Integrating time-frequency resource conversion (TFRC), a new network resource allocation strategy, with call admission control can not only increase the cell capacity but also reduce network congestion effectively. However, the optimal setting of TFRC-oriented call admission control suffers from the curse of dimensionality, due to Markov chain-based optimization in a high-dimensional space. To address the scalability issue of TFRC, in [1] we extend the study of TFRC into the area of scheduling. Specifically, we study downlink scheduling based on TFRC for an LTE-type cellular network, to maximize service delivery. The service scheduling of interest is formulated as a joint request, channel and slot allocation problem which is NP-hard. An offline deflation and sequential fixing based algorithm (named DSFRB) with only polynomial-time complexity is proposed to solve the problem. For practical online implementation, two TFRC-enabled low-complexity algorithms, modified Smith ratio algorithm (named MSR) and modified exponential capacity algorithm (named MEC), are proposed as well. In this report, we present detailed numerical results of the proposed offline and online algorithms, which not only show the effectiveness of the proposed algorithms but also corroborate the advantages of the proposed TFRC-based schedule techniques in terms of quality-of-service (QoS) provisioning for each user and revenue improvement for a service operator.
Q($λ$) with Off-Policy Corrections
Venue: arXiv cs.AI 2016
Year: 2016

We propose and analyze an alternate approach to off-policy multi-step temporal difference learning, in which off-policy returns are corrected with the current Q-function in terms of rewards, rather than with the target policy in terms of transition probabilities. We prove that such approximate corrections are sufficient for off-policy convergence both in policy evaluation and control, provided certain conditions. These conditions relate the distance between the target and behavior policies, the eligibility trace parameter and the discount factor, and formalize an underlying tradeoff in off-policy TD($λ$). We illustrate this theoretical relationship empirically on a continuous-state control task.
Deconvolutional Feature Stacking for Weakly-Supervised Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

A weakly-supervised semantic segmentation framework with a tied deconvolutional neural network is presented. Each deconvolution layer in the framework consists of unpooling and deconvolution operations. 'Unpooling' upsamples the input feature map based on unpooling switches defined by corresponding convolution layer's pooling operation. 'Deconvolution' convolves the input unpooled features by using convolutional weights tied with the corresponding convolution layer's convolution operation. The unpooling-deconvolution combination helps to eliminate less discriminative features in a feature extraction stage, since output features of the deconvolution layer are reconstructed from the most discriminative unpooled features instead of the raw one. This results in reduction of false positives in a pixel-level inference stage. All the feature maps restored from the entire deconvolution layers can constitute a rich discriminative feature set according to different abstraction levels. Those features are stacked to be selectively used for generating class-specific activation maps. Under the weak supervision (image-level labels), the proposed framework shows promising results on lesion segmentation in medical images (chest X-rays) and achieves state-of-the-art performance on the PASCAL VOC segmentation dataset in the same experimental condition.
Symmetry Breaking Predicates for SAT-based DFA Identification
Venue: arXiv cs.FL 2016
Year: 2016

It was shown before that the NP-hard problem of deterministic finite automata (DFA) identification can be effectively translated to Boolean satisfiability (SAT). Modern SAT-solvers can tackle hard DFA identification instances efficiently. We present a technique to reduce the problem search space by enforcing an enumeration of DFA states in depth-first search (DFS) or breadth-first search (BFS) order. We propose symmetry breaking predicates, which can be added to Boolean formulae representing various DFA identification problems. We show how to apply this technique to DFA identification from both noiseless and noisy data. Also we propose a method to identify all automata of the desired size. The proposed approach outperforms the current state-of-the-art DFASAT method for DFA identification from noiseless data. A big advantage of the proposed approach is that it allows to determine exactly the existence or non-existence of a solution of the noisy DFA identification problem unlike metaheuristic approaches such as genetic algorithms.
Exploration of Faulty Hamiltonian Graphs
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An exploration algorithm, for a given network and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm.
Order-to-chaos transition in the hardness of random Boolean satisfiability problems
Venue: arXiv cs.CC 2016
Year: 2016

Transient chaos is an ubiquitous phenomenon characterizing the dynamics of phase space trajectories evolving towards a steady state attractor in physical systems as diverse as fluids, chemical reactions and condensed matter systems. Here we show that transient chaos also appears in the dynamics of certain efficient algorithms searching for solutions of constraint satisfaction problems that include scheduling, circuit design, routing, database problems or even Sudoku. In particular, we present a study of the emergence of hardness in Boolean satisfiability ($k$-SAT), a canonical class of constraint satisfaction problems, by using an analog deterministic algorithm based on a system of ordinary differential equations. Problem hardness is defined through the escape rate $κ$, an invariant measure of transient chaos of the dynamical system corresponding to the analog algorithm, and it expresses the rate at which the trajectory approaches a solution.We show that for a given density of constraints and fixed number of Boolean variables $N$, the hardness of formulas in random $k$-SAT ensembles has a wide variation, approximable by a lognormal distribution. We also show that when increasing the density of constraints $α$, hardness appears through a second-order phase transition at $α_χ$ in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic. A similar behavior is found in 4-SAT as well, however, such transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter $κ\sim N^{B|α- α_χ|^{1-γ}}$ with $0< γ< 1$. We demonstrate that the transition is generated by the appearance of metastable basins in the solution space as the density of constraints $α$ is increased.
A Simple Condition for the Existence of Transversals
Venue: arXiv cs.DM 2016
Year: 2016

Hall's Theorem is a basic result in Combinatorics which states that the obvious necesssary condition for a finite family of sets to have a transversal is also sufficient. We present a sufficient (but not necessary) condition on the sizes of the sets in the family and the sizes of their intersections so that a transversal exists. Using this, we prove that in a bipartite graph $G$ (bipartition $\{A, B\}$), without 4-cycles, if $°(v) \geq \sqrt{2e|A|}$ for all $v \in A$, then $G$ has a matching of size $|A|$.
Density-based Denoising of Point Cloud
Venue: arXiv cs.CV 2016
Year: 2016

Point cloud source data for surface reconstruction is usually contaminated with noise and outliers. To overcome this deficiency, a density-based point cloud denoising method is presented to remove outliers and noisy points. First, particle-swam optimization technique is employed for automatically approximating optimal bandwidth of multivariate kernel density estimation to ensure the robust performance of density estimation. Then, mean-shift based clustering technique is used to remove outliers through a thresholding scheme. After removing outliers from the point cloud, bilateral mesh filtering is applied to smooth the remaining points. The experimental results show that this approach, comparably, is robust and efficient.
Category theoretic semantics for theorem proving in logic programming: embracing the laxness
Venue: arXiv cs.LO 2016
Year: 2016

A propositional logic program $P$ may be identified with a $P_fP_f$-coalgebra on the set of atomic propositions in the program. The corresponding $C(P_fP_f)$-coalgebra, where $C(P_fP_f)$ is the cofree comonad on $P_fP_f$, describes derivations by resolution. Using lax semantics, that correspondence may be extended to a class of first-order logic programs without existential variables. The resulting extension captures the proofs by term-matching resolution in logic programming. Refining the lax approach, we further extend it to arbitrary logic programs. We also exhibit a refinement of Bonchi and Zanasi's saturation semantics for logic programming that complements lax semantics.
Diffusion of innovation in large scale graphs
Venue: arXiv cs.SI 2016
Year: 2016

Will a new smartphone application diffuse deeply in the population or will it sink into oblivion soon? To predict this, we argue that common models of spread of innovations based on cascade dynamics or epidemics may not be fully adequate. Therefore we propose a novel stochastic network dynamics modeling the spread of a new technological asset, whose adoption is based on the word-of-mouth and the persuasion strength increases the more the product is diffused. In this paper we carry on an analysis on large scale graphs to show off how the parameters of the model, the topology of the graph and, possibly, the initial diffusion of the asset, determine whether the spread of the asset is successful or not. In particular, by means of stochastic dominations and deterministic approximations, we provide some general results for a large class of expansive graphs. Finally we present numerical simulations trying to expand the analytical results we proved to even more general topologies.
HeSP: a simulation framework for solving the task scheduling-partitioning problem on heterogeneous architectures
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we describe HeSP, a complete simulation framework to study a general task scheduling-partitioning problem on heterogeneous architectures, which treats recursive task partitioning and scheduling decisions on equal footing. Considering recursive partitioning as an additional degree of freedom, tasks can be dynamically partitioned or merged at runtime for each available processor type, exposing additional or reduced degrees of parallelism as needed. Our simulations reveal that, for a specific class of dense linear algebra algorithms taken as a driving example, simultaneous decisions on task scheduling and partitioning yield significant performance gains on two different heterogeneous platforms: a highly heterogeneous CPU-GPU system and a low-power asymmetric big.LITTLE ARM platform. The insights extracted from the framework can be further applied to actual runtime task schedulers in order to improve performance on current or future architectures and for different task-parallel codes.
Multihead Multitrack Detection with ITI Estimation in Next Generation Magnetic Recording System
Venue: arXiv cs.IT 2016
Year: 2016

Multitrack detection with array-head reading is a promising technique proposed for next generation magnetic storage systems. The multihead multitrack (MHMT) system is characterized by intersymbol interference (ISI) in the downtrack direction and intertrack interference (ITI) in the crosstrack direction. Constructing the trellis of a MHMT maximum likelihood (ML) detector requires knowledge of the ITI, which is generally unknown at the receiver. In addition, to retain efficiency, the ML detector requires a static estimate of the ITI, whose true value may in reality vary. In this paper we propose a modified ML detector on the $n$-head, $n$-track ($n$H$n$T) channel which could efficiently track the change of ITI, and adapt to new estimates. The trellis used in the proposed detector is shown to be independent of the ITI level. A gain loop structure is used to estimate the ITI. Simulation results show that the proposed detector offers a performance advantage in settings where complexity constraints limit the traditional ML detector to use a static ITI estimate.
A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One
Venue: arXiv cs.FL 2016
Year: 2016

Branching VASS (BVASS) generalise vector addition systems with states by allowing for special branching transitions that can non-deterministically distribute a counter value between two control states. A run of a BVASS consequently becomes a tree, and reachability is to decide whether a given configuration is the root of a reachability tree. This paper shows P-completeness of reachability in BVASS in dimension one, the first decidability result for reachability in a subclass of BVASS known so far. Moreover, we show that coverability and boundedness in BVASS in dimension one are P-complete as well.
Repetition-Free Derivability from a Regular Grammar is NP-Hard
Venue: arXiv cs.FL 2016
Year: 2016

We prove the NP-hardness of the problem whether a given word can be derived from a given regular grammar without repeated occurrence of any nonterminal.
ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
Venue: arXiv cs.DS 2016
Year: 2016

We present ABRA, a suite of algorithms that compute and maintain probabilistically-guaranteed, high-quality, approximations of the betweenness centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms rely on random sampling and their analysis leverages on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, this is the first application of these concepts to the field of graph analysis. The results of our experimental evaluation show that our approach is much faster than exact methods, and vastly outperforms, in both speed and number of samples, current state-of-the-art algorithms with the same quality guarantees.
Efficient approaches for escaping higher order saddle points in non-convex optimization
Venue: arXiv cs.LG 2016
Year: 2016

Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such that the first and second order derivatives cannot distinguish them with local optima. In this paper we use higher order derivatives to escape these saddle points: we design the first efficient algorithm guaranteed to converge to a third order local optimum (while existing techniques are at most second order). We also show that it is NP-hard to extend this further to finding fourth order local optima.