OpenRaiser/Intern-Atlas huggingface dataset:
Nonlinearity of quartic rotation symmetric Boolean functions
Venue: arXiv cs.IT 2012
Year: 2012

Nonlinearity of rotation symmetric Boolean functions is an important topic on cryptography algorithm. Let $e\ge 1$ be any given integer. In this paper, we investigate the following question: Is the nonlinearity of the quartic rotation symmetric Boolean function generated by the monomial $x_0x_ex_{2e}x_{3e}$ equal to its weight? We introduce some new simple sub-functions and develop new technique to get several recursive formulas. Then we use these recursive formulas to show that the nonlinearity of the quartic rotation symmetric Boolean function generated by the monomial $x_0x_ex_{2e}x_{3e}$ is the same as its weight. So we answer the above question affirmatively. Finally, we conjecture that if $l\ge 4$ is an integer, then the nonlinearity of the rotation symmetric Boolean function generated by the monomial $x_0x_ex_{2e}...x_{le}$ equals its weight.
TCP Congestion Control over HSDPA: an Experimental Evaluation
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we focus on the experimental evaluation of TCP over the High Speed Downlink Packet Access (HSDPA), an upgrade of UMTS that is getting worldwide deployment. Today, this is particularly important in view of the "liberalization" brought in by the Linux OS which offers several variants of TCP congestion control. In particular, we consider four TCP variants: 1) TCP NewReno, which is the only congestion control standardized by the IETF; 2) TCP BIC, that was, and 3) TCP Cubic that is the default algorithm in the Linux OS; 4) Westwood+ TCP that has been shown to be particularly effective over wireless links. Main results are that all the TCP variants provide comparable goodputs but with significant larger round trip times and number of retransmissions and timeouts in the case of TCP BIC/Cubic, which is a consequence of their more aggressive probing phases. On the other hand, TCP Westwood+ provides the shortest round trip delays, which is an effect of its unique way of setting control windows after congestion episode based on bandwidth measurements.
Foundations of scientific research (Foundations of Research Activities)
Venue: arXiv cs.OH 2012
Year: 2012

During years 2008 to 2011 author gives several courses on Foundations of Scientific Research at Computer Science Faculty of the National Aviation University in Kiev. This text presents material to lectures of the courses. It consists of 18 sections and some ideas of the manual can be seen from their titles. These include: General notions about scientific research. Ontologies and upper ontologies. Ontologies of object domains. Examples of Research Activity. Some Notions of the Theory of Finite and Discrete Sets. Algebraic Operations and Algebraic Structures. Elements of the Theory of Graphs and Nets. Scientific activity on the example of Information and its investigation. Scientific research in Artificial Intelligence. Compilers and compilation. Objective, Concepts and History of Computer security. Methodological and categorical apparatus of scientific research. Methodology and methods of scientific research. Scientific idea and significance of scientific research. Forms of scientific knowledge organization and principles of scientific research. Theoretical study, applied study and creativity. Types of scientific research: theoretical study, applied study. Types of scientific research: forms of representation of material. Some sections of the text contain enough material to lectures, but in some cases these are sketchs without references to Foundations of Research Activities. Really this is the first version of the manual and author plans to edit, modify and extend the version. Some reasons impose the author to post it as e-print. . Author compiled material from many sources and hope that it gives various points of view on Foundations of Research Activities.
Non-Systematic Complex Number RS Coded OFDM by Unique Word Prefix
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we expand our recently introduced concept of UW-OFDM (unique word orthogonal frequency division multiplexing). In UW-OFDM the cyclic prefixes (CPs) are replaced by deterministic sequences, the so-called unique words (UWs). The UWs are generated by appropriately loading a set of redundant subcarriers. By that a systematic complex number Reed Solomon (RS) code construction is introduced in a quite natural way, because an RS code may be defined as the set of vectors, for which a block of successive zeros occurs in the other domain w.r.t. a discrete Fourier transform. (For a fixed block different to zero, i.e., a UW, a coset code of an RS code is generated.) A remaining problem in the original systematic coded UW-OFDM concept is the fact that the redundant subcarrier symbols disproportionately contribute to the mean OFDM symbol energy. In this paper we introduce the concept of non-systematic coded UW-OFDM, where the redundancy is no longer allocated to dedicated subcarriers, but distributed over all subcarriers. We derive optimum complex valued code generator matrices matched to the BLUE (best linear unbiased estimator) and to the LMMSE (linear minimum mean square error) data estimator, respectively. With the help of simulations we highlight the advantageous spectral properties and the superior BER (bit error ratio) performance of non-systematic coded UW-OFDM compared to systematic coded UW-OFDM as well as to CP-OFDM in AWGN (additive white Gaussian noise) and in frequency selective environments.
Hybrid Optimized Back propagation Learning Algorithm For Multi-layer Perceptron
Venue: arXiv cs.NE 2012
Year: 2012

