OpenRaiser/Intern-Atlas huggingface dataset:
Inferring Social Rank in an Old Assyrian Trade Network
Venue: arXiv cs.CY 2013
Year: 2013

We present work in jointly inferring the unique individuals as well as their social rank within a collection of letters from an Old Assyrian trade colony in Kültepe, Turkey, settled by merchants from the ancient city of Assur for approximately 200 years between 1950-1750 BCE, the height of the Middle Bronze Age. Using a probabilistic latent-variable model, we leverage pairwise social differences between names in cuneiform tablets to infer a single underlying social order that best explains the data we observe. Evaluating our output with published judgments by domain experts suggests that our method may be used for building informed hypotheses that are driven by data, and that may offer promising avenues for directed research by Assyriologists.
Statistical Texture Features based Handwritten and Printed Text Classification in South Indian Documents
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we use statistical texture features for handwritten and printed text classification. We primarily aim for word level classification in south Indian scripts. Words are first extracted from the scanned document. For each extracted word, statistical texture features are computed such as mean, standard deviation, smoothness, moment, uniformity, entropy and local range including local entropy. These feature vectors are then used to classify words via k-NN classifier. We have validated the approach over several different datasets. Scripts like Kannada, Telugu, Malayalam and Hindi i.e., Devanagari are primarily employed where an average classification rate of 99.26% is achieved. In addition, to provide an extensibility of the approach, we address Roman script by using publicly available dataset and interesting results are reported.
Features and Aggregators for Web-scale Entity Search
Venue: arXiv cs.IR 2013
Year: 2013

We focus on two research issues in entity search: scoring a document or snippet that potentially supports a candidate entity, and aggregating scores from different snippets into an entity score. Proximity scoring has been studied in IR outside the scope of entity search. However, aggregation has been hardwired except in a few cases where probabilistic language models are used. We instead explore simple, robust, discriminative ranking algorithms, with informative snippet features and broad families of aggregation functions. Our first contribution is a study of proximity-cognizant snippet features. In contrast with prior work which uses hardwired "proximity kernels" that implement a fixed decay with distance, we present a "universal" feature encoding which jointly expresses the perplexity (informativeness) of a query term match and the proximity of the match to the entity mention. Our second contribution is a study of aggregation functions. Rather than train the ranking algorithm on snippets and then aggregate scores, we directly train on entities such that the ranking algorithm takes into account the aggregation function being used. Our third contribution is an extensive Web-scale evaluation of the above algorithms on two data sets having quite different properties and behavior. The first one is the W3C dataset used in TREC-scale enterprise search, with pre-annotated entity mentions. The second is a Web-scale open-domain entity search dataset consisting of 500 million Web pages, which contain about 8 billion token spans annotated automatically with two million entities from 200,000 entity types in Wikipedia. On the TREC dataset, the performance of our system is comparable to the currently prevalent systems. On the much larger and noisier Web dataset, our system delivers significantly better performance than all other systems, with 8% MAP improvement over the closest competitor.
Joint Optimization of Throughput and Packet Drop Rate for Delay Sensitive Applications in TDD Satellite Network Coded Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the issue of throughput and packet drop rate (PDR) optimization as two performance metrics for delay sensitive applications in network coded time division duplex (TDD) satellite systems with large round trip times (RTT). We adopt random linear network coding (RLNC) under two different scenarios, feedback-less and with feedback, and our goal is to jointly optimize the mean throughputs and PDRs of users in the system. For this purpose, we propose a systematic framework and start with formulating and optimizing these performance metrics for the single-user case. This framework enables us to analytically compare the performance metrics under different system parameters and settings. By comparing RLNC schemes under feedback-less and feedback scenarios for different RTTs, we show that the feedback-less schemes outperform the schemes with feedback in TDD systems with large RTTs. Then, we extend the study of feedback-less RLNC schemes to the multi-user broadcast case. Here, we consider a number of different broadcast scenarios and optimize the system parameters such that the best overall performance is achieved. Furthermore, the complicated interplay of the mean throughputs and PDRs of different users with different packet erasure conditions in each of the considered broadcast scenarios is discussed.
Types and forgetfulness in categorical linguistics and quantum mechanics
Venue: arXiv cs.CL 2013
Year: 2013

