OpenRaiser/Intern-Atlas huggingface dataset:
Matrix Codes as Ideals for Grassmannian Codes and their Weight Properties
Venue: arXiv cs.IT 2015
Year: 2015

A systematic way of constructing Grassmannian codes endowed with the subspace distance as lifts of matrix codes over the prime field $GF(p)$ is introduced. The matrix codes are $GF(p)$-subspaces of the ring $M_2(GF(p))$ of $2 \times 2$ matrices over $GF(p)$ on which the rank metric is applied, and are generated as one-sided proper principal ideals by idempotent elements of $M_2(GF(p))$. Furthermore a weight function on the non-commutative matrix ring $M_2(GF(p))$, $q$ a power of $p$, is studied in terms of the egalitarian and homogeneous conditions. The rank weight distribution of $M_2(GF(q))$ is completely determined by the general linear group $GL(2,q)$. Finally a weight function on subspace codes is analogously defined and its egalitarian property is examined.
Robust CS reconstruction based on appropriate minimization norm
Venue: arXiv cs.IT 2015
Year: 2015

Noise robust compressive sensing algorithm is considered. This algorithm allows an efficient signal reconstruction in the presence of different types of noise due to the possibility to change minimization norm. For instance, the commonly used l1 and l2 norms, provide good results in case of Laplace and Gaussian noise. However, when the signal is corrupted by Cauchy or Cubic Gaussian noise, these norms fail to provide accurate reconstruction. Therefore, in order to achieve accurate reconstruction, the application of l3 minimization norm is analyzed. The efficiency of algorithm will be demonstrated on examples.
Limitations of Algebraic Approaches to Graph Isomorphism Testing
Venue: arXiv cs.CC 2015
Year: 2015

We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Gröbner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if the graphs are isomorphic, and then to (try to) decide satisfiability of the system using, for example, the Gröbner basis algorithm. In some cases this can be done in polynomial time, in particular, if the equations admit a bounded degree refutation in an algebraic proof systems such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on the polynomial calculus degree over all fields of characteristic different from 2 and also linear lower bounds for the degree of Positivstellensatz calculus derivations. We compare this approach to recently studied linear and semidefinite programming approaches to isomorphism testing, which are known to be related to the combinatorial Weisfeiler-Lehman algorithm. We exactly characterise the power of the Weisfeiler-Lehman algorithm in terms of an algebraic proof system that lies between degree-k Nullstellensatz and degree-k polynomial calculus.
Improved Model for Wire-Length Estimation in Stochastic Wiring Distribution
Venue: arXiv cs.OH 2015
Year: 2015

This paper presents a pair of improved stochastic wiring distribution model for better estimation of on-chip wire lengths. The proposed models provide 28 - 50% reduction in error when estimating the average on-chip wire length compared to the estimation using the existing models. The impact of Rent's exponent on the average wire length estimation is also investigated to demonstrate limitations of the approximations used in some of the current models. To improve the approximations of the model a new threshold for Rent's constant is recommended. Simulation results demonstrate that proposed models with the new threshold reduce the error of estimation by 38 to 75 percent compared to the previous works.
Functorial Data Migration: From Theory to Practice
Venue: arXiv cs.DB 2015
Year: 2015

In this paper we describe a functorial data migration scenario about the manufacturing service capability of a distributed supply chain. The scenario is a category-theoretic analog of an OWL ontology-based semantic enrichment scenario developed at the National Institute of Standards and Technology (NIST). The scenario is presented using, and is included with, the open-source FQL tool, available for download at categoricaldata.net/fql.html.
Sorting Networks: The Final Countdown
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we extend the knowledge on the problem of empirically searching for sorting networks of minimal depth. We present new search space pruning techniques for the last four levels of a candidate sorting network by considering only the output set representation of a network. We present an algorithm for checking whether an $n$-input sorting network of depth $d$ exists by considering the minimal up to permutation and reflection itemsets at each level and using the pruning at the last four levels. We experimentally evaluated this algorithm to find the optimal depth sorting networks for all $n \leq 12$.
A Heat-Map-based Algorithm for Recognizing Group Activities in Videos
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, a new heat-map-based (HMB) algorithm is proposed for group activity recognition. The proposed algorithm first models human trajectories as series of "heat sources" and then applies a thermal diffusion process to create a heat map (HM) for representing the group activities. Based on this heat map, a new key-point based (KPB) method is used for handling the alignments among heat maps with different scales and rotations. And a surface-fitting (SF) method is also proposed for recognizing group activities. Our proposed HM feature can efficiently embed the temporal motion information of the group activities while the proposed KPB and SF methods can effectively utilize the characteristics of the heat map for activity recognition. Experimental results demonstrate the effectiveness of our proposed algorithms.
Intra-and-Inter-Constraint-based Video Enhancement based on Piecewise Tone Mapping
Venue: arXiv cs.CV 2015
Year: 2015

