OpenRaiser/Intern-Atlas huggingface dataset:
One-Way Quantum Computer Simulation
Venue: arXiv cs.ET 2015
Year: 2015

In one-way quantum computation (1WQC) model, universal quantum computations are performed using measurements to designated qubits in a highly entangled state. The choices of bases for these measurements as well as the structure of the entanglements specify a quantum algorithm. As scalable and reliable quantum computers have not been implemented yet, quantum computation simulators are the only widely available tools to design and test quantum algorithms. However, simulating the quantum computations on a standard classical computer in most cases requires exponential memory and time. In this paper, a general direct simulator for 1WQC, called OWQS, is presented. Some techniques such as qubit elimination, pattern reordering and implicit simulation of actions are used to considerably reduce the time and memory needed for the simulations. Moreover, our simulator is adjusted to simulate the measurement patterns with a generalized flow without calculating the measurement probabilities which is called extended one-way quantum computation simulator (EOWQS). Experimental results validate the feasibility of the proposed simulators and that OWQS and EOWQS are faster as compared with the well-known quantum circuit simulators, i.e., QuIDDPro and libquantum for simulating 1WQC model.
Challenges to Integration of Information Technology in Physical Infrastructure Development Processes at the Local Government Level
Venue: arXiv cs.CY 2015
Year: 2015

Ghana's Decentralization Policy has made significant contribution in infrastructural implementation and delivery through Metropolitan, Municipal and District Assemblies as an alternative development strategy to ensure the implementation of the overall national agenda. To date, many systems and strategies have been implemented towards improving development of infrastructure at the local government level. Given that initiation and implementation of infrastructural development at the local level involves the multi-institutional participation of various stakeholders in local governance for effective monitoring and development, several governance forms including e-governance have been initiated towards improvement and effective management of the assemblies. E-Governance through the use of relevant Information and Communication Technology has been implemented through the Government Policy on Information and Communications Technology for Accelerated Development as a catalyst to facilitate the cross-sectoral participation in the implementation of infrastructural development. Unfortunately, to date, the ICT4AD does not appear to be successfully on course having been in existence for over a decade. Similarly, the development and monitoring of the physical infrastructure at the local level continue to suffer several setbacks and it is currently clearly evident that a refined system of best practices must be put in place to simplify and harmonize the entire development process. This paper is aimed at the assessment of the challenges of e-governance in infrastructural development at the local government level in Ghana. Using a mixed approach with purposive sampling, data gathered from the MMDAs in Ashanti Region suggest that the entire programme has been very slow; bedeviled with lack of funding and
Review of Inferring Latent Attributes from Twitter
Venue: arXiv cs.SI 2015
Year: 2015

This paper reviews literature from 2011 to 2013 on how Latent attributes like gender, political leaning etc. can be inferred from a person's twitter and neighborhood data. Prediction of demographic data can bring value to businesses, can prove instrumental in legal investigation. Moreover, political leanings can be inferred from the wide variety of user data available on-line. The motive of this review is to understand how large data sets can be made from available twitter data. The tweeting and re tweeting behavior of a user can be user to infer attributes like, gender, age etc. We explore in this text how this field can be expanded in future and possible avenues for future research.
An Approach to Speed-up the Word Sense Disambiguation Procedure through Sense Filtering
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we are going to focus on speed up of the Word Sense Disambiguation procedure by filtering the relevant senses of an ambiguous word through Part-of-Speech Tagging. First, this proposed approach performs the Part-of-Speech Tagging operation before the disambiguation procedure using Bigram approximation. As a result, the exact Part-of-Speech of the ambiguous word at a particular text instance is derived. In the next stage, only those dictionary definitions (glosses) are retrieved from an online dictionary, which are associated with that particular Part-of-Speech to disambiguate the exact sense of the ambiguous word. In the training phase, we have used Brown Corpus for Part-of-Speech Tagging and WordNet as an online dictionary. The proposed approach reduces the execution time upto half (approximately) of the normal execution time for a text, containing around 200 sentences. Not only that, we have found several instances, where the correct sense of an ambiguous word is found for using the Part-of-Speech Tagging before the Disambiguation procedure.
CBAS: context based arabic stemmer
Venue: arXiv cs.CL 2015
Year: 2015

