OpenRaiser/Intern-Atlas huggingface dataset:
Identifying an Honest ${\rm EXP}^{\rm NP}$ Oracle Among Many
Venue: arXiv cs.CC 2015
Year: 2015

We provide a general framework to remove short advice by formulating the following computational task for a function $f$: given two oracles at least one of which is honest (i.e. correctly computes $f$ on all inputs) as well as an input, the task is to compute $f$ on the input with the help of the oracles by a probabilistic polynomial-time machine, which we shall call a selector. We characterize the languages for which short advice can be removed by the notion of selector: a paddable language has a selector if and only if short advice of a probabilistic machine that accepts the language can be removed under any relativized world. Previously, instance checkers have served as a useful tool to remove short advice of probabilistic computation. We indicate that existence of instance checkers is a property stronger than that of removing short advice: although no instance checker for ${\rm EXP}^{\rm NP}$-complete languages exists unless ${\rm EXP}^{\rm NP} = {\rm NEXP}$, we prove that there exists a selector for any ${\rm EXP}^{\rm NP}$-complete language, by building on the proof of ${\rm MIP} = {\rm NEXP}$ by Babai, Fortnow, and Lund (1991).
Accuracy Enhancement of Pickett Tunnelling Barrier Memristor Model
Venue: arXiv cs.ET 2015
Year: 2015

Titanium dioxide (TiO2) memristors exhibit complex conduction mechanism. Several models of different complexity have been developed in order to mimic the experimental results for physical behaviors observed in memristor devices. Pickett's tunneling barrier model describes the TiO2 memristors, and utilizes complex derivative of tunnel barrier width. It attains a large error in the ON switching region. Variety of research consider it as the reference model for the TiO2 memristors. In this paper, we first analyze the theory of operation of the memristor and discuss Pickett's model. Then, we propose a modification to its derivative functions to provide a lower error and closer agreement with physical behavior. This modification is represented by two additional fitting parameters to damp or accelerate the tunnel width derivative. Also, we incorporate a hard limiter term to limit the tunnel width to its physical extremes 1 nm and 2 nm. We run simulations to test the model modifications and we compare the results to the experimental and original Pickett's model results. The modified model more closely resembles the experimental behavior of TiO2 memristors and potentially enables the memristor to be used as a multilevel memory.
Empirical Study of Traffic Velocity Distribution and its Effect on VANETs Connectivity
Venue: arXiv cs.NI 2015
Year: 2015

In this article we use real traffic data to confirm that vehicle velocities follow Gaussian distribution in steady state traffic regimes (free-flow, and congestion). We also show that in the transition between free-flow and congestion, the velocity distribution is better modeled by generalized extreme value distribution (GEV). We study the effect of the different models on estimating the probability distribution of connectivity duration between vehicles in vehicular ad-hoc networks.
Multiple State EFN Transistors
Venue: arXiv cs.ET 2015
Year: 2015

Electrostatically Formed Nanowire (EFN) based transistors have been suggested in the past as gas sensing devices. These transistors are multiple gate transistors in which the source to drain conduction path is determined by the bias applied to the back gate, and two junction gates. If a specific bias is applied to the side gates, the conduction band electrons between them are confined to a well-defined area forming a narrow channel- the Electrostatically Formed Nanowire. Recent work has shown that by applying non-symmetric bias on the side gates, the lateral position of the EFN can be controlled. We propose a novel Multiple State EFN Transistor (MSET) that utilizes this degree of freedom for the implementation of complete multiplexer functionality in a single transistor like device. The multiplexer functionality allows a very simple implementation of binary and multiple valued logic functions.
An efficient multi-core implementation of a novel HSS-structured multifrontal solver using randomized sampling
Venue: arXiv cs.MS 2015
Year: 2015

We present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination, and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factorization leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to 7 fold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-of-the-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK -- STRUctured Matrices PACKage, which also has a distributed memory component for dense rank-structured matrices.
A Holistic Approach for Modeling and Synthesis of Image Processing Applications for Heterogeneous Computing Architectures
Venue: arXiv cs.CV 2015
Year: 2015

Image processing applications are common in every field of our daily life. However, most of them are very complex and contain several tasks with different complexities which result in varying requirements for computing architectures. Nevertheless, a general processing scheme in every image processing application has a similar structure, called image processing pipeline: (1) capturing an image, (2) pre-processing using local operators, (3) processing with global operators and (4) post-processing using complex operations. Therefore, application-specialized hardware solutions based on heterogeneous architectures are used for image processing. Unfortunately the development of applications for heterogeneous hardware architectures is challenging due to the distribution of computational tasks among processors and programmable logic units. Nowadays, image processing systems are started from scratch which is time-consuming, error-prone and inflexible. A new methodology for modeling and implementing is needed in order to reduce the development time of heterogenous image processing systems. This paper introduces a new holistic top down approach for image processing systems. Two challenges have to be investigated. First, designers ought to be able to model their complete image processing pipeline on an abstract layer using UML. Second, we want to close the gap between the abstract system and the system architecture.
Distributed Analysis for Diagnosability in Concurrent Systems
Venue: arXiv cs.SE 2015
Year: 2015

