OpenRaiser/Intern-Atlas huggingface dataset:
Impact of Knowledge on Election Time in Anonymous Networks
Venue: arXiv cs.DS 2016
Year: 2016

Leader election is one of the basic problems in distributed computing. For anonymous networks, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in arbitrary anonymous networks. It is well known that leader election is impossible in some networks, regardless of the allocated amount of time, even if nodes know the map of the network. However, even in networks in which it is possible to elect a leader knowing the map, the task may be still impossible without any knowledge, regardless of the allocated time. On the other hand, for any network in which leader election is possible knowing the map, there is a minimum time, called the election index, in which this can be done. Informally, the election index of a network is the minimum depth at which views of all nodes are distinct. Our aim is to establish tradeoffs between the allocated time $τ$ and the amount of information that has to be given a priori to the nodes to enable leader election in time $τ$ in all networks for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information is provided to all nodes at the start by an oracle knowing the entire network. The length of this string (its number of bits) is called the size of advice. For a given time $τ$ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $τ$. We focus on the two sides of the time spectrum and give tight (or almost tight) bounds on the minimum size of advice for these extremes. We also show that constant advice is not sufficient for leader election in all graphs, regardless of the allocated time.
On Modular and Fully-Abstract Compilation -- Technical Appendix
Venue: arXiv cs.PL 2016
Year: 2016

Secure compilation studies compilers that generate target-level components that are as secure as their source-level counterparts. Full abstraction is the most widely-proven property when defining a secure compiler. A compiler is modular if it allows different components to be compiled independently and then to be linked together to form a whole program. Unfortunately, many existing fully-abstract compilers to untyped machine code are not modular. So, while fully-abstractly compiled components are secure from malicious attackers, if they are linked against each other the resulting component may become vulnerable to attacks. This paper studies how to devise modular, fully-abstract compilers. It first analyses the attacks arising when compiled programs are linked together, identifying security threats that are due to linking. Then, it defines a compiler from an object-based language with method calls and dynamic memory allocation to untyped assembly language extended with a memory isolation mechanism. The paper provides a proof sketch that the defined compiler is fully-abstract and modular, so its output can be linked together without introducing security violations.
From Dynamic to Static Semantics, Quantitatively
Venue: arXiv cs.LO 2016
Year: 2016

We exhibit a new relationship between dynamic and static semantics. We define the categorical outlay needed to define Interaction Graphs models, a generalisation of Girard's Geometry of Interaction models, which strongly relate to game semantics. We then show how this category is mapped to weighted relational models of linear logic. This brings into vision a new bridge between the dynamic and static approaches, and provides formal grounds for considering interaction graphs models as quantitative versions of GoI and game semantics models. We finally proceed to show how the interaction graphs models relate to a very general notion of quantitative coherence spaces.
Balancing Data Security and Blocking Performance with Spectrum Randomization in Optical Networks
Venue: arXiv cs.NI 2016
Year: 2016

Data randomization or scrambling has been effectively used in various applications to improve the data security. In this paper, we use the idea of data randomization to proactively randomize the spectrum (re)allocation to improve connections' security. As it is well-known that random (re)allocation fragments the spectrum and thus increases blocking in elastic optical networks, we analyze the tradeoff between system performance and security. To this end, in addition to spectrum randomization, we utilize an on-demand defragmentation scheme every time a request is blocked due to the spectrum fragmentation. We model the occupancy pattern of an elastic optical link (EOL) using a multi-class continuous-time Markov chain (CTMC) under the random-fit spectrum allocation method. Numerical results show that although both the blocking and security can be improved for a particular so-called randomization process (RP) arrival rate, while with the increase in RP arrival rate the connections' security improves at the cost of the increase in overall blocking.
Frequency-Domain Response Based Timing Synchronization: A Near Optimal Sampling Phase Criterion for TDS-OFDM
Venue: arXiv cs.IT 2016
Year: 2016

In time-domain synchronous OFDM (TDS-OFDM) system for digital television terrestrial multimedia broadcasting (DTMB) standard, the baseband OFDM signal is upsampled and shaping filtered by square root raised cosine (SRRC) filter before digital-to-analog converter (DAC). Much of the work in the area of timing synchronization for TDS-OFDM focuses on frame synchronization and sampling clock frequency offset recovery, which does not consider the sampling clock phase offset due to the upsampling and SRRC filter. This paper evaluates the bit-error-rate (BER) effect of sampling clock phase offset in TDS-OFDM system. First, we provide the BER for M-order quadrature amplitude modulation (M-QAM) in uncoded TDS-OFDM system. Second, under the condition of the optimal BER criterion and additive white Gaussian noise (AWGN) channel, we propose a near optimal sampling phase estimation criterion based on frequency-domain response. Simulations demonstrate that the proposed criterion also has good performance in actual TDS-OFDM system with channel coding over multipath channels, and it is superior to the conventional symbol timing recovery methods for TDS-OFDM system.
QoS Constrained Power Minimization in the Multiple Stream MIMO Broadcast Channel
Venue: arXiv cs.IT 2016
Year: 2016