Arabic morphology encapsulates many valuable features such as word root. Arabic roots are being utilized for many tasks; the process of extracting a word root is referred to as stemming. Stemming is an essential part of most Natural Language Processing tasks, especially for derivative languages such as Arabic. However, stemming is faced with the problem of ambiguity, where two or more roots could be extracted from the same word. On the other hand, distributional semantics is a powerful co-occurrence model. It captures the meaning of a word based on its context. In this paper, a distributional semantics model utilizing Smoothed Pointwise Mutual Information (SPMI) is constructed to investigate its effectiveness on the stemming analysis task. It showed an accuracy of 81.5%, with a at least 9.4% improvement over other stemmers.
Schwerdtfeger-Fillmore-Springer-Cnops Construction Implemented in GiNaC
Venue: arXiv cs.MS 2015
Year: 2015

This paper presents an implementation of the Schwerdtfeger-Fillmore-Springer-Cnops construction (SFSCc) along with illustrations of its usage. SFSCc linearises the linear-fraction action of the Moebius group in R^n. This has clear advantages in several theoretical and applied fields including engineering. Our implementation is based on the Clifford algebra capacities of the GiNaC computer algebra system (http://www.ginac.de/), which were described in cs.MS/0410044. The core of this realisation of SFSCc is done for an arbitrary dimension of R^n with a metric given by an arbitrary bilinear form. We also present a subclass for two dimensional cycles (i.e. circles, parabolas and hyperbolas), which add some 2D specific routines including a visualisation to PostScript files through the MetaPost (http://www.tug.org/metapost.html) or Asymptote (http://asymptote.sourceforge.net/) packages. This software is the backbone of many results published in math.CV/0512416 and we use its applications their for demonstration. The library can be ported (with various level of required changes) to other CAS with Clifford algebras capabilities similar to GiNaC. There is an ISO image of a Live Debian DVD attached to this paper as an auxiliary file, a copy is stored on Google Drive as well.
Compactly accessible categories and quantum key distribution
Venue: arXiv cs.LO 2016
Year: 2016

Compact categories have lately seen renewed interest via applications to quantum physics. Being essentially finite-dimensional, they cannot accomodate (co)limit-based constructions. For example, they cannot capture protocols such as quantum key distribution, that rely on the law of large numbers. To overcome this limitation, we introduce the notion of a compactly accessible category, relying on the extra structure of a factorisation system. This notion allows for infinite dimension while retaining key properties of compact categories: the main technical result is that the choice-of-duals functor on the compact part extends canonically to the whole compactly accessible category. As an example, we model a quantum key distribution protocol and prove its correctness categorically.
Bounds on monotone switching networks for directed connectivity
Venue: arXiv cs.CC 2016
Year: 2016

We separate monotone analogues of L and NL by proving that any monotone switching network solving directed connectivity on $n$ vertices must have size at least $n^(Ω(\lg(n)))$.
Completeness of Flat Coalgebraic Fixpoint Logics
Venue: arXiv cs.LO 2016
Year: 2016

Modal fixpoint logics traditionally play a central role in computer science, in particular in artificial intelligence and concurrency. The mu-calculus and its relatives are among the most expressive logics of this type. However, popular fixpoint logics tend to trade expressivity for simplicity and readability, and in fact often live within the single variable fragment of the mu-calculus. The family of such flat fixpoint logics includes, e.g., LTL, CTL, and the logic of common knowledge. Extending this notion to the generic semantic framework of coalgebraic logic enables covering a wide range of logics beyond the standard mu-calculus including, e.g., flat fragments of the graded mu-calculus and the alternating-time mu-calculus (such as alternating-time temporal logic ATL), as well as probabilistic and monotone fixpoint logics. We give a generic proof of completeness of the Kozen-Park axiomatization for such flat coalgebraic fixpoint logics.
Forward Analysis and Model Checking for Trace Bounded WSTS
Venue: arXiv cs.LO 2016
Year: 2016

We investigate a subclass of well-structured transition systems (WSTS), the bounded---in the sense of Ginsburg and Spanier (Trans. AMS 1964)---complete deterministic ones, which we claim provide an adequate basis for the study of forward analyses as developed by Finkel and Goubault-Larrecq (Logic. Meth. Comput. Sci. 2012). Indeed, we prove that, unlike other conditions considered previously for the termination of forward analysis, boundedness is decidable. Boundedness turns out to be a valuable restriction for WSTS verification, as we show that it further allows to decide all $ω$-regular properties on the set of infinite traces of the system.
Distance Constraint Satisfaction Problems
Venue: arXiv cs.CC 2016
Year: 2016

We study the complexity of constraint satisfaction problems for templates $Γ$ that are first-order definable in $(\Bbb Z; succ)$, the integers with the successor relation. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), we provide a full classification for the case that Gamma is locally finite (i.e., the Gaifman graph of $Γ$ has finite degree). We show that one of the following is true: The structure Gamma is homomorphically equivalent to a structure with a d-modular maximum or minimum polymorphism and $\mathrm{CSP}(Γ)$ can be solved in polynomial time, or $Γ$ is homomorphically equivalent to a finite transitive structure, or $\mathrm{CSP}(Γ)$ is NP-complete.
Local Computation: Lower and Upper Bounds
Venue: arXiv cs.DC 2016
Year: 2016