The role of types in categorical models of meaning is investigated. A general scheme for how typed models of meaning may be used to compare sentences, regardless of their grammatical structure is described, and a toy example is used as an illustration. Taking as a starting point the question of whether the evaluation of such a type system 'loses information', we consider the parametrized typing associated with connectives from this viewpoint. The answer to this question implies that, within full categorical models of meaning, the objects associated with types must exhibit a simple but subtle categorical property known as self-similarity. We investigate the category theory behind this, with explicit reference to typed systems, and their monoidal closed structure. We then demonstrate close connections between such self-similar structures and dagger Frobenius algebras. In particular, we demonstrate that the categorical structures implied by the polymorphically typed connectives give rise to a (lax unitless) form of the special forms of Frobenius algebras known as classical structures, used heavily in abstract categorical approaches to quantum mechanics.
Distributed Space-Time Coding of Over-the-Air Superimposed Packets in Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we propose a new cooperative packet transmission scheme that allows independent sources to superimpose over-the-air their packet transmissions. Relay nodes are used and cooperative diversity is combined with distributed space-time block coding (STBC). With the proposed scheme the participating relays create a ST code for the over-the-air superimposed symbols that are received locally and without proceeding to any decoding step beforehand. The advantage of the proposed scheme is that communication is completed in fewer transmission slots because of the concurrent packet transmissions, while the diversity benefit from the use of the STBC results in higher decoding performance. The proposed scheme does not depend on the STBC that is applied at the relays. Simulation results reveal significant throughput benefits even in the low SNR regime.
Proposed Video Encryption Algorithm v/s Other Existing Algorithms: A Comparative Study
Venue: arXiv cs.CR 2013
Year: 2013

Securing multimedia data has become of utmost importance especially in the applications related to military purposes. With the rise in development in computer and internet technology, multimedia data has become the most convenient method for military training. An innovative encryption algorithm for videos compressed using H.264 was proposed to safely exchange highly confidential videos. To maintain a balance between security and computational time, the proposed algorithm shuffles the video frames along with the audio, and then AES is used to selectively encrypt the sensitive video codewords. Using this approach unauthorized viewing of the video file can be prevented and hence this algorithm provides a high level of security. A comparative study of the proposed algorithm with other existing algorithms has been put forward in this paper to prove the effectiveness of the proposed algorithm.
Blind Identification of SIMO Wiener Systems based on Kernel Canonical Correlation Analysis
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of blind identification and equalization of single-input multiple-output (SIMO) nonlinear channels. Specifically, the nonlinear model consists of multiple single-channel Wiener systems that are excited by a common input signal. The proposed approach is based on a well-known blind identification technique for linear SIMO systems. By transforming the output signals into a reproducing kernel Hilbert space (RKHS), a linear identification problem is obtained, which we propose to solve through an iterative procedure that alternates between canonical correlation analysis (CCA) to estimate the linear parts, and kernel canonical correlation (KCCA) to estimate the memoryless nonlinearities. The proposed algorithm is able to operate on systems with as few as two output channels, on relatively small data sets and on colored signals. Simulations are included to demonstrate the effectiveness of the proposed technique.
Classification of Boolean Functions where Affine Functions are Uniformly Distributed
Venue: arXiv cs.LO 2013
Year: 2013

Classification of Non-linear Boolean functions is a long-standing problem in the area of theoretical computer science. In this paper, effort has been made to achieve a systematic classification of all n-variable Boolean functions, where only one affine Boolean function belongs to each class. Two different methods are proposed to achieve this classification. The first method is a recursive procedure that uses the Cartesian product of sets starting from the set of 1-variable Boolean function and in the second method classification is achieved through a set of invariant bit positions with respect to an affine function belonging to that class. The invariant bit positions also provide information concerning the size and symmetry properties of the classes/sub-classes, such that the members of classes/sub-classes satisfy certain similar properties.
A survey on sensing methods and feature extraction algorithms for SLAM problem
Venue: arXiv cs.RO 2013
Year: 2013

This paper is a survey work for a bigger project for designing a Visual SLAM robot to generate 3D dense map of an unknown unstructured environment. A lot of factors have to be considered while designing a SLAM robot. Sensing method of the SLAM robot should be determined by considering the kind of environment to be modeled. Similarly the type of environment determines the suitable feature extraction method. This paper goes through the sensing methods used in some recently published papers. The main objective of this survey is to conduct a comparative study among the current sensing methods and feature extraction algorithms and to extract out the best for our work.
Adaptive Reduced-Rank MBER Linear Receive Processing for Large Multiuser MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we propose a novel adaptive reduced-rank strategy based on joint interpolation, decimation and filtering (JIDF) for large multiuser multiple-input multiple-output (MIMO) systems. In this scheme, a reduced-rank framework is proposed for linear receive processing and multiuser interference suppression according to the minimization of the bit error rate (BER) cost function. We present a structure with multiple processing branches that performs dimensionality reduction, where each branch contains a group of jointly optimized interpolation and decimation units, followed by a linear receive filter. We then develop stochastic gradient (SG) algorithms to compute the parameters of the interpolation and receive filters along with a low-complexity decimation technique. Simulation results are presented for time-varying environments and show that the proposed MBER-JIDF receive processing strategy and algorithms achieve a superior performance to existing methods at a reduced complexity.
Future Evolution of CSMA Protocols for the IEEE 802.11 Standard
Venue: arXiv cs.NI 2013
Year: 2013

