OpenRaiser/Intern-Atlas huggingface dataset:
Short review of lattice basis reduction types and his applications (Russian)
Venue: arXiv cs.DM 2012
Year: 2012

This article presets a review of lattice lattice basis reduction types. Paper contains the main five types of lattice basis reduction: size reduced (weak Hermit), c-reduced, Lovasz condition, Hermit-Korkin-Zolotarev, Minkowski reduced. The article provides references to applications in: information theory (decoding of coding group in MIMO), calculus (minimize of the positive quadratic form), complexity theory and cryptanalysis of Merkle-Hellman cryptography (solving subset sum problems), algebra and control theory(solving system of linear diophantine equation), compiler theory (lattice based memory allocation), synthesize cryptographic and cryptanalysis in lattice based cryptography.
Block Korkin-Zolotarev algorithm generalization and their practical implementation (Russian)
Venue: arXiv cs.DM 2012
Year: 2012

We propose a practical algorithm for block Korkin-Zolotarev reduction, a concept introduced by Schnorr, using CPU arbitrary length Householder QR-decomposition for orthogonalization and double precision OpenCL GPU Finke-Post shortest vector enumeration. Empirical tests was used on random lattices in the sense of Goldstein and Mayer.
A measure of similarity between scientific journals and of diversity of a list of publications
Venue: arXiv cs.DL 2012
Year: 2012

The aim of this note is to propose a definition of the scientific diversity and corollarly, a measure of the "interdisciplinarity" of collaborations. With respect to previous studies, the proposed approach consists of 2 steps : first, the definition of similarity between journals and second, these similarities are used to characterize the homogeneity (or, on the contrary the diversity) of a publication list (that can be for one individual or a team).
Informaticology: combining Computer Science, Data Science, and Fiction Science
Venue: arXiv cs.SE 2012
Year: 2012

Motivated by an intention to remedy current complications with Dutch terminology concerning informatics, the term informaticology is positioned to denote an academic counterpart of informatics where informatics is conceived of as a container for a coherent family of practical disciplines ranging from computer engineering and software engineering to network technology, data center management, information technology, and information management in a broad sense. Informaticology escapes from the limitations of instrumental objectives and the perspective of usage that both restrict the scope of informatics. That is achieved by including fiction science in informaticology and by ranking fiction science on equal terms with computer science and data science, and framing (the study of) game design, evelopment, assessment and distribution, ranging from serious gaming to entertainment gaming, as a chapter of fiction science. A suggestion for the scope of fiction science is specified in some detail. In order to illustrate the coherence of informaticology thus conceived, a potential application of fiction to the ontology of instruction sequences and to software quality assessment is sketched, thereby highlighting a possible role of fiction (science) within informaticology but outside gaming.
Multiple-antenna fading coherent channels with arbitrary inputs: Characterization and optimization of the reliable information transmission rate
Venue: arXiv cs.IT 2012
Year: 2012

We investigate the constrained capacity of multiple-antenna fading coherent channels, where the receiver knows the channel state but the transmitter knows only the channel distribution, driven by arbitrary equiprobable discrete inputs in a regime of high signal-to-noise ratio (${\sf snr}$). In particular, we capitalize on intersections between information theory and estimation theory to conceive expansions to the average minimum-mean squared error (MMSE) and the average mutual information, which leads to an expansion of the constrained capacity, that capture well their behavior in the asymptotic regime of high ${\sf snr}$. We use the expansions to study the constrained capacity of various multiple-antenna fading coherent channels, including Rayleigh fading models, Ricean fading models and antenna-correlated models. The analysis unveils in detail the impact of the number of transmit and receive antennas, transmit and receive antenna correlation, line-of-sight components and the geometry of the signalling scheme on the reliable information transmission rate. We also use the expansions to design key system elements, such as power allocation and precoding schemes, as well as to design space-time signalling schemes for multiple-antenna fading coherent channels. Simulations results demonstrate that the expansions lead to very sharp designs.
Jointly they edit: examining the impact of community identification on political interaction in Wikipedia
Venue: arXiv cs.SI 2012
Year: 2012