The question of what can be computed, and how efficiently, are at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a \emph{distributed} fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first poly-logarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.
Approximate Tree Decompositions of Planar Graphs in Linear Time
Venue: arXiv cs.DS 2016
Year: 2016

Many algorithms have been developed for NP-hard problems on graphs with small treewidth $k$. For example, all problems that are expressable in linear extended monadic second order can be solved in linear time on graphs of bounded treewidth. It turns out that the bottleneck of many algorithms for NP-hard problems is the computation of a tree decomposition of width $O(k)$. In particular, by the bidimensional theory, there are many linear extended monadic second order problems that can be solved on $n$-vertex planar graphs with treewidth $k$ in a time linear in $n$ and subexponential in $k$ if a tree decomposition of width $O(k)$ can be found in such a time. We present the first algorithm that, on $n$-vertex planar graphs with treewidth $k$, finds a tree decomposition of width $O(k)$ in such a time. In more detail, our algorithm has a running time of $O(n k^2 \log k)$. We show the result as a special case of a result concerning so-called weighted treewidth of weighted graphs.
Resource allocation with costly participation
Venue: arXiv cs.GT 2016
Year: 2016

We propose a new all-pay auction format in which risk-loving bidders pay a constant fee each time they bid for an object whose monetary value is common knowledge among the bidders, and bidding fees are the only source of benefit for the seller. We show that for the proposed model there exists a {unique} Symmetric Subgame Perfect Equilibrium (SSPE). The characterized SSPE is stationary when re-entry in the auction is allowed, and it is Markov perfect when re-entry is forbidden. Furthermore, we fully characterize the expected revenue of the seller. Generally, with or without re-entry, it is more beneficial for the seller to choose $v$ (value of the object), $s$ (sale price), and $c$ (bidding fee) such that $\frac{v-s}{c}$ becomes sufficiently large. In particular, when re-entry is permitted: the expected revenue of the seller is \emph{independent} of the number of bidders, decreasing in the sale price, increasing in the value of the object, and decreasing in the bidding fee; Moreover, the seller's revenue is equal to the value of the object when players are risk neutral, and it is strictly greater than the value of the object when bidders are risk-loving. We further show that allowing re-entry can be important in practice. Because, if the seller were to run such an auction without allowing re-entry, the auction would last a long time, and for almost all of its duration have only two remaining players. Thus, the seller's revenue relies on those two players being willing to participate, without any breaks, in an auction that might last for thousands of rounds
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
Venue: arXiv cs.DS 2016
Year: 2016

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective $\sum_{ij\in E} C_{ij}(f_{ij})$ over feasible flows $f$, where on every arc $ij$ of the network, $C_{ij}$ is a convex function. We give a strongly polynomial algorithm for the case when all $C_{ij}$'s are convex quadratic functions, settling an open problem raised e.g. by Hochbaum [1994]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities, that can be formulated in this framework (see Shmyrev [2009], Devanur et al. [2011]). For the latter class this resolves an open question raised by Vazirani [2010]. The running time is $O(m^4\log m)$ for quadratic costs, $O(n^4+n^2(m+n\log n)\log n)$ for Fisher's markets with linear utilities and $O(mn^3 +m^2(m+n\log n)\log m)$ for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [1994]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.
On Bitcoin and Red Balloons
Venue: arXiv cs.GT 2016
Year: 2016

Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system. Bitcoin represents a radical new approach to monetary systems. It has been getting a large amount of public attention over the last year, both in policy discussions and in the popular press. Its cryptographic fundamentals have largely held up even as its usage has become increasingly widespread. We find, however, that it exhibits a fundamental problem of a different nature, based on how its incentives are structured. We propose a modification to the protocol that can eliminate this problem. Bitcoin relies on a peer-to-peer network to track transactions that are performed with the currency. For this purpose, every transaction a node learns about should be transmitted to its neighbors in the network. The current implemented protocol provides an incentive to nodes to not broadcast transactions they are aware of. Our solution is to augment the protocol with a scheme that rewards information propagation. Since clones are easy to create in the Bitcoin system, an important feature of our scheme is Sybil-proofness. We show that our proposed scheme succeeds in setting the correct incentives, that it is Sybil-proof, and that it requires only a small payment overhead, all this is achieved with iterated elimination of dominated strategies. We complement this result by showing that there are no reward schemes in which information propagation and no self-cloning is a dominant strategy.
Statistical Algorithms and a Lower Bound for Detecting Planted Clique
Venue: arXiv cs.CC 2016
Year: 2016

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory (Kearns, 1998). Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size $O(n^{1/2-δ})$ for any constant $δ> 0$. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.
Model-Checking of Linear-Time Properties Based on Possibility Measure
Venue: arXiv cs.LO 2016
Year: 2016

