OpenRaiser/Intern-Atlas huggingface dataset:
Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
Venue: arXiv cs.DM 2013
Year: 2013

The conjugacy problem belongs to algorithmic group theory. It is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjugated, i.e., whether there exists some z such that zxz^{-1} = y in G. The conjugacy problem is more difficult than the word problem, in general. We investigate the complexity of the conjugacy problem for two prominent groups: the Baumslag-Solitar group BS(1,2) and the Baumslag(-Gersten) group G(1,2). The conjugacy problem in BS(1,2) is TC^0-complete. To the best of our knowledge BS(1,2) is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G(1,2) is an HNN-extension of BS(1,2). We show that the conjugacy problem is decidable (which has been known before); but our results go far beyond decidability. In particular, we are able to show that conjugacy in G(1,2) can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs conjugacy in G(1,2) can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in G(1,2) by reducing the division problem in power circuits to the conjugacy problem in G(1,2). The complexity of the division problem in power circuits is an open and interesting problem in integer arithmetic.
Recognizing Speech in a Novel Accent: The Motor Theory of Speech Perception Reframed
Venue: arXiv cs.CL 2013
Year: 2013

The motor theory of speech perception holds that we perceive the speech of another in terms of a motor representation of that speech. However, when we have learned to recognize a foreign accent, it seems plausible that recognition of a word rarely involves reconstruction of the speech gestures of the speaker rather than the listener. To better assess the motor theory and this observation, we proceed in three stages. Part 1 places the motor theory of speech perception in a larger framework based on our earlier models of the adaptive formation of mirror neurons for grasping, and for viewing extensions of that mirror system as part of a larger system for neuro-linguistic processing, augmented by the present consideration of recognizing speech in a novel accent. Part 2 then offers a novel computational model of how a listener comes to understand the speech of someone speaking the listener's native language with a foreign accent. The core tenet of the model is that the listener uses hypotheses about the word the speaker is currently uttering to update probabilities linking the sound produced by the speaker to phonemes in the native language repertoire of the listener. This, on average, improves the recognition of later words. This model is neutral regarding the nature of the representations it uses (motor vs. auditory). It serve as a reference point for the discussion in Part 3, which proposes a dual-stream neuro-linguistic architecture to revisits claims for and against the motor theory of speech perception and the relevance of mirror neurons, and extracts some implications for the reframing of the motor theory.
How to Implement Access Rights in an MIS Project
Venue: arXiv cs.CR 2013
Year: 2013

The MIS data is critical to an organization and should be protected from misuse by wrong persons. Although The MIS data is typically meant for the senior managers each MIS report may not be required by every manager. The access to MIS data is determined by the role of an individual in the organization and controlled by the MIS administrator accordingly. The access is generally determined by the following parameters, (a) the type of user (such as staff or manager etc.), (b) the type of data (whether general data or managerial data), (c) level of access (read/ write/ admin access) and (d) special access allocated by MIS admin. By combining all the above four parameters, each individual user can be allocated exact specific rights required to access the MIS.
Higher-order Reverse Automatic Differentiation with emphasis on the third-order
Venue: arXiv cs.MS 2013
Year: 2013

It is commonly assumed that calculating third order information is too expensive for most applications. But we show that the directional derivative of the Hessian ($D^3f(x)\cdot d$) can be calculated at a cost proportional to that of a state-of-the-art method for calculating the Hessian matrix. We do this by first presenting a simple procedure for designing high order reverse methods and applying it to deduce several methods including a reverse method that calculates $D^3f(x)\cdot d$. We have implemented this method taking into account symmetry and sparsity, and successfully calculated this derivative for functions with a million variables. These results indicate that the use of third order information in a general nonlinear solver, such as Halley-Chebyshev methods, could be a practical alternative to Newton's method.
High Precision Arithmetic for Scientific Applications
Venue: arXiv cs.MS 2013
Year: 2013

All but a few digital computers used for scientific computations have supported floating-point and digital arithmetic of rather limited numerical precision. The underlying assumptions were that the systems being studied were basically deterministic and of limited complexity. The ideal scientific paradigm was the orbits of the major planets, which could be observed with high precision, predicted for thousands of years into the future, and extrapolated for thousands of years into the past. Much the same technology that has made computers possible has also provided instrumentation that has vastly expanded the scope and precision of scientific analysis. Complex nonlinear systems exhibiting so-called chaotic dynamics are now fair game for scientists and engineers in every discipline. Today it seems that computers need to enhance the precision of their numerical computations to support the needs of science. However, there is no need to wait for the necessary updates in both hardware and software; it is easy enough to monitor numerical precision with a few minor modifications to existing software.
On the k-Atomicity-Verification Problem
Venue: arXiv cs.DC 2013
Year: 2013