This work addresses the design of optimal linear transmit filters for the Multiple Input-Multiple Output (MIMO) Broadcast Channel (BC) when several spatial streams are allocated to each user.We also consider that the Channel State Information (CSI) is perfect at the receivers but is only partial at the transmitter. A statistical model for the partial CSI is assumed and exploited for the filter design. Similarly to the single-stream per user case, the problem is solved via Mean Square Error (MSE) dualities and interference functions. However, including more streams per user involves an additional complexity level since we must determine how to distribute the per-user rates among the streams. Such problem is solved using a projected gradient algorithm.
An Approximation Algorithm for a Shortest Dubins Path Problem
Venue: arXiv cs.RO 2016
Year: 2016

The problem of finding the shortest path for a vehicle visiting a given sequence of target points subject to the motion constraints of the vehicle is an important problem that arises in several monitoring and surveillance applications involving unmanned aerial vehicles. There is currently no algorithm that can find an optimal solution to this problem. Therefore, heuristics that can find approximate solutions with guarantees on the quality of the solutions are useful. The best approximation algorithm currently available for the case when the distance between any two adjacent target points in the sequence is at least equal to twice the minimum radius of the vehicle has a guarantee of 3.04. This article provides a new approximation algorithm which improves this guarantee to 2.04. The developed algorithm is also implemented for hundreds of typical instances involving at most 30 points to corroborate the performance of the proposed approach.
Annual Journal citation indices: a comparative study
Venue: arXiv cs.DL 2016
Year: 2016

We study the statistics of citations made to the indexed Science journals in the Journal Citation Reports during the period 2004-2013 using different measures. We consider different measures which quantify the impact of the journals. To our surprise, we find that the apparently uncorrelated measures, even when defined in an arbitrary manner, show strong correlations. This is checked over all the years considered. Impact factor being one of these measures, the present work raises the question whether it is actually a nearly perfect index as claimed often. In addition we study the distributions of the different indices which also behave similarly.
Pixel-level Encoding and Depth Layering for Instance-level Semantic Labeling
Venue: arXiv cs.CV 2016
Year: 2016

Recent approaches for instance-aware semantic labeling have augmented convolutional neural networks (CNNs) with complex multi-task architectures or computationally expensive graphical models. We present a method that leverages a fully convolutional network (FCN) to predict semantic labels, depth and an instance-based encoding using each pixel's direction towards its corresponding instance center. Subsequently, we apply low-level computer vision techniques to generate state-of-the-art instance segmentation on the street scene datasets KITTI and Cityscapes. Our approach outperforms existing works by a large margin and can additionally predict absolute distances of individual instances from a monocular image as well as a pixel-level semantic labeling.
Finite-length scaling based on belief propagation for spatially coupled LDPC codes
Venue: arXiv cs.IT 2016
Year: 2016

The equivalence of peeling decoding (PD) and Belief Propagation (BP) for low-density parity-check (LDPC) codes over the binary erasure channel is analyzed. Modifying the scheduling for PD, it is shown that exactly the same variable nodes (VNs) are resolved in every iteration than with BP. The decrease of erased VNs during the decoding process is analyzed instead of resolvable equations. This quantity can also be derived with density evolution, resulting in a drastic decrease in complexity. Finally, a scaling law using this quantity is established for spatially coupled LDPC codes.
Locally Imposing Function for Generalized Constraint Neural Networks - A Study on Equality Constraints
Venue: arXiv cs.NE 2016
Year: 2016

This work is a further study on the Generalized Constraint Neural Network (GCNN) model [1], [2]. Two challenges are encountered in the study, that is, to embed any type of prior information and to select its imposing schemes. The work focuses on the second challenge and studies a new constraint imposing scheme for equality constraints. A new method called locally imposing function (LIF) is proposed to provide a local correction to the GCNN prediction function, which therefore falls within Locally Imposing Scheme (LIS). In comparison, the conventional Lagrange multiplier method is considered as Globally Imposing Scheme (GIS) because its added constraint term exhibits a global impact to its objective function. Two advantages are gained from LIS over GIS. First, LIS enables constraints to fire locally and explicitly in the domain only where they need on the prediction function. Second, constraints can be implemented within a network setting directly. We attempt to interpret several constraint methods graphically from a viewpoint of the locality principle. Numerical examples confirm the advantages of the proposed method. In solving boundary value problems with Dirichlet and Neumann constraints, the GCNN model with LIF is possible to achieve an exact satisfaction of the constraints.
Can Boosting with SVM as Week Learners Help?
Venue: arXiv cs.CV 2016
Year: 2016

