OpenRaiser/Intern-Atlas huggingface dataset:
Growing the Digital Repository of Mathematical Formulae with Generic LaTeX Sources
Venue: arXiv cs.DL 2015
Year: 2015

One initial goal for the DRMF is to seed our digital compendium with fundamental orthogonal polynomial formulae. We had used the data from the NIST Digital Library of Mathematical Functions (DLMF) as initial seed for our DRMF project. The DLMF input LaTeX source already contains some semantic information encoded using a highly customized set of semantic LaTeX macros. Those macros could be converted to content MathML using LaTeXML. During that conversion the semantics were translated to an implicit DLMF content dictionary. This year, we have developed a semantic enrichment process whose goal is to infer semantic information from generic LaTeX sources. The generated context-free semantic information is used to build DRMF formula home pages for each individual formula. We demonstrate this process using selected chapters from the book "Hypergeometric Orthogonal Polynomials and their $q$-Analogues" (2010) by Koekoek, Lesky and Swarttouw (KLS) as well as an actively maintained addendum to this book by Koornwinder (KLSadd). The generic input KLS and KLSadd LaTeX sources describe the printed representation of the formulae, but does not contain explicit semantic information. See http://drmf.wmflabs.org.
Tight Bounds for Linear Sketches of Approximate Matchings
Venue: arXiv cs.DS 2015
Year: 2015

We resolve the space complexity of linear sketches for approximating the maximum matching problem in dynamic graph streams where the stream may include both edge insertion and deletion. Specifically, we show that for any $ε> 0$, there exists a one-pass streaming algorithm, which only maintains a linear sketch of size $\tilde{O}(n^{2-3ε})$ bits and recovers an $n^ε$-approximate maximum matching in dynamic graph streams, where $n$ is the number of vertices in the graph. In contrast to the extensively studied insertion-only model, to the best of our knowledge, no non-trivial single-pass streaming algorithms were previously known for approximating the maximum matching problem on general dynamic graph streams. Furthermore, we show that our upper bound is essentially tight. Namely, any linear sketch for approximating the maximum matching to within a factor of $O(n^ε)$ has to be of size $n^{2-3ε-o(1)}$ bits. We establish this lower bound by analyzing the corresponding simultaneous number-in-hand communication model, with a combinatorial construction based on Ruzsa-Szemerédi graphs.
Numerical investigation of a space-fractional model of turbulent fluid flow in rectangular ducts
Venue: arXiv cs.NA 2015
Year: 2015

The models that are based of fractional derivatives should be highlighted among promising new models to describe turbulent fluid flows. In the present work, a steady-state flow in a duct is considered under the condition that the turbulent diffusion is governed by a fractional power of the Laplace operator. To study numerically flows in rectangular channels, finite-difference approximations are employed. For approximate solving the corresponding boundary value problem, the iterative method of conjugate gradients is used. At each iteration, the problem with a fractional power of the grid Laplace operator is solved. Predictions of turbulent flows in ducts at different Reynolds numbers are presented via mean velocity fields.
An improvement on fragmentation in Distribution Database Design Based on Knowledge-Oriented Clustering Techniques
Venue: arXiv cs.DB 2015
Year: 2015

The problem of optimizing distributed database includes: fragmentation and positioning data. Several different approaches and algorithms have been proposed to solve this problem. In this paper, we propose an algorithm that builds the initial equivalence relation based on the distance threshold. This threshold is also based on knowledge- oriented clustering techniques for both of horizontal and vertical fragmentation. Similarity measures used in the algorithms are the measures developed from the classical measures. Experimental results carrying on the small data set match fragmented results based on the classical algorithm. Execution time and data fragmentation significantly reduced while the complexity of our algorithm in the general case is stable.
Documentation Generator Focusing on Symbols for the HTML-ized Mizar Library
Venue: arXiv cs.MS 2015
Year: 2015

The purpose of this project is to collect symbol information in the Mizar Mathematical Library and manipulate it into practical and organized documentation. Inspired by the MathWiki project and API reference systems for computer programs, we developed a documentation generator focusing on symbols for the HTML-ized Mizar library. The system has several helpful features, including a symbol list, incremental search, and a referrer list. It targets those who use proof assistance systems, the volume of whose libraries has been rapidly increasing year by year.
Secure User Authentication & Graphical Password using Cued Click-Points
Venue: arXiv cs.CR 2015
Year: 2015

The major problem of user registration, mostly text base password, is well known. In the login user be inclined to select simple passwords which is frequently in mind that are straightforward for attackers to guess, difficult machine created password mostly complicated to user take in mind. User authenticate password using cued click points and Persuasive Cued Click Points graphical password scheme which includes usability and security evaluations. This paper includes the persuasion to secure user authentication & graphical password using cued click-points so that users select more random or more difficult to guess the passwords. In click-based graphical passwords, image or video frame that provide database to load the image, and then store all information into database. Mainly passwords are composed of strings which have letters as well as digits. Example is alpha-numeric type letters and digits.
An Improvement on the Hasse-Weil Bound and applications to Character Sums, Cryptography and Coding
Venue: arXiv cs.DM 2015
Year: 2015