In this paper a candidate protocol to replace the prevalent CSMA/CA medium access control in Wireless Local Area Networks is presented. The proposed protocol can achieve higher throughput than CSMA/CA, while maintaining fairness, and without additional implementation complexity. Under certain circumstances, it is able to reach and maintain collision-free operation, even when the number of contenders is variable and potentially large. It is backward compatible, allowing for new and legacy stations to coexist without degrading one another's performance, a property that can make the adoption process by future versions of the standard smooth and inexpensive.
Friend or Foe? Fake Profile Identification in Online Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

The amount of personal information unwillingly exposed by users on online social networks is staggering, as shown in recent research. Moreover, recent reports indicate that these networks are infested with tens of millions of fake users profiles, which may jeopardize the users' security and privacy. To identify fake users in such networks and to improve users' security and privacy, we developed the Social Privacy Protector software for Facebook. This software contains three protection layers, which improve user privacy by implementing different methods. The software first identifies a user's friends who might pose a threat and then restricts this "friend's" exposure to the user's personal information. The second layer is an expansion of Facebook's basic privacy settings based on different types of social network usage profiles. The third layer alerts users about the number of installed applications on their Facebook profile, which have access to their private information. An initial version of the Social Privacy Protection software received high media coverage, and more than 3,000 users from more than twenty countries have installed the software, out of which 527 used the software to restrict more than nine thousand friends. In addition, we estimate that more than a hundred users accepted the software's recommendations and removed at least 1,792 Facebook applications from their profiles. By analyzing the unique dataset obtained by the software in combination with machine learning techniques, we developed classifiers, which are able to predict which Facebook profiles have high probabilities of being fake and therefore, threaten the user's well-being. Moreover, in this study, we present statistics on users' privacy settings and statistics of the number of applications installed on Facebook profiles...
Alternating Traps in Muller and Parity Games
Venue: arXiv cs.LO 2013
Year: 2013

Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP and co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap-depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth.
A new class of superregular matrices and MDP convolutional codes
Venue: arXiv cs.IT 2013
Year: 2013

This paper deals with the problem of constructing superregular matrices that lead to MDP convolutional codes. These matrices are a type of lower block triangular Toeplitz matrices with the property that all the square submatrices that can possibly be nonsingular due to the lower block triangular structure are nonsingular. We present a new class of matrices that are superregular over a suficiently large finite field F. Such construction works for any given choice of characteristic of the field F and code parameters (n; k; d) such that (n-k)|d. Finally, we discuss the size of F needed so that the proposed matrices are superregular.
Grasping Complexity
Venue: arXiv cs.GL 2013
Year: 2013

The century of complexity has come. The face of science has changed. Surprisingly, when we start asking about the essence of these changes and then critically analyse the answers, the result are mostly discouraging. Most of the answers are related to the properties that have been in the focus of scientific research already for more than a century (like non-linearity). This paper is Preface to the special issue "Grasping Complexity" of the journal "Computers and Mathematics with Applications". We analyse the change of era in science, its reasons and main changes in scientific activity and give a brief review of the papers in the issue.
Efficient Evolutionary Algorithm for Single-Objective Bilevel Optimization
Venue: arXiv cs.NE 2013
Year: 2013

Bilevel optimization problems are a class of challenging optimization problems, which contain two levels of optimization tasks. In these problems, the optimal solutions to the lower level problem become possible feasible candidates to the upper level problem. Such a requirement makes the optimization problem difficult to solve, and has kept the researchers busy towards devising methodologies, which can efficiently handle the problem. Despite the efforts, there hardly exists any effective methodology, which is capable of handling a complex bilevel problem. In this paper, we introduce bilevel evolutionary algorithm based on quadratic approximations (BLEAQ) of optimal lower level variables with respect to the upper level variables. The approach is capable of handling bilevel problems with different kinds of complexities in relatively smaller number of function evaluations. Ideas from classical optimization have been hybridized with evolutionary methods to generate an efficient optimization algorithm for generic bilevel problems. The efficacy of the algorithm has been shown on two sets of test problems. The first set is a recently proposed SMD test set, which contains problems with controllable complexities, and the second set contains standard test problems collected from the literature. The proposed method has been evaluated against two benchmarks, and the performance gain is observed to be significant.
An Adaptive Methodology for Ubiquitous ASR System
Venue: arXiv cs.CL 2013
Year: 2013