Modern Internet-scale storage systems often provide weak consistency in exchange for better performance and resilience. An important weak consistency property is k-atomicity, which bounds the staleness of values returned by read operations. The k-atomicity-verification problem (or k-AV for short) is the problem of deciding whether a given history of operations is k-atomic. The 1-AV problem is equivalent to verifying atomicity/linearizability, a well-known and solved problem. However, for k > 2, no polynomial-time k-AV algorithm is known. This paper makes the following contributions towards solving the k-AV problem. First, we present a simple 2- AV algorithm called LBT, which is likely to be efficient (quasilinear) for histories that arise in practice, although it is less efficient (quadratic) in the worst case. Second, we present a more involved 2-AV algorithm called FZF, which runs efficiently (quasilinear) even in the worst case. To our knowledge, these are the first algorithms that solve the 2-AV problem fully. Third, we show that the weighted k-AV problem, a natural extension of the k-AV problem, is NP-complete.
Generic Image Classification Approaches Excel on Face Recognition
Venue: arXiv cs.CV 2013
Year: 2013

The main finding of this work is that the standard image classification pipeline, which consists of dictionary learning, feature encoding, spatial pyramid pooling and linear classification, outperforms all state-of-the-art face recognition methods on the tested benchmark datasets (we have tested on AR, Extended Yale B, the challenging FERET, and LFW-a datasets). This surprising and prominent result suggests that those advances in generic image classification can be directly applied to improve face recognition systems. In other words, face recognition may not need to be viewed as a separate object classification problem. While recently a large body of residual based face recognition methods focus on developing complex dictionary learning algorithms, in this work we show that a dictionary of randomly extracted patches (even from non-face images) can achieve very promising results using the image classification pipeline. That means, the choice of dictionary learning methods may not be important. Instead, we find that learning multiple dictionaries using different low-level image features often improve the final classification accuracy. Our proposed face recognition approach offers the best reported results on the widely-used face recognition benchmark datasets. In particular, on the challenging FERET and LFW-a datasets, we improve the best reported accuracies in the literature by about 20% and 30% respectively.
Modularity Index Metrics for Java-Based Open Source Software Projects
Venue: arXiv cs.SE 2013
Year: 2013

Open Source Software (OSS) Projects are gaining popularity these days, and they become alternatives in building software system. Despite many failures in these projects, there are some success stories with one of the identified success factors is modularity. This paper presents the first quantitative software metrics to measure modularity level of Java-based OSS Projects called Modularity Index. This software metrics is formulated by analyzing modularity traits such as size, complexity, cohesion, and coupling of 59 Java-based OSS Projects from sourceforge.net using SONAR tool. These OSS Projects are selected since they have been downloaded more than 100K times and believed to have the required modularity trait to be successful. The software metrics related to modularity in class, package and system level of these projects are extracted and analyzed. The similarities found are then analyzed to determine the class quality, package quality, and then combined with system architecture measure to formulate the Modularity Index. The case study of measuring Modularity Index during the evolution of JFreeChart project has shown that this software metrics is able to identify strengths and potential problems of the project.
Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem
Venue: arXiv cs.DS 2013
Year: 2013

We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival times, arbitrary job deadlines, and unit job execution time. For this problem, we present a lower bound 2.09 on the competitive factor of \emph{any} online algorithms, followed by designing a 5.2-competitive online algorithm. We also point out a false claim made in an existing paper of Shi and Ye regarding a further restricted case of the considered problem. To the best of our knowledge, what we present is the first concrete result concerning online machine-minimizing job scheduling with arbitrary job arrival times and deadlines.
On Exploring Consumers' Technology Foresight Capabilities - An Analysis of 4000 Mobile Service Ideas
Venue: arXiv cs.HC 2013
Year: 2013

Lead user driven innovation and open innovation paradigms seek to involve consumers and common people to innovative product development projects. In order to help developers choose ideas that meet the end users' needs, we undertook a massive collaborative research effort and collected 40000 ideas from 2150 common people about future mobile services that they would like to use. We inspired each people to produce tens of mobile service ideas. In this paper we carry out an analysis for 4000 ideas from the idea database. We had a particular interest in whether peoples' ideas can be used in foreseeing the technology development needs. The results show that end users produce ideas that are conservative more than novel. Therefore, we claim that consumers' technology foresight horizon is limited by the existing technological base. The second finding, linked to the previous one, is that the great majority of the ideas that consumers expressed could be realised utilizing existing technologies. The implication of this finding is that the idea database should be an interesting source of ideas for service developers. The third finding of the study, related to the methodology, is that a vast number of ideas can be collected fairly easily but analyzing them cost effectively is a challenge.
Adaptive Variable Step Algorithm for Missing Samples Recovery in Sparse Signals
Venue: arXiv cs.IT 2013
Year: 2013