The Hasse-Weil bound is a deep result in mathematics and has found wide applications in mathematics, theoretical computer science, information theory etc. In general, the bound is tight and cannot be improved. However, for some special families of curves the bound could be improved substantially. In this paper, we focus on the Hasse-Weil bound for the curve defined by $y^p-y=f(x)$ over the finite field $\F_q$, where $p$ is the characteristic of $\F_q$. Recently, Kaufman and Lovett \cite[FOCS2011]{KL11} showed that the Hasse-Weil bound can be improved for this family of curves with $f(x)=g(x)+h(x)$, where $g(x)$ is a polynomial of degree $\ll \sqrt{q}$ and $h(x)$ is a sparse polynomial of arbitrary degree but bounded weight degree. The other recent improvement by Rojas-Leon and Wan \cite[Math. Ann. 2011]{RW11} shows that an extra $\sqrt{p}$ can be removed for this family of curves if $p$ is very large compared with polynomial degree of $f(x)$ and $\log_pq$. In this paper, we show that the Hasse-Weil bound for this special family of curves can be improved if $q=p^n$ with odd $n$ which is the same case where Serre \cite{Se85} improved the Hasse-Weil bound. However, our improvement is greater than Serre's one for this special family of curves. Furthermore, our improvement works for small $p$ as well compared with the requirement of large $p$ by Rojas-Leon and Wan. In addition, our improvement finds interesting applications to character sums, cryptography and coding theory. The key idea behind is that this curve has the Hasse-Witt invariant $0$ and we show that the Hasse-Weil bound can be improved for any curves with the Hasse-Witt invariant $0$. The main tool used in our proof involves Newton polygon and some results in algebraic geometry.
Predicting Community Evolution in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Nowadays, sustained development of different social media can be observed worldwide. One of the relevant research domains intensively explored recently is analysis of social communities existing in social media as well as prediction of their future evolution taking into account collected historical evolution chains. These evolution chains proposed in the paper contain group states in the previous time frames and its historical transitions that were identified using one out of two methods: Stable Group Changes Identification (SGCI) and Group Evolution Discovery (GED). Based on the observed evolution chains of various length, structural network features are extracted, validated and selected as well as used to learn classification models. The experimental studies were performed on three real datasets with different profile: DBLP, Facebook and Polish blogosphere. The process of group prediction was analysed with respect to different classifiers as well as various descriptive feature sets extracted from evolution chains of different length. The results revealed that, in general, the longer evolution chains the better predictive abilities of the classification models. However, chains of length 3 to 7 enabled the GED-based method to almost reach its maximum possible prediction quality. For SGCI, this value was at the level of 3 to 5 last periods.
A Tractable Model of the LTE Access Reservation Procedure for Machine-Type Communications
Venue: arXiv cs.IT 2015
Year: 2015

A canonical scenario in Machine-Type Communications (MTC) is the one featuring a large number of devices, each of them with sporadic traffic. Hence, the number of served devices in a single LTE cell is not determined by the available aggregate rate, but rather by the limitations of the LTE access reservation protocol. Specifically, the limited number of contention preambles and the limited amount of uplink grants per random access response are crucial to consider when dimensioning LTE networks for MTC. We propose a low-complexity model of LTE's access reservation protocol that encompasses these two limitations and allows us to evaluate the outage probability at click-speed. The model is based chiefly on closed-form expressions, except for the part with the feedback impact of retransmissions, which is determined by solving a fixed point equation. Our model overcomes the incompleteness of the existing models that are focusing solely on the preamble collisions. A comparison with the simulated LTE access reservation procedure that follows the 3GPP specifications, confirms that our model provides an accurate estimation of the system outage event and the number of supported MTC devices.
Spacetimes with Semantics (II), Scaling of agency, semantics, and tenancy
Venue: arXiv cs.MA 2015
Year: 2015