Object recognition in images involves identifying objects with partial occlusions, viewpoint changes, varying illumination, cluttered backgrounds. Recent work in object recognition uses machine learning techniques SVM-KNN, Local Ensemble Kernel Learning, Multiple Kernel Learning. In this paper, we want to utilize SVM as week learners in AdaBoost. Experiments are done with classifiers like near- est neighbor, k-nearest neighbor, Support vector machines, Local learning(SVM- KNN) and AdaBoost. Models use Scale-Invariant descriptors and Pyramid his- togram of gradient descriptors. AdaBoost is trained with set of week classifier as SVMs, each with kernel distance function on different descriptors. Results shows AdaBoost with SVM outperform other methods for Object Categorization dataset.
Check-hybrid GLDPC Codes: Systematic Elimination of Trapping Sets and Guaranteed Error Correction Capability
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a new approach to construct a class of check-hybrid generalized low-density parity-check (CH-GLDPC) codes which are free of small trapping sets. The approach is based on converting some selected check nodes involving a trapping set into super checks corresponding to a 2-error correcting component code. Specifically, we follow two main purposes to construct the check-hybrid codes; first, based on the knowledge of the trapping sets of the global LDPC code, single parity checks are replaced by super checks to disable the trapping sets. We show that by converting specified single check nodes, denoted as critical checks, to super checks in a trapping set, the parallel bit flipping (PBF) decoder corrects the errors on a trapping set and hence eliminates the trapping set. The second purpose is to minimize the rate loss caused by replacing the super checks through finding the minimum number of such critical checks. We also present an algorithm to find critical checks in a trapping set of column-weight 3 LDPC code and then provide upper bounds on the minimum number of such critical checks such that the decoder corrects all error patterns on elementary trapping sets. Moreover, we provide a fixed set for a class of constructed check-hybrid codes. The guaranteed error correction capability of the CH-GLDPC codes is also studied. We show that a CH-GLDPC code in which each variable node is connected to 2 super checks corresponding to a 2-error correcting component code corrects up to 5 errors. The results are also extended to column-weight 4 LDPC codes. Finally, we investigate the eliminating of trapping sets of a column-weight 3 LDPC code using the Gallager B decoding algorithm and generalize the results obtained for the PBF for the Gallager B decoding algorithm.
A Novel Approach for Mining Similarity Profiled Temporal Association Patterns
Venue: arXiv cs.DB 2016
Year: 2016

The problem of frequent pattern mining from non-temporal databases is studied extensively by various researchers working in areas of data mining, temporal databases and information retrieval. However, Conventional frequent pattern algorithms are not suitable to find similar temporal association patterns from temporal databases. A Temporal database is a database which can store past, present and future information. The objective of this research is to come up with a novel approach so as to find similar temporal association patterns w.r.t user specified threshold and a given reference support time sequence using concept of Venn diagrams. For this, we maintain two types of supports called positive support and negative support values to find similar temporal association patterns of user interest. The main advantage of our method is that, it performs only a single scan of temporal database to find temporal association patterns similar to specified reference support sequence. This single database scan approach hence eliminates the huge overhead incurred when the database is scanned multiple times. The present approach also eliminates the need to compute and maintain true support values of all the subsets of temporal patterns of previous stages when computing temporal patterns of next stage.
Capacity of Cellular Networks with Femtocache
Venue: arXiv cs.IT 2016
Year: 2016

The capacity of next generation of cellular networks using femtocaches is studied when multihop communications and decentralized cache placement are considered. We show that the storage capability of future network User Terminals (UT) can be effectively used to increase the capacity in random decentralized uncoded caching. We further propose a random decentralized coded caching scheme which achieves higher capacity results than the random decentralized uncoded caching. The result shows that coded caching which is suitable for systems with limited storage capabilities can improve the capacity of cellular networks by a factor of log(n) where n is the number of nodes served by the femtocache.
Design of Dynamic Algorithms via Primal-Dual Method
Venue: arXiv cs.DS 2016
Year: 2016

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an $O(f^2)$-approximately optimal solution in $O(f \cdot \log (m+n))$ amortized update time, where $f$ is the maximum "frequency" of an element, $n$ is the number of sets, and $m$ is the maximum number of elements in the universe at any point in time. (2) For the dynamic $b$-matching problem, we maintain an $O(1)$-approximately optimal solution in $O(\log^3 n)$ amortized update time, where $n$ is the number of nodes in the graph.
Binary Multi-Level Routing Protocol for Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2016
Year: 2016