Recovery of arbitrarily positioned samples that are missing in sparse signals recently attracted significant research interest. Sparse signals with heavily corrupted arbitrary positioned samples could be analyzed in the same way as compressive sensed signals by omitting the corrupted samples and considering them as unavailable during the recovery process. The reconstruction of missing samples is done by using one of the well known reconstruction algorithms. In this paper we will propose a very simple and efficient adaptive variable step algorithm, applied directly to the concentration measures, without reformulating the reconstruction problem within the standard linear programming form. Direct application of the gradient approach to the nondifferentiable forms of measures lead us to introduce a variable step size algorithm. A criterion for changing adaptive algorithm parameters is presented. The results are illustrated on the examples with sparse signals, including approximately sparse signals and noisy sparse signals.
Energy-Efficient Optimization for Wireless Information and Power Transfer in Large-Scale MIMO Systems Employing Energy Beamforming
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we consider a large-scale multiple-input multiple-output (MIMO) system where the receiver should harvest energy from the transmitter by wireless power transfer to support its wireless information transmission. The energy beamforming in the large-scale MIMO system is utilized to address the challenging problem of long-distance wireless power transfer. Furthermore, considering the limitation of the power in such a system, this letter focuses on the maximization of the energy efficiency of information transmission (bit per Joule) while satisfying the quality-of-service (QoS) requirement, i.e. delay constraint, by jointly optimizing transfer duration and transmit power. By solving the optimization problem, we derive an energy-efficient resource allocation scheme. Numerical results validate the effectiveness of the proposed scheme.
Improved Analyses for SP and CoSaMP Algorithms in Terms of Restricted Isometry Constants
Venue: arXiv cs.IT 2013
Year: 2013

In the context of compressed sensing (CS), both Subspace Pursuit (SP) and Compressive Sampling Matching Pursuit (CoSaMP) are very important iterative greedy recovery algorithms which could reduce the recovery complexity greatly comparing with the well-known $\ell_1$-minimization. Restricted isometry property (RIP) and restricted isometry constant (RIC) of measurement matrices which ensure the convergency of iterative algorithms play key roles for the guarantee of successful reconstructions. In this paper, we show that for the $s$-sparse recovery, the RICs are enlarged to $δ_{3s}<0.4859$ for SP and $δ_{4s}<0.5$ for CoSaMP, which improve the known results significantly. The proposed results also apply to almost sparse signal and corrupted measurements.
Partition-Merge: Distributed Inference and Modularity Optimization
Venue: arXiv cs.DS 2013
Year: 2013

This paper presents a novel meta algorithm, Partition-Merge (PM), which takes existing centralized algorithms for graph computation and makes them distributed and faster. In a nutshell, PM divides the graph into small subgraphs using our novel randomized partitioning scheme, runs the centralized algorithm on each partition separately, and then stitches the resulting solutions to produce a global solution. We demonstrate the efficiency of the PM algorithm on two popular problems: computation of Maximum A Posteriori (MAP) assignment in an arbitrary pairwise Markov Random Field (MRF), and modularity optimization for community detection. We show that the resulting distributed algorithms for these problems essentially run in time linear in the number of nodes in the graph, and perform as well -- or even better -- than the original centralized algorithm as long as the graph has geometric structures. Here we say a graph has geometric structures, or polynomial growth property, when the number of nodes within distance r of any given node grows no faster than a polynomial function of r. More precisely, if the centralized algorithm is a C-factor approximation with constant C \ge 1, the resulting distributed algorithm is a (C+δ)-factor approximation for any small δ>0; but if the centralized algorithm is a non-constant (e.g. logarithmic) factor approximation, then the resulting distributed algorithm becomes a constant factor approximation. For general graphs, we compute explicit bounds on the loss of performance of the resulting distributed algorithm with respect to the centralized algorithm.
Numerical Solutions of Fredholm Integral Equations Using Bernstein Polynomials
Venue: arXiv cs.NA 2013
Year: 2013

In this paper, Bernstein piecewise polynomials are used to solve the integral equations numerically. A matrix formulation is given for a non-singular linear Fredholm Integral Equation by the technique of Galerkin method. In the Galerkin method, the Bernstein polynomials are used as the approximation of basis functions. Examples are considered to verify the effectiveness of the proposed derivations, and the numerical solutions guarantee the desired accuracy.
Tracking Sentiment in Mail: How Genders Differ on Emotional Axes
Venue: arXiv cs.CL 2013
Year: 2013