Standard neural network based on general back propagation learning using delta method or gradient descent method has some great faults like poor optimization of error-weight objective function, low learning rate, instability .This paper introduces a hybrid supervised back propagation learning algorithm which uses trust-region method of unconstrained optimization of the error objective function by using quasi-newton method .This optimization leads to more accurate weight update system for minimizing the learning error during learning phase of multi-layer perceptron.[13][14][15] In this paper augmented line search is used for finding points which satisfies Wolfe condition. In this paper, This hybrid back propagation algorithm has strong global convergence properties & is robust & efficient in practice.
On Extracting Unit Tests from Interactive Programming Sessions
Venue: arXiv cs.SE 2012
Year: 2012

Software engineering methodologies propose that developers should capture their efforts in ensuring that programs run correctly in repeatable and automated artifacts, such as unit tests. However, when looking at developer activities on a spectrum from exploratory testing to scripted testing we find that many engineering activities include bursts of exploratory testing. In this paper we propose to leverage these exploratory testing bursts by automatically extracting scripted tests from a recording of these sessions. In order to do so, we wiretap the development environment so we can record all program input, all user-issued functions calls, and all program output of an exploratory testing session. We propose to then use machine learning (i.e. clustering) to extract scripted test cases from these recordings in real-time. We outline two early-stage prototypes, one for a static and one for a dynamic language. And we outline how this idea fits into the bigger research direction of programming by example.
A Heuristic Reputation Based System to Detect Spam activities in a Social Networking Platform, HRSSSNP
Venue: arXiv cs.CR 2012
Year: 2012

The introduction of the social networking platform has drastically affected the way individuals interact. Even though most of the effects have been positive, there exist some serious threats associated with the interactions on a social networking website. A considerable proportion of the crimes that occur are initiated through a social networking platform [5]. Almost 33% of the crimes on the internet are initiated through a social networking website [5]. Moreover activities like spam messages create unnecessary traffic and might affect the user base of a social networking platform. As a result preventing interactions with malicious intent and spam activities becomes crucial. This work attempts to detect the same in a social networking platform by considering a social network as a weighted graph wherein each node, which represents an individual in the social network, stores activities of other nodes with respect to itself in an optimized format which is referred to as localized data-set. The weights associated with the edges in the graph represent the trust relationship between profiles. The weights of the edges along with the localized data-set is used to infer whether nodes in the social network are compromised and are performing spam or malicious activities.
User Taglines: Alternative Presentations of Expertise and Interest in Social Media
Venue: arXiv cs.SI 2012
Year: 2012