Video enhancement plays an important role in various video applications. In this paper, we propose a new intra-and-inter-constraint-based video enhancement approach aiming to 1) achieve high intra-frame quality of the entire picture where multiple region-of-interests (ROIs) can be adaptively and simultaneously enhanced, and 2) guarantee the inter-frame quality consistencies among video frames. We first analyze features from different ROIs and create a piecewise tone mapping curve for the entire frame such that the intra-frame quality of a frame can be enhanced. We further introduce new inter-frame constraints to improve the temporal quality consistency. Experimental results show that the proposed algorithm obviously outperforms the state-of-the-art algorithms.
Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors
Venue: arXiv cs.NE 2015
Year: 2015

We study the expressive power of positive neural networks. The model uses positive connection weights and multiple input neurons. Different behaviors can be expressed by varying the connection weights. We show that in discrete time, and in absence of noise, the class of positive neural networks captures the so-called monotone-regular behaviors, that are based on regular languages. A finer picture emerges if one takes into account the delay by which a monotone-regular behavior is implemented. Each monotone-regular behavior can be implemented by a positive neural network with a delay of one time unit. Some monotone-regular behaviors can be implemented with zero delay. And, interestingly, some simple monotone-regular behaviors can not be implemented with zero delay.
Reinforcement Learning in a Neurally Controlled Robot Using Dopamine Modulated STDP
Venue: arXiv cs.NE 2015
Year: 2015

Recent work has shown that dopamine-modulated STDP can solve many of the issues associated with reinforcement learning, such as the distal reward problem. Spiking neural networks provide a useful technique in implementing reinforcement learning in an embodied context as they can deal with continuous parameter spaces and as such are better at generalizing the correct behaviour to perform in a given context. In this project we implement a version of DA-modulated STDP in an embodied robot on a food foraging task. Through simulated dopaminergic neurons we show how the robot is able to learn a sequence of behaviours in order to achieve a food reward. In tests the robot was able to learn food-attraction behaviour, and subsequently unlearn this behaviour when the environment changed, in all 50 trials. Moreover we show that the robot is able to operate in an environment whereby the optimal behaviour changes rapidly and so the agent must constantly relearn. In a more complex environment, consisting of food-containers, the robot was able to learn food-container attraction in 95% of trials, despite the large temporal distance between the correct behaviour and the reward. This is achieved by shifting the dopamine response from the primary stimulus (food) to the secondary stimulus (food-container). Our work provides insights into the reasons behind some observed biological phenomena, such as the bursting behaviour observed in dopaminergic neurons. As well as demonstrating how spiking neural network controlled robots are able to solve a range of reinforcement learning tasks.
New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects
Venue: arXiv cs.CG 2015
Year: 2015

For $\cal C$ a collection of $n$ objects in $R^d$, let the packing and piercing numbers of $\cal C$, denoted by $Pack({\cal C})$, and $Pierce({\cal C})$, respectively, be the largest number of pairwise disjoint objects in ${\cal C}$, and the smallest number of points in $R^d$ that are common to all elements of ${\cal C}$, respectively. When elements of $\cal C$ are fat objects of arbitrary sizes, we derive sub-exponential time algorithms for the NP-hard problems of computing ${Pack}({\cal C})$ and $Pierce({\cal C})$, respectively, that run in $n^{O_d({{Pack}({\cal C})}^{d-1\over d})}$ and $n^{O_d({{Pierce}({\cal C})}^{d-1\over d})}$ time, respectively, and $O(n\log n)$ storage. Our main tool which is interesting in its own way, is a new separation theorem. The algorithms readily give rise to polynomial time approximation schemes (PTAS) that run in $n^{O({({1\overε})}^{d-1})}$ time and $O(n\log n)$ storage. The results favorably compare with many related best known results. Specifically, our separation theorem significantly improves the splitting ratio of the previous result of Chan, whereas, the sub-exponential time algorithms significantly improve upon the running times of very recent algorithms of Fox and Pach for packing of spheres.
Boosting of Image Denoising Algorithms
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we propose a generic recursive algorithm for improving image denoising methods. Given the initial denoised image, we suggest repeating the following "SOS" procedure: (i) (S)trengthen the signal by adding the previous denoised image to the degraded input image, (ii) (O)perate the denoising method on the strengthened image, and (iii) (S)ubtract the previous denoised image from the restored signal-strengthened outcome. The convergence of this process is studied for the K-SVD image denoising and related algorithms. Still in the context of K-SVD image denoising, we introduce an interesting interpretation of the SOS algorithm as a technique for closing the gap between the local patch-modeling and the global restoration task, thereby leading to improved performance. In a quest for the theoretical origin of the SOS algorithm, we provide a graph-based interpretation of our method, where the SOS recursive update effectively minimizes a penalty function that aims to denoise the image, while being regularized by the graph Laplacian. We demonstrate the SOS boosting algorithm for several leading denoising methods (K-SVD, NLM, BM3D, and EPLL), showing tendency to further improve denoising performance.
StarL: Towards a Unified Framework for Programming, Simulating and Verifying Distributed Robotic Systems
Venue: arXiv cs.PL 2015
Year: 2015