In their 2005 study, Adamic and Glance coined the memorable phrase "divided they blog", referring to a trend of cyberbalkanization in the political blogosphere, with liberal and conservative blogs tending to link to other blogs with a similar political slant, and not to one another. As political discussion and activity increasingly moves online, the power of framing political discourses is shifting from mass media to social media. Continued examination of political interactions online is critical, and we extend this line of research by examining the activities of political users within the Wikipedia community. First, we examined how users in Wikipedia choose to display (or not to display) their political affiliation. Next, we more closely examined the patterns of cross-party interaction and community participation among those users proclaiming a political affiliation. In contrast to previous analyses of other social media, we did not find strong trends indicating a preference to interact with members of the same political party within the Wikipedia community. Our results indicate that users who proclaim their political affiliation within the community tend to proclaim their identity as a "Wikipedian" even more loudly. It seems that the shared identity of "being Wikipedian" may be strong enough to triumph over other potentially divisive facets of personal identity, such as political affiliation.
Predicting Near-Future Churners and Win-Backs in the Telecommunications Industry
Venue: arXiv cs.CE 2012
Year: 2012

In this work, we presented the strategies and techniques that we have developed for predicting the near-future churners and win-backs for a telecom company. On a large-scale and real-world database containing customer profiles and some transaction data from a telecom company, we first analyzed the data schema, developed feature computation strategies and then extracted a large set of relevant features that can be associated with the customer churning and returning behaviors. Our features include both the original driver factors as well as some derived features. We evaluated our features on the imbalance corrected dataset, i.e. under-sampled dataset and compare a large number of existing machine learning tools, especially decision tree-based classifiers, for predicting the churners and win-backs. In general, we find RandomForest and SimpleCart learning algorithms generally perform well and tend to provide us with highly competitive prediction performance. Among the top-15 driver factors that signal the churn behavior, we find that the service utilization, e.g. last two months' download and upload volume, last three months' average upload and download, and the payment related factors are the most indicative features for predicting if churn will happen soon. Such features can collectively tell discrepancies between the service plans, payments and the dynamically changing utilization needs of the customers. Our proposed features and their computational strategy exhibit reasonable precision performance to predict churn behavior in near future.
On the complexity of the model checking problem
Venue: arXiv cs.LO 2012
Year: 2012

The model checking problem for various fragments of first-order logic has attracted much attention over the last two decades: in particular, for the primitive positive and the positive Horn fragments, which are better known as the constraint satisfaction problem and the quantified constraint satisfaction problem, respectively. These two fragments are in fact the only ones for which there is currently no known complexity classification. All other syntactic fragments can be easily classified, either directly or using Schaefer's dichotomy theorems for SAT and QSAT, with the exception of the positive equality free fragment. This outstanding fragment can also be classified and enjoys a tetrachotomy: according to the model, the corresponding model checking problem is either tractable, NP-complete, co-NP-complete or Pspace-complete. Moreover, the complexity drop is always witnessed by a generic solving algorithm which uses quantifier relativisation. Furthermore, its complexity is characterised by algebraic means: the presence or absence of specific surjective hyper-operations among those that preserve the model characterise the complexity.
Sampling-based proofs of almost-periodicity results and algorithmic applications
Venue: arXiv cs.DM 2012
Year: 2012

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask, whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and L^p-norm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almost-periodic sumsets of dense subsets of F_2^n. As an application, we give a new algorithmic version of the quasipolynomial Bogolyubov-Ruzsa lemma recently proved by Sanders. Together with the results by the last two authors, this implies an algorithmic version of the quadratic Goldreich-Levin theorem in which the number of terms in the quadratic Fourier decomposition of a given function is quasipolynomial in the error parameter, compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence instead of an exponential one. We also give an application to the problem of finding large subspaces in sumsets of dense sets. Green showed that the sumset of a dense subset of F_2^n contains a large subspace. Using Fourier analytic methods, Sanders proved that such a subspace must have dimension bounded below by a constant times the density times n. We provide an alternative (and L^p norm-free) proof of a comparable bound, which is analogous to a recent result of Croot, Laba and Sisask in the integers.
Influence of Context on Decision Making during Requirements Elicitation
Venue: arXiv cs.SE 2012
Year: 2012

Requirements engineers should strive to get a better insight into decision making processes. During elicitation of requirements, decision making influences how stakeholders communicate with engineers, thereby affecting the engineers' understanding of requirements for the future information system. Empirical studies issued from Artificial Intelligence offer an adequate groundwork to understand how decision making is influenced by some particular contextual factors. However, no research has gone into the validation of such empirical studies in the process of collecting needs of the future system's users. As an answer, the paper empirically studies factors, initially identified by AI literature, that influence decision making and communication during requirements elicitation. We argue that the context's structure of the decision should be considered as a cornerstone to adequately study how stakeholders decide to communicate or not a requirement. The paper proposes a context framework to categorize former factors into specific families, and support the engineers during the elicitation process.
Legacy Software Restructuring: Analyzing a Concrete Case
Venue: arXiv cs.SE 2012
Year: 2012