Web applications are increasingly showing recommended users from social media along with some descriptions, an attempt to show relevancy - why they are being shown. For example, Twitter search for a topical keyword shows expert twitterers on the side for 'whom to follow'. Google+ and Facebook also recommend users to follow or add to friend circle. Popular Internet newspaper- The Huffington Post shows Twitter influencers/ experts on the side of an article for authoritative relevant tweets. The state of the art shows user profile bios as summary for Twitter experts, but it has issues with length constraint imposed by user interface (UI) design, missing bio and sometimes funny profile bio. Alternatively, applications can use human generated user summary, but it will not scale. Therefore, we study the problem of automatic generation of informative expertise summary or taglines for Twitter experts in space constraint imposed by UI design. We propose three methods for expertise summary generation- Occupation-Pattern based, Link-Triangulation based and User-Classification based, with use of knowledge-enhanced computing approaches. We also propose methods for final summary selection for users with multiple candidates of generated summaries. We evaluate the proposed approaches by user-study using a number of experiments. Our results show promising quality of 92.8% good summaries with majority agreement in the best case and 70% with majority agreement in the worst case. Our approaches also outperform the state of the art up to 88%. This study has implications in the area of expert profiling, user presentation and application design for engaging user experience.
A Generation-based Text Steganography Method using SQL Queries
Venue: arXiv cs.CR 2012
Year: 2012

Cryptography and Steganography are two techniques commonly used to secure and safely transmit digital data. Nevertheless, they do differ in important ways. In fact, cryptography scrambles data so that they become unreadable by eavesdroppers; while, steganography hides the very existence of data so that they can be transferred unnoticed. Basically, steganography is a technique for hiding data such as messages into another form of data such as images. Currently, many types of steganography are in use; however, there is yet no known steganography application for query languages such as SQL. This paper proposes a new steganography method for textual data. It encodes input text messages into SQL carriers made up of SELECT queries. In effect, the output SQL carrier is dynamically generated out of the input message using a dictionary of words implemented as a hash table and organized into 65 categories, each of which represents a particular character in the language. Generally speaking, every character in the message to hide is mapped to a random word from a corresponding category in the dictionary. Eventually, all input characters are transformed into output words which are then put together to form an SQL query. Experiments conducted, showed how the proposed method can operate on real examples proving the theory behind it. As future work, other types of SQL queries are to be researched including INSERT, DELETE, and UPDATE queries, making the SQL carrier quite puzzling for malicious third parties to recuperate the secret message that it encodes.
Small-Size Relative (p,Epsilon)-Approximations for Well-Behaved Range Spaces
Venue: arXiv cs.CG 2012
Year: 2012