Routing in mobile ad hoc networks (MANETs) presents a big challenge, especially when support for a large number of nodes is needed. This paper extends the local visibility concept of the recent DHT-based URBAN_XOR routing protocol, which aims to reduce routing table sizes while keeping efficiency high. Our main contribution is providing a guarantee that if any two nodes are connected through other nodes, they are able to communicate with each other. We propose a new route acquisition method that aims to reduce the total amount of overhead traffic and improve convergence rate. In addition, we introduce an abstraction for describing the network structure that makes it easy to understand and analyze. Compared to existing approaches in ad hoc routing, the new protocol supports the following features: scalability, guaranteed connectivity assuming network convergence, absence of single points of failure, low path-stretch, and mobility.
Parts for the Whole: The DCT Norm for Extreme Visual Recovery
Venue: arXiv cs.CV 2016
Year: 2016

Here we study the extreme visual recovery problem, in which over 90\% of pixel values in a given image are missing. Existing low rank-based algorithms are only effective for recovering data with at most 90\% missing values. Thus, we exploit visual data's smoothness property to help solve this challenging extreme visual recovery problem. Based on the Discrete Cosine Transformation (DCT), we propose a novel DCT norm that involves all pixels and produces smooth estimations in any view. Our theoretical analysis shows that the total variation (TV) norm, which only achieves local smoothness, is a special case of the proposed DCT norm. We also develop a new visual recovery algorithm by minimizing the DCT and nuclear norms to achieve a more visually pleasing estimation. Experimental results on a benchmark image dataset demonstrate that the proposed approach is superior to state-of-the-art methods in terms of peak signal-to-noise ratio and structural similarity.
Ensemble Enabled Weighted PageRank
Venue: arXiv cs.IR 2016
Year: 2016

This paper describes our solution for WSDM Cup 2016. Ranking the query independent importance of scholarly articles is a critical and challenging task, due to the heterogeneity and dynamism of entities involved. Our approach is called Ensemble enabled Weighted PageRank (EWPR). To do this, we first propose Time-Weighted PageRank that extends PageRank by introducing a time decaying factor. We then develop an ensemble method to assemble the authorities of the heterogeneous entities involved in scholarly articles. We finally propose to use external data sources to further improve the ranking accuracy. Our experimental study shows that our EWPR is a good choice for ranking scholarly articles.
The SP theory of intelligence and the representation and processing of knowledge in the brain
Venue: arXiv cs.AI 2016
Year: 2016

The "SP theory of intelligence", with its realisation in the "SP computer model", aims to simplify and integrate observations and concepts across AI-related fields, with information compression as a unifying theme. This paper describes how abstract structures and processes in the theory may be realised in terms of neurons, their interconnections, and the transmission of signals between neurons. This part of the SP theory -- "SP-neural" -- is a tentative and partial model for the representation and processing of knowledge in the brain. In the SP theory (apart from SP-neural), all kinds of knowledge are represented with "patterns", where a pattern is an array of atomic symbols in one or two dimensions. In SP-neural, the concept of a "pattern" is realised as an array of neurons called a "pattern assembly", similar to Hebb's concept of a "cell assembly" but with important differences. Central to the processing of information in the SP system is the powerful concept of "multiple alignment", borrowed and adapted from bioinformatics. Processes such as pattern recognition, reasoning and problem solving are achieved via the building of multiple alignments, while unsupervised learning -- significantly different from the "Hebbian" kinds of learning -- is achieved by creating patterns from sensory information and also by creating patterns from multiple alignments in which there is a partial match between one pattern and another. Short-lived neural structures equivalent to multiple alignments will be created via an inter-play of excitatory and inhibitory neural signals. The paper discusses several associated issues, with relevant empirical evidence.
A Safety and Liveness Theory for Total Reversibility (Extended Abstract)
Venue: arXiv cs.LO 2016
Year: 2016

We study the theory of safety and liveness in a reversible calculus where reductions are totally ordered and rollbacks lead the systems to past states. Similar to previous work on communicating transactions, liveness and safety respectively correspond to the should-testing and inverse may-testing preorders. We develop fully abstract models for these preorders in a reversible calculus, which are based only on forward transitions, thus providing a simple proof technique for refinement of such systems. We show that with respect to safety, total reversibility is a conservative extension to CCS. With respect to liveness, however, adding total reversibility to CCS distinguishes more systems. To our knowledge, this work provides the first characterisations of safety and liveness, and the first testing theory for a reversible calculus.