Software re-modularization is an old preoccupation of reverse engineering research. The advantages of a well structured or modularized system are well known. Yet after so much time and efforts, the field seems unable to come up with solutions that make a clear difference in practice. Recently, some researchers started to question whether some basic assumptions of the field were not overrated. The main one consists in evaluating the high-cohesion/low-coupling dogma with metrics of unknown relevance. In this paper, we study a real structuring case (on the Eclipse platform) to try to better understand if (some) existing metrics would have helped the software engineers in the task. Results show that the cohesion and coupling metrics used in the experiment did not behave as expected and would probably not have helped the maintainers reach there goal. We also measured another possible restructuring which is to decrease the number of cyclic dependencies between modules. Again, the results did not meet expectations.
Distributed Control of Angle-constrained Circular Formations using Bearing-only Measurements
Venue: arXiv cs.SY 2012
Year: 2012

This paper studies distributed formation control of multiple agents in the plane using bearing-only measurements. It is assumed that each agent only measures the local bearings of their neighbor agents. The target formation considered in this paper is a circular formation, where each agent has exactly two neighbors. In the target formation, the angle subtended at each agent by their two neighbors is specified. We propose a distributed control law that stabilizes angle-constrained target formations merely using local bearing measurements. The stability of the target formation is analyzed based on Lyapunov approaches. We present a unified proof to show that our control law not only can ensure local exponential stability but also can give local finite-time stability. The exponential or finite-time stability can be easily switched by tuning a parameter in the control law.
Rewriting Codes for Flash Memories
Venue: arXiv cs.IT 2012
Year: 2012

Flash memory is a non-volatile computer memory comprising blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes (or flash codes) and buffer codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n,k,t)q flash code C is a coding scheme for storing k information bits in $n$ cells in such a way that any sequence of up to t writes can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of C, defined as δ(C) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency O(qk\log k) if q \geq \log_2k, and at most O(k\log^2 k) otherwise. An (n,r,\ell,t)q buffer code is a coding scheme for storing a buffer of r \ell-ary symbols such that for any sequence of t symbols it is possible to successfully decode the last r symbols that were written. We improve upon a previous upper bound on the maximum number of writes t in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiang et al. that uses multiple cells, where n\geq 2r.
Plagiarism Detection: Keeping Check on Misuse of Intellectual Property
Venue: arXiv cs.OH 2012
Year: 2012

Today, Plagiarism has become a menace. Every journal editor or conference organizers has to deal with this problem. Simply Copying or rephrasing of text without giving due credit to the original author has become more common. This is considered to be an Intellectual Property Theft. We are developing a Plagiarism Detection Tool which would deal with this problem. In this paper we discuss the common tools available to detect plagiarism and their short comings and the advantages of our tool over these tools.
Implementation of a Vision System for a Landmine Detecting Robot Using Artificial Neural Network
Venue: arXiv cs.NE 2012
Year: 2012

Landmines, specifically anti-tank mines, cluster bombs, and unexploded ordnance form a serious problem in many countries. Several landmine sweeping techniques are used for minesweeping. This paper presents the design and the implementation of the vision system of an autonomous robot for landmines localization. The proposed work develops state-of-the-art techniques in digital image processing for pre-processing captured images of the contaminated area. After enhancement, Artificial Neural Network (ANN) is used in order to identify, recognize and classify the landmines' make and model. The Back-Propagation algorithm is used for training the network. The proposed work proved to be able to identify and classify different types of landmines under various conditions (rotated landmine, partially covered landmine) with a success rate of up to 90%.
Greedy Selfish Network Creation
Venue: arXiv cs.GT 2012
Year: 2012