Using Promise Theory as a calculus, I review how to define agency in a scalable way, for the purpose of understanding semantic spacetimes. By following simple scaling rules, replacing individual agents with `super-agents' (sub-spaces), it is shown how agency can be scaled both dynamically and semantically. The notion of occupancy and tenancy, or how space is used and filled in different ways, is also defined, showing how spacetime can be shared between independent parties, both by remote association and local encapsulation. I describe how to build up dynamic and semantic continuity, by joining discrete individual atoms and molecules of space into quasi-continuous lattices.
CogCell: Cognitive Interplay between 60GHz Picocells and 2.4/5GHz Hotspots in the 5G Era
Venue: arXiv cs.NI 2015
Year: 2015

Rapid proliferation of wireless communication devices and the emergence of a variety of new applications have triggered investigations into next-generation mobile broadband systems, i.e., 5G. Legacy 2G--4G systems covering large areas were envisioned to serve both indoor and outdoor environments. However, in the 5G-era, 80\% of overall traffic is expected to be generated in indoors. Hence, the current approach of macro-cell mobile network, where there is no differentiation between indoors and outdoors, needs to be reconsidered. We envision 60\,GHz mmWave picocell architecture to support high-speed indoor and hotspot communications. We envisage the 5G indoor network as a combination of-, and interplay between, 2.4/5\,GHz having robust coverage and 60\,GHz links offering high datarate. This requires an intelligent coordination and cooperation. We propose 60\,GHz picocellular network architecture, called CogCell, leveraging the ubiquitous WiFi. We propose to use 60\,GHz for the data plane and 2.4/5GHz for the control plane. The hybrid network architecture considers an opportunistic fall-back to 2.4/5\,GHz in case of poor connectivity in the 60\,GHz domain. Further, to avoid the frequent re-beamforming in 60\,GHz directional links due to mobility, we propose a cognitive module -- a sensor-assisted intelligent beam switching procedure -- which reduces the communication overhead. We believe that the CogCell concept will help future indoor communications and possibly outdoor hotspots, where mobile stations and access points collaborate with each other to improve the user experience.
Development of a Burst Buffer System for Data-Intensive Applications
Venue: arXiv cs.DC 2015
Year: 2015

Modern parallel filesystems such as Lustre are designed to provide high, scalable I/O bandwidth in response to growing I/O requirements; however, the bursty I/O characteristics of many data-intensive scientific applications make it difficult for back-end parallel filesystems to efficiently handle I/O requests. A burst buffer system, through which data can be temporarily buffered via high-performance storage mediums, allows for gradual flushing of data to back-end filesystems. In this paper, we explore issues surrounding the development of a burst buffer system for data-intensive scientific applications. Our initial results demonstrate that utilizing a burst buffer system on top of the Lustre filesystem shows promise for dealing with the intense I/O traffic generated by application checkpointing.
Optimal Decision-Theoretic Classification Using Non-Decomposable Performance Metrics
Venue: arXiv cs.LG 2015
Year: 2015

We provide a general theoretical analysis of expected out-of-sample utility, also referred to as decision-theoretic classification, for non-decomposable binary classification metrics such as F-measure and Jaccard coefficient. Our key result is that the expected out-of-sample utility for many performance metrics is provably optimized by a classifier which is equivalent to a signed thresholding of the conditional probability of the positive class. Our analysis bridges a gap in the literature on binary classification, revealed in light of recent results for non-decomposable metrics in population utility maximization style classification. Our results identify checkable properties of a performance metric which are sufficient to guarantee a probability ranking principle. We propose consistent estimators for optimal expected out-of-sample classification. As a consequence of the probability ranking principle, computational requirements can be reduced from exponential to cubic complexity in the general case, and further reduced to quadratic complexity in special cases. We provide empirical results on simulated and benchmark datasets evaluating the performance of the proposed algorithms for decision-theoretic classification and comparing them to baseline and state-of-the-art methods in population utility maximization for non-decomposable metrics.
An LP-based inconsistency monitoring of pairwise comparison matrices
Venue: arXiv cs.OH 2015
Year: 2015

A distance-based inconsistency indicator, defined by the third author for the consistency-driven pairwise comparisons method, is extended to the incomplete case. The corresponding optimization problem is transformed into an equivalent linear programming problem. The results can be applied in the process of filling in the matrix as the decision maker gets automatic feedback. As soon as a serious error occurs among the matrix elements, even due to a misprint, a significant increase in the inconsistency index is reported. The high inconsistency may be alarmed not only at the end of the process of filling in the matrix but also during the completion process. Numerical examples are also provided.
Energy Efficient Symbol-Level Precoding in Multiuser MISO Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the idea of exploiting interference among the simultaneous multiuser transmissions in the downlink of multiple antennas systems. Using symbol level precoding, a new approach towards addressing the multiuser interference is discussed through jointly utilizing the channel state information (CSI) and data information (DI). In this direction, the interference among the data streams is transformed under certain conditions to useful signal that can improve the signal to interference noise ratio (SINR) of the downlink transmissions. In this context, new constructive interference precoding techniques that tackle the transmit power minimization (min power) with individual SINR constraints at each user's receivers are proposed. Furthermore, we investigate the CI precoding design under the assumption that the received MPSK symbol can reside in a relaxed region in order to be correctly detected.
Applying Sorting Networks to Synthesize Optimized Sorting Libraries
Venue: arXiv cs.DS 2015
Year: 2015

This paper shows an application of the theory of sorting networks to facilitate the synthesis of optimized general purpose sorting libraries. Standard sorting libraries are often based on combinations of the classic Quicksort algorithm with insertion sort applied as the base case for small fixed numbers of inputs. Unrolling the code for the base case by ignoring loop conditions eliminates branching and results in code which is equivalent to a sorting network. This enables the application of further program transformations based on sorting network optimizations, and eventually the synthesis of code from sorting networks. We show that if considering the number of comparisons and swaps then theory predicts no real advantage of this approach. However, significant speed-ups are obtained when taking advantage of instruction level parallelism and non-branching conditional assignment instructions, both of which are common in modern CPU architectures. We provide empirical evidence that using code synthesized from efficient sorting networks as the base case for Quicksort libraries results in significant real-world speed-ups.
Evolving Boolean Networks with RNA Editing
Venue: arXiv cs.NE 2015
Year: 2015

The editing of transcribed RNA by other molecules such that the form of the final product differs from that specified in the corresponding DNA sequence is ubiquitous. This paper uses an abstract, tunable Boolean genetic regulatory network model to explore aspects of RNA editing. In particular, it is shown how dynamically altering expressed sequences via a guide RNA-inspired mechanism can be selected for by simulated evolution under various single and multicellular scenarios.
Density Estimations for Approximate Query Processing on SIMD Architectures
Venue: arXiv cs.DC 2015
Year: 2015

Approximate query processing (AQP) is an interesting alternative for exact query processing. It is a tool for dealing with the huge data volumes where response time is more important than perfect accuracy (this is typically the case during initial phase of data exploration). There are many techniques for AQP, one of them is based on probability density functions (PDF). PDFs are typically calculated using nonparametric data-driven methods. One of the most popular nonparametric method is the kernel density estimator (KDE). However, a very serious drawback of using KDEs is the large number of calculations required to compute them. The shape of final density function is very sensitive to an entity called bandwidth or smoothing parameter. Calculating it's optimal value is not a trivial task and in general is very time consuming. In this paper we investigate the possibility of utilizing two SIMD architectures: SSE CPU extensions and NVIDIA's CUDA architecture to accelerate finding of the bandwidth. Our experiments show orders of magnitude improvements over a simple sequential implementation of classical algorithms used for that task.
Decomposition of Power Flow Used for Optimizing Zonal Configurations of Energy Market
Venue: arXiv cs.CE 2015
Year: 2015

Zonal configuration of energy market is often a consequence of political borders. However there are a few methods developed to help with zonal delimitation in respect to some measures. This paper presents the approach aiming at reduction of the loop flow effect - an element of unscheduled flows which introduces a loss of market efficiency. In order to undertake zonal partitioning, a detailed decomposition of power flow is performed. Next, we identify the zone which is a source of the problem and enhance delimitation by dividing it into two zones. The procedure is illustrated by a study of simple case.
The Anatomy and Facets of Dynamic Policies
Venue: arXiv cs.CR 2015
Year: 2015

Information flow policies are often dynamic; the security concerns of a program will typically change during execution to reflect security-relevant events. A key challenge is how to best specify, and give proper meaning to, such dynamic policies. A large number of approaches exist that tackle that challenge, each yielding some important, but unconnected, insight. In this work we synthesise existing knowledge on dynamic policies, with an aim to establish a common terminology, best practices, and frameworks for reasoning about them. We introduce the concept of facets to illuminate subtleties in the semantics of policies, and closely examine the anatomy of policies and the expressiveness of policy specification mechanisms. We further explore the relation between dynamic policies and the concept of declassification.
Optimal Quantization of TV White Space Regions for a Broadcast Based Geolocation Database
Venue: arXiv cs.IT 2015
Year: 2015

In the current paradigm, TV white space databases communicate the available channels over a reliable Internet connection to the secondary devices. For places where an Internet connection is not available, such as in developing countries, a broadcast based geolocation database can be considered. This geolocation database will broadcast the TV white space (or the primary services protection regions) on rate-constrained digital channel. In this work, the quantization or digital representation of protection regions is considered for rate-constrained broadcast geolocation database. Protection regions should not be declared as white space regions due to the quantization error. In this work, circular and basis based approximations are presented for quantizing the protection regions. In circular approximation, quantization design algorithms are presented to protect the primary from quantization error while minimizing the white space area declared as protected region. An efficient quantizer design algorithm is presented in this case. For basis based approximations, an efficient method to represent the protection regions by an `envelope' is developed. By design this envelope is a sparse approximation, i.e., it has lesser number of non-zero coefficients in the basis when compared to the original protection region. The approximation methods presented in this work are tested using three experimental data-sets.