We developed StarL as a framework for programming, simulating, and verifying distributed systems that interacts with physical processes. StarL framework has (a) a collection of distributed primitives for coordination, such as mutual exclusion, registration and geocast that can be used to build sophisticated applications, (b) theory libraries for verifying StarL applications in the PVS theorem prover, and (c) an execution environment that can be used to deploy the applications on hardware or to execute them in a discrete event simulator. The primitives have (i) abstract, nondeterministic specifications in terms of invariants, and assume-guarantee style progress properties, (ii) implementations in Java/Android that always satisfy the invariants and attempt progress using best effort strategies. The PVS theories specify the invariant and progress properties of the primitives, and have to be appropriately instantiated and composed with the application's state machine to prove properties about the application. We have built two execution environments: one for deploying applications on Android/iRobot Create platform and a second one for simulating large instantiations of the applications in a discrete even simulator. The capabilities are illustrated with a StarL application for vehicle to vehicle coordination in a automatic intersection that uses primitives for point-to-point motion, mutual exclusion, and registration.
A Sound and Complete Axiomatization of Majority-n Logic
Venue: arXiv cs.LO 2015
Year: 2015

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional logic systems. Also, the Boolean satisfiability problem finds new solving approaches when described in terms of majority decisions. To support computer logic applications based on majority a sound and complete set of axioms is required. Most of the recent advances in majority logic deal only with ternary majority (MAJ- 3) operators because the axiomatization with solely MAJ-3 and complementation operators is well understood. However, it is of interest extending such axiomatization to n-ary majority operators (MAJ-n) from both the theoretical and practical perspective. In this work, we address this issue by introducing a sound and complete axiomatization of MAJ-n logic. Our axiomatization naturally includes existing majority logic systems. Based on this general set of axioms, computer applications can now fully exploit the expressive power of majority logic.
Mutually Testing Processes
Venue: arXiv cs.LO 2015
Year: 2015

In the standard testing theory of DeNicola-Hennessy one process is considered to be a refinement of another if every test guaranteed by the former is also guaranteed by the latter. In the domain of web services this has been recast, with processes viewed as servers and tests as clients. In this way the standard refinement preorder between servers is determined by their ability to satisfy clients. But in this setting there is also a natural refinement preorder between clients, determined by their ability to be satisfied by servers. In more general settings where there is no distinction between clients and servers, but all processes are peers, there is a further refinement preorder based on the mutual satisfaction of peers. We give a uniform account of these three preorders. In particular we give two characterisations. The first is behavioural, in terms of traces and ready sets. The second, for finite processes, is equational.
Tight Bounds for Symmetric Divergence Measures and a New Inequality Relating $f$-Divergences
Venue: arXiv cs.IT 2015
Year: 2015

Tight bounds for several symmetric divergence measures are introduced, given in terms of the total variation distance. Each of these bounds is attained by a pair of 2 or 3-element probability distributions. An application of these bounds for lossless source coding is provided, refining and improving a certain bound by Csiszár. A new inequality relating $f$-divergences is derived, and its use is exemplified. The last section of this conference paper is not included in the recent journal paper that was published in the February 2015 issue of the IEEE Trans. on Information Theory (see arXiv:1403.7164), as well as some new paragraphs throughout the paper which are linked to new references.
From Seed AI to Technological Singularity via Recursively Self-Improving Software
Venue: arXiv cs.AI 2015
Year: 2015

Software capable of improving itself has been a dream of computer scientists since the inception of the field. In this work we provide definitions for Recursively Self-Improving software, survey different types of self-improving software, review the relevant literature, analyze limits on computation restricting recursive self-improvement and introduce RSI Convergence Theory which aims to predict general behavior of RSI systems. Finally, we address security implications from self-improving intelligent software.
An Empirical Study of Mobile Ad Targeting
Venue: arXiv cs.CR 2015
Year: 2015