We present improved upper bounds for the size of relative (p,Epsilon)-approximation for range spaces with the following property: For any (finite) range space projected onto (that is, restricted to) a ground set of size n and for any parameter 1 <= k <= n, the number of ranges of size at most k is only nearly-linear in n and polynomial in k. Such range spaces are called "well behaved". Our bound is an improvement over the bound O(\log{(1/p)/\eps^2 p) introduced by Li etal. for the general case (where this bound has been shown to be tight in the worst case), when p << Epsilon. We also show that such small size relative (p,Epsilon)-approximations can be constructed in expected polynomial time. Our bound also has an interesting interpretation in the context of "p-nets": As observed by Har-Peled and Sharir, p-nets are special cases of relative (p,Epsilon)-approximations. Specifically, when Epsilon is a constant smaller than 1, their analysis implies that there are p-nets of size O(\log{(1/p)}/p) that are \emph{also} relative approximations. In this context our construction significantly improves this bound for well-behaved range spaces. Despite the progress in the theory of p-nets and the existence of improved bounds corresponding to the cases that we study, these bounds do not necessarily guarantee a bounded relative error. Lastly, we present several geometric scenarios of well-behaved range spaces, and show the resulting bound for each of these cases obtained as a consequence of our analysis. In particular, when Epsilon is a constant smaller than 1, our bound for points and axis-parallel boxes in two and three dimensions, as well as points and "fat" triangles in the plane, matches the optimal bound for p-nets.
Semantics and Security Issues in JavaScript
Venue: arXiv cs.PL 2012
Year: 2012

There is a plethora of research articles describing the deep semantics of JavaScript. Nevertheless, such articles are often difficult to grasp for readers not familiar with formal semantics. In this report, we propose a digest of the semantics of JavaScript centered around security concerns. This document proposes an overview of the JavaScript language and the misleading semantic points in its design. The first part of the document describes the main characteristics of the language itself. The second part presents how those characteristics can lead to problems. It finishes by showing some coding patterns to avoid certain traps and presents some ECMAScript 5 new features.
Enhanced Mobile Digital Video Broadcasting with Distributed Space-Time Coding
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates the distributed space-time (ST) coding proposals for the future Digital Video Broadcasting--Next Generation Handheld (DVB-NGH) standard. We first theoretically show that the distributed MIMO scheme is the best broadcasting scenario in terms of channel capacity. Consequently we evaluate the performance of several ST coding proposals for DVB-NGH with practical system specifications and channel conditions. Simulation results demonstrate that the 3D code is the best ST coding solution for broadcasting in the distributed MIMO scenario.
On the complexity of learning a language: An improvement of Block's algorithm
Venue: arXiv cs.CL 2012
Year: 2012

Language learning is thought to be a highly complex process. One of the hurdles in learning a language is to learn the rules of syntax of the language. Rules of syntax are often ordered in that before one rule can applied one must apply another. It has been thought that to learn the order of n rules one must go through all n! permutations. Thus to learn the order of 27 rules would require 27! steps or 1.08889x10^{28} steps. This number is much greater than the number of seconds since the beginning of the universe! In an insightful analysis the linguist Block ([Block 86], pp. 62-63, p.238) showed that with the assumption of transitivity this vast number of learning steps reduces to a mere 377 steps. We present a mathematical analysis of the complexity of Block's algorithm. The algorithm has a complexity of order n^2 given n rules. In addition, we improve Block's results exponentially, by introducing an algorithm that has complexity of order less than n log n.
A beaconing approach whith key exchange in vehicular ad hoc networks
Venue: arXiv cs.CR 2012
Year: 2012

Vehicular Ad-Hoc Networks (VANETs) are special forms of Mobile Ad-Hoc Networks (MANETs) that allows vehicles to communicate together in the absence of fixed infrastructure.In this type of network beaconing is the means used to discover the nodes in its eighborhood.For routing protocol successful delivery of beacons containing speed, direction and position of a car is extremely important.Otherwise, routing information should not be modified/manipulated during transmission without detection, in order to ensure the routing information, messages must be signed and provided with a certificate to attest valid network participants. In this work we present a beaconing protocol with key exchange to prepare the generation of a signature to protect the routing information protocol 'Greedy Perimeter Stateless Routing'.
Mining Techniques in Network Security to Enhance Intrusion Detection Systems
Venue: arXiv cs.CR 2012
Year: 2012

In intrusion detection systems, classifiers still suffer from several drawbacks such as data dimensionality and dominance, different network feature types, and data impact on the classification. In this paper two significant enhancements are presented to solve these drawbacks. The first enhancement is an improved feature selection using sequential backward search and information gain. This, in turn, extracts valuable features that enhance positively the detection rate and reduce the false positive rate. The second enhancement is transferring nominal network features to numeric ones by exploiting the discrete random variable and the probability mass function to solve the problem of different feature types, the problem of data dominance, and data impact on the classification. The latter is combined to known normalization methods to achieve a significant hybrid normalization approach. Finally, an intensive and comparative study approves the efficiency of these enhancements and shows better performance comparing to other proposed methods.
Monte Carlo Matrix Inversion Policy Evaluation
Venue: arXiv cs.LG 2012
Year: 2012

In 1950, Forsythe and Leibler (1950) introduced a statistical technique for finding the inverse of a matrix by characterizing the elements of the matrix inverse as expected values of a sequence of random walks. Barto and Duff (1994) subsequently showed relations between this technique and standard dynamic programming and temporal differencing methods. The advantage of the Monte Carlo matrix inversion (MCMI) approach is that it scales better with respect to state-space size than alternative techniques. In this paper, we introduce an algorithm for performing reinforcement learning policy evaluation using MCMI. We demonstrate that MCMI improves on runtime over a maximum likelihood model-based policy evaluation approach and on both runtime and accuracy over the temporal differencing (TD) policy evaluation approach. We further improve on MCMI policy evaluation by adding an importance sampling technique to our algorithm to reduce the variance of our estimator. Lastly, we illustrate techniques for scaling up MCMI to large state spaces in order to perform policy improvement.
Learning Riemannian Metrics
Venue: arXiv cs.LG 2012
Year: 2012

We propose a solution to the problem of estimating a Riemannian metric associated with a given differentiable manifold. The metric learning problem is based on minimizing the relative volume of a given set of points. We derive the details for a family of metrics on the multinomial simplex. The resulting metric has applications in text classification and bears some similarity to TFIDF representation of text documents.
Approximate Inference and Constrained Optimization
Venue: arXiv cs.LG 2012
Year: 2012

Loopy and generalized belief propagation are popular algorithms for approximate inference in Markov random fields and Bayesian networks. Fixed points of these algorithms correspond to extrema of the Bethe and Kikuchi free energy. However, belief propagation does not always converge, which explains the need for approaches that explicitly minimize the Kikuchi/Bethe free energy, such as CCCP and UPS. Here we describe a class of algorithms that solves this typically nonconvex constrained minimization of the Kikuchi free energy through a sequence of convex constrained minimizations of upper bounds on the Kikuchi free energy. Intuitively one would expect tighter bounds to lead to faster algorithms, which is indeed convincingly demonstrated in our simulations. Several ideas are applied to obtain tight convex bounds that yield dramatic speed-ups over CCCP.
Decision Making with Partially Consonant Belief Functions
Venue: arXiv cs.AI 2012
Year: 2012

This paper studies decision making for Walley's partially consonant belief functions (pcb). In a pcb, the set of foci are partitioned. Within each partition, the foci are nested. The pcb class includes probability functions and possibility functions as extreme cases. Unlike earlier proposals for a decision theory with belief functions, we employ an axiomatic approach. We adopt an axiom system similar in spirit to von Neumann - Morgenstern's linear utility theory for a preference relation on pcb lotteries. We prove a representation theorem for this relation. Utility for a pcb lottery is a combination of linear utility for probabilistic lottery and binary utility for possibilistic lottery.
Solving MAP Exactly using Systematic Search
Venue: arXiv cs.AI 2012
Year: 2012

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network given some evidence. Unlike computing posterior probabilities, or MPE (a special case of MAP), the time and space complexity of structural solutions for MAP are not only exponential in the network treewidth, but in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computing posterior probabilities or MPE. This paper introduces a new, simple upper bound on the probability of a MAP solution, which admits a tradeoff between the bound quality and the time needed to compute it. The bound is shown to be generally much tighter than those of other methods of comparable complexity. We use this proposed upper bound to develop a branch-and-bound search algorithm for solving MAP exactly. Experimental results demonstrate that the search algorithm is able to solve many problems that are far beyond the reach of any structure-based method for MAP. For example, we show that the proposed algorithm can compute MAP exactly and efficiently for some networks whose constrained treewidth is more than 40.
On Local Optima in Learning Bayesian Networks
Venue: arXiv cs.LG 2012
Year: 2012

This paper proposes and evaluates the k-greedy equivalence search algorithm (KES) for learning Bayesian networks (BNs) from complete data. The main characteristic of KES is that it allows a trade-off between greediness and randomness, thus exploring different good local optima. When greediness is set at maximum, KES corresponds to the greedy equivalence search algorithm (GES). When greediness is kept at minimum, we prove that under mild assumptions KES asymptotically returns any inclusion optimal BN with nonzero probability. Experimental results for both synthetic and real data are reported showing that KES often finds a better local optima than GES. Moreover, we use KES to experimentally confirm that the number of different local optima is often huge.