We introduce and analyze greedy equilibria (GE) for the well-known model of selfish network creation by Fabrikant et al.[PODC'03]. GE are interesting for two reasons: (1) they model outcomes found by agents which prefer smooth adaptations over radical strategy-changes, (2) GE are outcomes found by agents which do not have enough computational resources to play optimally. In the model of Fabrikant et al. agents correspond to Internet Service Providers which buy network links to improve their quality of network usage. It is known that computing a best response in this model is NP-hard. Hence, poly-time agents are likely not to play optimally. But how good are networks created by such agents? We answer this question for very simple agents. Quite surprisingly, naive greedy play suffices to create remarkably stable networks. Specifically, we show that in the SUM version, where agents attempt to minimize their average distance to all other agents, GE capture Nash equilibria (NE) on trees and that any GE is in 3-approximate NE on general networks. For the latter we also provide a lower bound of 3/2 on the approximation ratio. For the MAX version, where agents attempt to minimize their maximum distance, we show that any GE-star is in 2-approximate NE and any GE-tree having larger diameter is in 6/5-approximate NE. Both bounds are tight. We contrast these positive results by providing a linear lower bound on the approximation ratio for the MAX version on general networks in GE. This result implies a locality gap of $Ω(n)$ for the metric min-max facility location problem, where n is the number of clients.
Reusability Framework for Cloud Computing
Venue: arXiv cs.SE 2012
Year: 2012

Cloud based development is a challenging task for several software engineering projects, especially for those which needs development with reusability. Present time of cloud computing is allowing new professional models for using the software development. The expected upcoming trend of computing is assumed to be this cloud computing because of speed of application deployment, shorter time to market, and lower cost of operation. Until Cloud Co mputing Reusability Model is considered a fundamental capability, the speed of developing services is very slow. Th is paper spreads cloud computing with component based development named Cloud Co mputing Reusability Model (CCR) and enable reusability in cloud computing. In this paper Cloud Co mputing Reusability Model has been proposed. The model has been validated by Cloudsim an d experimental result shows that reusability based cloud computing approach is effective in minimizing cost and time to market.
A Note on the Dimensions of the Structural Invariant Subspaces of the Discrete-Time Singular Hamiltonian Systems
Venue: arXiv cs.SY 2012
Year: 2012

The structural invariant subspaces of the discrete-time singular Hamiltonian system are used in 1] to give an analytic nonrecursive expression of all the admissible trajectories. A deeper insight into the features of these subspaces, particularly focused on the dimensionality issue, is the object of this note.
Hierarchical Learning Algorithm for the Beta Basis Function Neural Network
Venue: arXiv cs.NE 2012
Year: 2012

The paper presents a two-level learning method for the design of the Beta Basis Function Neural Network BBFNN. A Genetic Algorithm is employed at the upper level to construct BBFNN, while the key learning parameters :the width, the centers and the Beta form are optimised using the gradient algorithm at the lower level. In order to demonstrate the effectiveness of this hierarchical learning algorithm HLABBFNN, we need to validate our algorithm for the approximation of non-linear function.
Non-uniform Quantization of Detail Components in Wavelet Transformed Image for Lossy JPEG2000 Compression
Venue: arXiv cs.MM 2012
Year: 2012

The paper introduces the idea of non-uniform quantization in the detail components of wavelet transformed image. It argues that most of the coefficients of horizontal, vertical and diagonal components lie near to zeros and the coefficients representing large differences are few at the extreme ends of histogram. Therefore, this paper advocates need for variable step size quantization scheme which preserves the edge information at the edge of histogram and removes redundancy with the minimal number of quantized values. To support the idea, preliminary results are provided using a non-uniform quantization algorithm. We believe that successful implementation of non-uniform quantization in detail components in JPEG-2000 still image standard will improve image quality and compression efficiency with lesser number of quantized values.
Testing the Finch Hypothesis on Green OA Mandate Ineffectiveness
Venue: arXiv cs.DL 2012
Year: 2012

We have now tested the Finch Committee's Hypothesis that Green Open Access Mandates are ineffective in generating deposits in institutional repositories. With data from ROARMAP on institutional Green OA mandates and data from ROAR on institutional repositories, we show that deposit number and rate is significantly correlated with mandate strength (classified as 1-12): The stronger the mandate, the more the deposits. The strongest mandates generate deposit rates of 70%+ within 2 years of adoption, compared to the un-mandated deposit rate of 20%. The effect is already detectable at the national level, where the UK, which has the largest proportion of Green OA mandates, has a national OA rate of 35%, compared to the global baseline of 25%. The conclusion is that, contrary to the Finch Hypothesis, Green Open Access Mandates do have a major effect, and the stronger the mandate, the stronger the effect (the Liege ID/OA mandate, linked to research performance evaluation, being the strongest mandate model). RCUK (as well as all universities, research institutions and research funders worldwide) would be well advised to adopt the strongest Green OA mandates and to integrate institutional and funder mandates.
Non-associative public-key cryptography
Venue: arXiv cs.CR 2012
Year: 2012

We introduce a generalized Anshel-Anshel-Goldfeld (AAG) key establishment protocol (KEP) for magmas. This leads to the foundation of non-associative public-key cryptography (PKC), generalizing the concept of non-commutative PKC. We show that left selfdistributive systems appear in a natural special case of a generalized AAG-KEP for magmas, and we propose, among others instances, concrete realizations using $f$-conjugacy in groups and shifted conjugacy in braid groups. We discuss the advantages of our schemes compared with the classical AAG-KEP based on conjugacy in braid groups.