We study the LTL model-checking in possibilistic Kripke structure using possibility measure. First, the notion of possibilistic Kripke structure and the related possibility measure are introduced, then model-checking of reachability and repeated reachability linear-time properties in finite possibilistic Kripke structure are studied. Standard safety property and -regular property in possibilistic Kripke structure are introduced, the verification of regular safety property and -regular property using finite automata are thoroughly studied. It has been shown that the verification of regular safety property and -regular property in finite possibilistic Kripke structure can be transformed into the verification of reachability property and repeated reachability property in the product possibilistic Kripke structure introduced in this paper. Several examples are given to illustrate the methods presented in the paper.
List Decoding Algorithm based on Voting in Groebner Bases for General One-Point AG Codes
Venue: arXiv cs.IT 2016
Year: 2016

We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amorós and O'Sullivan (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010). It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010; Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs.
Fast Cross-Validation via Sequential Testing
Venue: arXiv cs.LG 2016
Year: 2016

With the increasing size of today's data sets, finding the right parameter configuration in model selection via cross-validation can be an extremely time-consuming task. In this paper we propose an improved cross-validation procedure which uses nonparametric testing coupled with sequential analysis to determine the best parameter set on linearly increasing subsets of the data. By eliminating underperforming candidates quickly and keeping promising candidates as long as possible, the method speeds up the computation while preserving the capability of the full cross-validation. Theoretical considerations underline the statistical power of our procedure. The experimental evaluation shows that our method reduces the computation time by a factor of up to 120 compared to a full cross-validation with a negligible impact on the accuracy.