Complex systems often exhibit unexpected faults that are difficult to handle. Such systems are desirable to be diagnosable, i.e. faults can be automatically detected as they occur (or shortly afterwards), enabling the system to handle the fault or recover. A system is diagnosable if it is possible to detect every fault, in a finite time after they occurred, by only observing the available information from the system. Complex systems are usually built from simpler components running concurrently. We study how to infer the diagnosability property of a complex system (distributed and with multiple faults) from a parallelized analysis of the diagnosability of each of its components synchronizing with fault free versions of the others. In this paper we make the following contributions: (1) we address the diagnosability problem of concurrent systems with arbitrary faults occurring freely in each component. (2) We distribute the diagnosability analysis and illustrate our approach with examples. Moreover, (3) we present a prototype tool that implements our techniques showing promising results.
Rational Kernels for Arabic Stemming and Text Classification
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we address the problems of Arabic Text Classification and stemming using Transducers and Rational Kernels. We introduce a new stemming technique based on the use of Arabic patterns (Pattern Based Stemmer). Patterns are modelled using transducers and stemming is done without depending on any dictionary. Using transducers for stemming, documents are transformed into finite state transducers. This document representation allows us to use and explore rational kernels as a framework for Arabic Text Classification. Stemming experiments are conducted on three word collections and classification experiments are done on the Saudi Press Agency dataset. Results show that our approach, when compared with other approaches, is promising specially in terms of Accuracy, Recall and F1.
A Channel Coding Approach for Physical-Layer Authentication
Venue: arXiv cs.IT 2015
Year: 2015

For physical-layer authentication, the authentication tags are often sent concurrently with messages without much bandwidth expansion. In this paper, we present a channel coding approach for physical-layer authentication. The generation of authentication tags can be formulated as an encoding process for an ensemble of codes, where the shared key between Alice and Bob is considered as the input and the message is used to specify a code from the ensemble of codes. Then, we show that the security of physical-layer authentication schemes can be analyzed through decoding and physical-layer authentication schemes can potentially achieve both information-theoretic and computational securities.
Distributed Opportunistic Scheduling for Energy Harvesting Based Wireless Networks: A Two-Stage Probing Approach
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a heterogeneous ad hoc network with multiple transmitter-receiver pairs, in which all transmitters are capable of harvesting renewable energy from the environment and compete for one shared channel by random access. In particular, we focus on two different scenarios: the constant energy harvesting (EH) rate model where the EH rate remains constant within the time of interest and the i.i.d. EH rate model where the EH rates are independent and identically distributed across different contention slots. To quantify the roles of both the energy state information (ESI) and the channel state information (CSI), a distributed opportunistic scheduling (DOS) framework with two-stage probing and save-then-transmit energy utilization is proposed. Then, the optimal throughput and the optimal scheduling strategy are obtained via one-dimension search, i.e., an iterative algorithm consisting of the following two steps in each iteration: First, assuming that the stored energy level at each transmitter is stationary with a given distribution, the expected throughput maximization problem is formulated as an optimal stopping problem, whose solution is proved to exist and then derived for both models; second, for a fixed stopping rule, the energy level at each transmitter is shown to be stationary and an efficient iterative algorithm is proposed to compute its steady-state distribution. Finally, we validate our analysis by numerical results and quantify the throughput gain compared with the best-effort delivery scheme.
The conjugated null space method of blind PSF estimation and deconvolution optimization
Venue: arXiv cs.CV 2015
Year: 2015

We have shown that the vector of the point spread function (PSF) lexicographical presentation belongs to the left side conjugated null space (NS) of the autoregression (AR) matrix operator on condition the AR parameters are common for original and blurred images. The method of the PSF and inverse PSF (IPSF) evaluation in the basis of the NS eigenfunctions is offered. The optimization of the PSF and IPSF shape with the aim of fluctuation elimination is considered in NS spectral domain and image space domain. The function of surface area was used as the regularization functional. Two methods of original image estimate optimization were designed basing on maximum entropy generalization of sought and blurred images conditional probability density and regularization. The first method uses balanced variations of convolutions with the PSF and IPSF to obtaining iterative schema of image optimization. The variations balance is providing by dynamic regularization basing on condition of the iteration process convergence. The regularization has dynamic character because depends on current and previous image estimate variations. The second method implements the regularization of the deconvolution optimization in curved space with metric defined on image estimate surface. The given iterative schemas have fast convergence and therefore can be used for reconstruction of high resolution images series in real time. The NS can be used for design of denoising bilateral linear filter which does not introduce image smoothing.
Generating 56-bit passwords using Markov Models (and Charles Dickens)
Venue: arXiv cs.CR 2015
Year: 2015