With the widespread use of email, we now have access to unprecedented amounts of text that we ourselves have written. In this paper, we show how sentiment analysis can be used in tandem with effective visualizations to quantify and track emotions in many types of mail. We create a large word--emotion association lexicon by crowdsourcing, and use it to compare emotions in love letters, hate mail, and suicide notes. We show that there are marked differences across genders in how they use emotion words in work-place email. For example, women use many words from the joy--sadness axis, whereas men prefer terms from the fear--trust axis. Finally, we show visualizations that can help people track emotions in their emails.
Diffeomorphic Metric Mapping and Probabilistic Atlas Generation of Hybrid Diffusion Imaging based on BFOR Signal Basis
Venue: arXiv cs.CV 2013
Year: 2013

We propose a large deformation diffeomorphic metric mapping algorithm to align multiple b-value diffusion weighted imaging (mDWI) data, specifically acquired via hybrid diffusion imaging (HYDI), denoted as LDDMM-HYDI. We then propose a Bayesian model for estimating the white matter atlas from HYDIs. We adopt the work given in Hosseinbor et al. (2012) and represent the q-space diffusion signal with the Bessel Fourier orientation reconstruction (BFOR) signal basis. The BFOR framework provides the representation of mDWI in the q-space and thus reduces memory requirement. In addition, since the BFOR signal basis is orthonormal, the L2 norm that quantifies the differences in the q-space signals of any two mDWI datasets can be easily computed as the sum of the squared differences in the BFOR expansion coefficients. In this work, we show that the reorientation of the $q$-space signal due to spatial transformation can be easily defined on the BFOR signal basis. We incorporate the BFOR signal basis into the LDDMM framework and derive the gradient descent algorithm for LDDMM-HYDI with explicit orientation optimization. Additionally, we extend the previous Bayesian atlas estimation framework for scalar-valued images to HYDIs and derive the expectation-maximization algorithm for solving the HYDI atlas estimation problem. Using real HYDI datasets, we show the Bayesian model generates the white matter atlas with anatomical details. Moreover, we show that it is important to consider the variation of mDWI reorientation due to a small change in diffeomorphic transformation in the LDDMM-HYDI optimization and to incorporate the full information of HYDI for aligning mDWI.
A Fuzzy expert system for goalkeeper quality recognition
Venue: arXiv cs.AI 2013
Year: 2013

Goalkeeper (GK) is an expert in soccer and goalkeeping is a complete professional job. In fact, achieving success seems impossible without a reliable GK. His effect in successes and failures is more dominant than other players. The most visible mistakes in a game are those of goalkeeper's. In this paper the expert fuzzy system is used as a suitable tool to study the quality of a goalkeeper and compare it with others. Previously done researches are used to find the goalkeepers' indexes in soccer. Soccer experts have found that a successful GK should have some qualifications. A new pattern is offered here which is called "Soccer goalkeeper quality recognition using fuzzy expert systems". This pattern has some important capabilities. Firstly, among some goalkeepers the one with the best quality for the main team arrange can be chosen. Secondly, the need to expert coaches for choosing a GK using their senses and experiences decreases a lot. Thirdly, in the survey of a GK, quantitative criteria can be included, and finally this pattern is simple and easy to understand.
Hardware Implementation of the GPS authentication
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we explore new area/throughput trade- offs for the Girault, Poupard and Stern authentication protocol (GPS). This authentication protocol was selected in the NESSIE competition and is even part of the standard ISO/IEC 9798. The originality of our work comes from the fact that we exploit a fixed key to increase the throughput. It leads us to implement GPS using the Chapman constant multiplier. This parallel implementation is 40 times faster but 10 times bigger than the reference serial one. We propose to serialize this multiplier to reduce its area at the cost of lower throughput. Our hybrid Chapman's multiplier is 8 times faster but only twice bigger than the reference. Results presented here allow designers to adapt the performance of GPS authentication to their hardware resources. The complete GPS prover side is also integrated in the network stack of the PowWow sensor which contains an Actel IGLOO AGL250 FPGA as a proof of concept.
On the Stability of Generalized Second Price Auctions with Budgets
Venue: arXiv cs.GT 2013
Year: 2013

The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets
Introduction to the Symbolic Integration System
Venue: arXiv cs.SC 2013
Year: 2013

Symbolic integration is an important module of a typical Computer Algebra System. As for now, Mathematica, Matlab, Maple and Sage are all mainstream CAS. They share the same framework for symbolic integration at some points. In this book first we review the state of the art in the field of CAS. Then we focus on typical frameworks of the current symbolic integration systems and summarize the main mathematical theories behind these frameworks. Based on the open-source computer algebra system maTHmU developed by our team in our university, we propose a potential framework to improve the performance of the current symbolic integration system.