Achieving and maintaining the performance of ubiquitous (Automatic Speech Recognition) ASR system is a real challenge. The main objective of this work is to develop a method that will improve and show the consistency in performance of ubiquitous ASR system for real world noisy environment. An adaptive methodology has been developed to achieve an objective with the help of implementing followings, -Cleaning speech signal as much as possible while preserving originality / intangibility using various modified filters and enhancement techniques. -Extracting features from speech signals using various sizes of parameter. -Train the system for ubiquitous environment using multi-environmental adaptation training methods. -Optimize the word recognition rate with appropriate variable size of parameters using fuzzy technique. The consistency in performance is tested using standard noise databases as well as in real world environment. A good improvement is noticed. This work will be helpful to give discriminative training of ubiquitous ASR system for better Human Computer Interaction (HCI) using Speech User Interface (SUI).
Simple Search Engine Model: Selective Properties
Venue: arXiv cs.IR 2013
Year: 2013

In this paper we study the relationship between query and search engine by exploring the selective properties based on a simple search engine. We used the set theory and utilized the words and terms for defining singleton and doubleton in the event spaces and then provided their implementation for proving the existence of the shadow of micro-cluster.
On Linear Spaces of Polyhedral Meshes
Venue: arXiv cs.GR 2013
Year: 2013

Polyhedral meshes (PM) - meshes having planar faces - have enjoyed a rise in popularity in recent years due to their importance in architectural and industrial design. However, they are also notoriously difficult to generate and manipulate. Previous methods start with a smooth surface and then apply elaborate meshing schemes to create polyhedral meshes approximating the surface. In this paper, we describe a reverse approach: given the topology of a mesh, we explore the space of possible planar meshes with that topology. Our approach is based on a complete characterization of the maximal linear spaces of polyhedral meshes contained in the curved manifold of polyhedral meshes with a given topology. We show that these linear spaces can be described as nullspaces of differential operators, much like harmonic functions are nullspaces of the Laplacian operator. An analysis of this operator provides tools for global and local design of a polyhedral mesh, which fully expose the geometric possibilities and limitations of the given topology.
Sharp Bounds in Stochastic Network Calculus
Venue: arXiv cs.PF 2013
Year: 2013

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of potential looseness of its performance bounds. In this paper it is uncovered that for bursty arrival processes (specifically Markov-Modulated On-Off (MMOO)), whose amenability to \textit{per-flow} analysis is typically proclaimed as a highlight of SNC, the bounds can unfortunately indeed be very loose (e.g., by several orders of magnitude off). In response to this uncovered weakness of SNC, the (Standard) per-flow bounds are herein improved by deriving a general sample-path bound, using martingale based techniques, which accommodates FIFO, SP, EDF, and GPS scheduling. The obtained (Martingale) bounds gain an exponential decay factor of ${\mathcal{O}}(e^{-αn})$ in the number of flows $n$. Moreover, numerical comparisons against simulations show that the Martingale bounds are remarkably accurate for FIFO, SP, and EDF scheduling; for GPS scheduling, although the Martingale bounds substantially improve the Standard bounds, they are numerically loose, demanding for improvements in the core SNC analysis of GPS.
A Qualitative Comparison of the Suitability of Four Theorem Provers for Basic Auction Theory
Venue: arXiv cs.LO 2013
Year: 2013

Novel auction schemes are constantly being designed. Their design has significant consequences for the allocation of goods and the revenues generated. But how to tell whether a new design has the desired properties, such as efficiency, i.e. allocating goods to those bidders who value them most? We say: by formal, machine-checked proofs. We investigated the suitability of the Isabelle, Theorema, Mizar, and Hets/CASL/TPTP theorem provers for reproducing a key result of auction theory: Vickrey's 1961 theorem on the properties of second-price auctions. Based on our formalisation experience, taking an auction designer's perspective, we give recommendations on what system to use for formalising auctions, and outline further steps towards a complete auction theory toolbox.