We describe a password generation scheme based on Markov models built from English text (specifically, Charles Dickens' *A Tale Of Two Cities*). We show a (linear-running-time) bijection between random bitstrings of any desired length and generated text, ensuring that all passwords are generated with equal probability. We observe that the generated passwords appear to strike a reasonable balance between memorability and security. Using the system, we get 56-bit passwords like 'The cusay is wither?" t', rather than passwords like 'tQ$%Xc4Ef'.
Analysis of Gradient based Algorithm for Signal reconstruction in the Presence of Noise
Venue: arXiv cs.IT 2015
Year: 2015

Common problem in signal processing is reconstruction of the missing signal samples. Missing samples can occur by intentionally omitting signal coefficients to reduce memory requirements, or to speed up the transmission process. Also, noisy signal coefficients can be considered as missing ones, since they have wrong values due to the noise. The reconstruction of these coefficients is demanding task, considered within the Compressive sensing area. Signal with large number of missing samples can be recovered, if certain conditions are satisfied. There is a number of algorithms used for signal reconstruction. In this paper we have analyzed the performance of iterative gradient-based algorithm for sparse signal reconstruction. The parameters influence on the optimal performances of this algorithm is tested. Two cases are observed: non-noisy and noisy signal case.
Graph Grammars, Insertion Lie Algebras, and Quantum Field Theory
Venue: arXiv cs.FL 2015
Year: 2015

Graph grammars extend the theory of formal languages in order to model distributed parallelism in theoretical computer science. We show here that to certain classes of context-free and context-sensitive graph grammars one can associate a Lie algebra, whose structure is reminiscent of the insertion Lie algebras of quantum field theory. We also show that the Feynman graphs of quantum field theories are graph languages generated by a theory dependent graph grammar.
Hybrid coding of visual content and local image features
Venue: arXiv cs.MM 2015
Year: 2015

Distributed visual analysis applications, such as mobile visual search or Visual Sensor Networks (VSNs) require the transmission of visual content on a bandwidth-limited network, from a peripheral node to a processing unit. Traditionally, a Compress-Then-Analyze approach has been pursued, in which sensing nodes acquire and encode the pixel-level representation of the visual content, that is subsequently transmitted to a sink node in order to be processed. This approach might not represent the most effective solution, since several analysis applications leverage a compact representation of the content, thus resulting in an inefficient usage of network resources. Furthermore, coding artifacts might significantly impact the accuracy of the visual task at hand. To tackle such limitations, an orthogonal approach named Analyze-Then-Compress has been proposed. According to such a paradigm, sensing nodes are responsible for the extraction of visual features, that are encoded and transmitted to a sink node for further processing. In spite of improved task efficiency, such paradigm implies the central processing node not being able to reconstruct a pixel-level representation of the visual content. In this paper we propose an effective compromise between the two paradigms, namely Hybrid-Analyze-Then-Compress (HATC) that aims at jointly encoding visual content and local image features. Furthermore, we show how a target tradeoff between image quality and task accuracy might be achieved by accurately allocating the bitrate to either visual content or local features.
The QC Relaxation: Theoretical and Computational Results on Optimal Power Flow
Venue: arXiv cs.CE 2015
Year: 2015

Convex relaxations of the power flow equations and, in particular, the Semi-Definite Programming (SDP) and Second-Order Cone (SOC) relaxations, have attracted significant interest in recent years. The Quadratic Convex (QC) relaxation is a departure from these relaxations in the sense that it imposes constraints to preserve stronger links between the voltage variables through convex envelopes of the polar representation. This paper is a systematic study of the QC relaxation for AC Optimal Power Flow with realistic side constraints. The main theoretical result shows that the QC relaxation is stronger than the SOC relaxation and neither dominates nor is dominated by the SDP relaxation. In addition, comprehensive computational results show that the QC relaxation may produce significant improvements in accuracy over the SOC relaxation at a reasonable computational cost, especially for networks with tight bounds on phase angle differences. The QC and SOC relaxations are also shown to be significantly faster and reliable compared to the SDP relaxation given the current state of the respective solvers.
Plagiarism Detection in Polyphonic Music using Monaural Signal Separation
Venue: arXiv cs.SD 2015
Year: 2015

Given the large number of new musical tracks released each year, automated approaches to plagiarism detection are essential to help us track potential violations of copyright. Most current approaches to plagiarism detection are based on musical similarity measures, which typically ignore the issue of polyphony in music. We present a novel feature space for audio derived from compositional modelling techniques, commonly used in signal separation, that provides a mechanism to account for polyphony without incurring an inordinate amount of computational overhead. We employ this feature representation in conjunction with traditional audio feature representations in a classification framework which uses an ensemble of distance features to characterize pairs of songs as being plagiarized or not. Our experiments on a database of about 3000 musical track pairs show that the new feature space characterization produces significant improvements over standard baselines.
Parsing as Reduction
Venue: arXiv cs.CL 2015
Year: 2015

We reduce phrase-representation parsing to dependency parsing. Our reduction is grounded on a new intermediate representation, "head-ordered dependency trees", shown to be isomorphic to constituent trees. By encoding order information in the dependency labels, we show that any off-the-shelf, trainable dependency parser can be used to produce constituents. When this parser is non-projective, we can perform discontinuous parsing in a very natural manner. Despite the simplicity of our approach, experiments show that the resulting parsers are on par with strong baselines, such as the Berkeley parser for English and the best single system in the SPMRL-2014 shared task. Results are particularly striking for discontinuous parsing of German, where we surpass the current state of the art by a wide margin.
O(1) Time Generation of Adjacent Multiset Combinations
Venue: arXiv cs.DS 2015
Year: 2015

We solve the problem of designing an O(1) time algorithm for generating adjacent multiset combinations in a different approach from Walsh. By the word adjacent, we mean that two adjacent multiset combinations are different at two places by one in their vector forms. Previous O(1) time algorithms for multiset combinations generated non-adjacent multiset combinations. Our algorithm in this paper can be derived from a general framework of combinatorial Gray code, which we characterise to suit our need for combinations and multiset combinations. The central idea is a twisted lexico tree, which is obtained from the lexicographic tree for the given set of combinatorial objects by twisting branches depending on the parity of each node. An iterative algorithm which traverses this tree will generate the given set of combinatorial objects in constant time as well as with a fixed number of changes from the present combinatorial object to the next.
Parameter Estimation of Jelinski-Moranda Model Based on Weighted Nonlinear Least Squares and Heteroscedasticity
Venue: arXiv cs.OH 2015
Year: 2015

Parameter estimation method of Jelinski-Moranda (JM) model based on weighted nonlinear least squares (WNLS) is proposed. The formulae of resolving the parameter WNLS estimation (WNLSE) are derived, and the empirical weight function and heteroscedasticity problem are discussed. The effects of optimization parameter estimation selection based on maximum likelihood estimation (MLE) method, least squares estimation (LSE) method and weighted nonlinear least squares estimation (WNLSE) method are also investigated. Two strategies of heteroscedasticity decision and weighting methods embedded in JM model prediction process are also investigated. The experimental results on standard software reliability analysis database-Naval Tactical Data System (NTDS) and three datasets used by J.D. Musa demonstrate that WNLSE method can be superior to LSE and MLE under the relative error (RE) criterion.
Multinational War is Hard
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we show that the problem of determining whether one player can force a win in a multiplayer version of the children's card game War is PSPACE-hard. The same reduction shows that a related problem, asking whether a player can survive k rounds, is PSPACE-complete when k is polynomial in the size of the input.
CSCW Principles to Support Citizen Science
Venue: arXiv cs.CY 2015
Year: 2015

Citizen science changes the way scientific research is pursued. It opens up data collection and analysis to the general public, to the wisdom of crowds. In this emerging area, there is much research to be done to better understand how we can develop citizen science infrastructure and continue the democratization of science. In creating such systems, there is much we can learn from principles that have emerged out of computer-supported cooperative work (CSCW) research. In this paper, I use a nine-step framework to highlight where CSCW knowledge can contribute.
Ranking Templates for Linear Loops
Venue: arXiv cs.LO 2015
Year: 2015

We present a new method for the constraint-based synthesis of termination arguments for linear loop programs based on linear ranking templates. Linear ranking templates are parameterized, well-founded relations such that an assignment to the parameters gives rise to a ranking function. Our approach generalizes existing methods and enables us to use templates for many different ranking functions with affine-linear components. We discuss templates for multiphase, nested, piecewise, parallel, and lexicographic ranking functions. These ranking templates can be combined to form more powerful templates. Because these ranking templates require both strict and non-strict inequalities, we use Motzkin's transposition theorem instead of Farkas' lemma to transform the generated $\exists\forall$-constraint into an $\exists$-constraint.