Advertising, long the financial mainstay of the web ecosystem, has become nearly ubiquitous in the world of mobile apps. While ad targeting on the web is fairly well understood, mobile ad targeting is much less studied. In this paper, we use empirical methods to collect a database of over 225,000 ads on 32 simulated devices hosting one of three distinct user profiles. We then analyze how the ads are targeted by correlating ads to potential targeting profiles using Bayes' rule and Pearson's chi squared test. This enables us to measure the prevalence of different forms of targeting. We find that nearly all ads show the effects of application- and time-based targeting, while we are able to identify location-based targeting in 43% of the ads and user-based targeting in 39%.
Distributed Spectrum Access for Cognitive Small Cell Networks: A Robust Graphical Game Approach
Venue: arXiv cs.IT 2015
Year: 2015

This letter investigates the problem of distributed spectrum access for cognitive small cell networks. Compared with existing work, two inherent features are considered: i) the transmission of a cognitive small cell base station only interferes with its neighbors due to the low power, i.e., the interference is local, and ii) the channel state is time-varying due to fading. We formulate the problem as a robust graphical game, and prove that it is an ordinal potential game which has at least one pure strategy Nash equilibrium (NE). Also, the lower throughput bound of NE solutions is analytically obtained. To cope with the dynamic and incomplete information constraints, we propose a distribute spectrum access algorithm to converge to some stable results. Simulation results validate the effectiveness of the proposed game-theoretic distributed learning solution in time-varying spectrum environment.
Sequential Aggregate Signatures with Short Public Keys without Random Oracles
Venue: arXiv cs.CR 2015
Year: 2015

The notion of aggregate signature has been motivated by applications and it enables any user to compress different signatures signed by different signers on different messages into a short signature. Sequential aggregate signature, in turn, is a special kind of aggregate signature that only allows a signer to add his signature into an aggregate signature in sequential order. This latter scheme has applications in diversified settings such as in reducing bandwidth of certificate chains and in secure routing protocols. Lu, Ostrovsky, Sahai, Shacham, and Waters (EUROCRYPT 2006) presented the first sequential aggregate signature scheme in the standard model. The size of their public key, however, is quite large (i.e., the number of group elements is proportional to the security parameter), and therefore, they suggested as an open problem the construction of such a scheme with short keys. In this paper, we propose the first sequential aggregate signature schemes with short public keys (i.e., a constant number of group elements) in prime order (asymmetric) bilinear groups that are secure under static assumptions in the standard model. Furthermore, our schemes employ a constant number of pairing operations per message signing and message verification operation. Technically, we start with a public-key signature scheme based on the recent dual system encryption technique of Lewko and Waters (TCC 2010). This technique cannot directly provide an aggregate signature scheme since, as we observed, additional elements should be published in a public key to support aggregation. Thus, our constructions are careful augmentation techniques for the dual system technique to allow it to support sequential aggregate signature schemes. We also propose a multi-signature scheme with short public parameters in the standard model.
Discrete Wavelet Transform and Gradient Difference based approach for text localization in videos
Venue: arXiv cs.CV 2015
Year: 2015

The text detection and localization is important for video analysis and understanding. The scene text in video contains semantic information and thus can contribute significantly to video retrieval and understanding. However, most of the approaches detect scene text in still images or single video frame. Videos differ from images in temporal redundancy. This paper proposes a novel hybrid method to robustly localize the texts in natural scene images and videos based on fusion of discrete wavelet transform and gradient difference. A set of rules and geometric properties have been devised to localize the actual text regions. Then, morphological operation is performed to generate the text regions and finally the connected component analysis is employed to localize the text in a video frame. The experimental results obtained on publicly available standard ICDAR 2003 and Hua dataset illustrate that the proposed method can accurately detect and localize texts of various sizes, fonts and colors. The experimentation on huge collection of video databases reveal the suitability of the proposed method to video databases.
Convergence Analysis using the Edge Laplacian: Robust Consensus of Nonlinear Multi-agent Systems via ISS Method
Venue: arXiv cs.SY 2015
Year: 2015

This study develops an original and innovative matrix representation with respect to the information flow for networked multi-agent system. To begin with, the general concepts of the edge Laplacian of digraph are proposed with its algebraic properties. Benefit from this novel graph-theoretic tool, we can build a bridge between the consensus problem and the edge agreement problem; we also show that the edge Laplacian sheds a new light on solving the leaderless consensus problem. Based on the edge agreement framework, the technical challenges caused by unknown but bounded disturbances and inherently nonlinear dynamics can be well handled. In particular, we design an integrated procedure for a new robust consensus protocol that is based on a blend of algebraic graph theory and the newly developed cyclic-small-gain theorem. Besides, to highlight the intricate relationship between the original graph and cyclic-small-gain theorem, the concept of edge-interconnection graph is introduced for the first time. Finally, simulation results are provided to verify the theoretical analysis.