OpenRaiser/Intern-Atlas huggingface dataset:
Vertex Fault Tolerant Additive Spanners
Venue: arXiv cs.DS 2014
Year: 2014

A {\em fault-tolerant} structure for a network is required to continue functioning following the failure of some of the network's edges or vertices. In this paper, we address the problem of designing a {\em fault-tolerant} additive spanner, namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of a single vertex, the surviving part of $H$ still contains an \emph{additive} spanner for (the surviving part of) $G$, satisfying $dist(s,t,H\setminus \{v\}) \leq dist(s,t,G\setminus \{v\})+β$ for every $s,t,v \in V$. Recently, the problem of constructing fault-tolerant additive spanners resilient to the failure of up to $f$ \emph{edges} has been considered by Braunschvig et. al. The problem of handling \emph{vertex} failures was left open therein. In this paper we develop new techniques for constructing additive FT-spanners overcoming the failure of a single vertex in the graph. Our first result is an FT-spanner with additive stretch $2$ and $\widetilde{O}(n^{5/3})$ edges. Our second result is an FT-spanner with additive stretch $6$ and $\widetilde{O}(n^{3/2})$ edges. The construction algorithm consists of two main components: (a) constructing an FT-clustering graph and (b) applying a modified path-buying procedure suitably adopted to failure prone settings. Finally, we also describe two constructions for {\em fault-tolerant multi-source additive spanners}, aiming to guarantee a bounded additive stretch following a vertex failure, for every pair of vertices in $S \times V$ for a given subset of sources $S\subseteq V$. The additive stretch bounds of our constructions are 4 and 8 (using a different number of edges).
Quantized CSI-Based Tomlinson-Harashima Precoding in Multiuser MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers the implementation of Tomlinson-Harashima (TH) precoding for multiuser MIMO systems based on quantized channel state information (CSI) at the transmitter side. Compared with the results in [1], our scheme applies to more general system setting where the number of users in the system can be less than or equal to the number of transmit antennas. We also study the achievable average sum rate of the proposed quantized CSI-based TH precoding scheme. The expressions of the upper bounds on both the average sum rate of the systems with quantized CSI and the mean loss in average sum rate due to CSI quantization are derived. We also present some numerical results. The results show that the nonlinear TH precoding can achieve much better performance than that of linear zero-forcing precoding for both perfect CSI and quantized CSI cases. In addition, our derived upper bound on the mean rate loss for TH precoding converges to the true rate loss faster than that of zeroforcing precoding obtained in [2] as the number of feedback bits becomes large. Both the analytical and numerical results show that nonlinear precoding suffers from imperfect CSI more than linear precoding does.
Tomlinson-Harashima Precoding for Multiuser MIMO Systems with Quantized CSI Feedback and User Scheduling
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the sum rate performance of a low complexity quantized CSI-based Tomlinson-Harashima (TH) precoding scheme for downlink multiuser MIMO tansmission, employing greedy user selection. The asymptotic distribution of the output signal to interference plus noise ratio of each selected user and the asymptotic sum rate as the number of users K grows large are derived by using extreme value theory. For fixed finite signal to noise ratios and a finite number of transmit antennas $n_T$, we prove that as K grows large, the proposed approach can achieve the optimal sum rate scaling of the MIMO broadcast channel. We also prove that, if we ignore the precoding loss, the average sum rate of this approach converges to the average sum capacity of the MIMO broadcast channel. Our results provide insights into the effect of multiuser interference caused by quantized CSI on the multiuser diversity gain.
ITEM: Immersive Telepresence for Entertainment and Meetings - A Practical Approach
Venue: arXiv cs.MM 2014
Year: 2014

This paper presents an Immersive Telepresence system for Entertainment and Meetings (ITEM). The system aims to provide a radically new video communication experience by seamlessly merging participants into the same virtual space to allow a natural interaction among them and shared collaborative contents. With the goal to make a scalable, flexible system for various business solutions as well as easily accessible by massive consumers, we address the challenges in the whole pipeline of media processing, communication, and displaying in our design and realization of such a system. Particularly, in this paper we focus on the system aspects that maximize the end-user experience, optimize the system and network resources, and enable various teleimmersive application scenarios. In addition, we also present a few key technologies, i.e. fast object-based video coding for real world data and spatialized audio capture and 3D sound localization for group teleconferencing. Our effort is to investigate and optimize the key system components and provide an efficient end-to-end optimization and integration by considering user needs and preferences. Extensive experiments show the developed system runs reliably and comfortably in real time with a minimal setup requirement (e.g. a webcam and/or a depth camera, an optional microphone array, a laptop/desktop connected to the public Internet) for teleimmersive communication. With such a really minimal deployment requirement, we present a variety of interesting applications and user experiences created by ITEM.
A Dual-Engine for Early Analysis of Critical Systems
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents a framework for modeling, simulating, and checking properties of critical systems based on the Alloy language -- a declarative, first-order, relational logic with a built-in transitive closure operator. The paper introduces a new dual-analysis engine that is capable of providing both counterexamples and proofs. Counterexamples are found fully automatically using an SMT solver, which provides a better support for numerical expressions than the existing Alloy Analyzer. Proofs, however, cannot always be found automatically since the Alloy language is undecidable. Our engine offers an economical approach by first trying to prove properties using a fully-automatic, SMT-based analysis, and switches to an interactive theorem prover only if the first attempt fails. This paper also reports on applying our framework to Microsoft's COM standard and the mark-and-sweep garbage collection algorithm.
A Trust-based Pollution Attack Prevention Scheme in Peer-to-Peer Streaming Networks
Venue: arXiv cs.NI 2014
Year: 2014

Nowadays, peer-to-peer (P2P) streaming systems have become a popular way to deliver multimedia content over the internet due to their low bandwidth requirement, high video streaming quality, and flexibility. However, P2P streaming systems are vulnerable to various attacks, especially pollution attacks, due to their distributed and dynamically changing infrastructure. In this paper, by exploring the features of various pollution attacks, we propose a trust management system tailored for P2P streaming systems. Both direct trust and indirect trust are taken into consideration when designing the trust management system. A new direct trust model is proposed. A dynamic confidence factor that can dynamically adjust the weight of direct and indirect trust in computing the trust is also proposed and studied. A novel double-threshold trust utilization scheme is given. It is shown that the proposed trust management system is effective in identifying polluters and preventing them from further sharing of polluted data chunks.
Advanced reversible Data Hiding With Encrypted Data
Venue: arXiv cs.CR 2014
Year: 2014

The advanced RDH work focuses on both data encryption and image encryption which makes it more secure and free of errors. All previous methods embed data without encrypting the data which may subject to errors on the data extraction or image recovery. The proposed work provides a novel RDH scheme in which both data and image can be encrypted and extracted reversibly without any errors. In the proposed work, data extraction and image recovery are free of any errors. The PSNR is significantly improved in the proposed work. This advanced work also performs data hiding in videos.
EF+EX Forest Algebras
Venue: arXiv cs.LO 2014
Year: 2014

We examine languages of unranked forests definable using the temporal operators EF and EX. We characterize the languages definable in this logic, and various fragments thereof, using the syntactic forest algebras introduced by Bojanczyk and Walukiewicz. Our algebraic characterizations yield efficient algorithms for deciding when a given language of forests is definable in this logic. The proofs are based on understanding the wreath product closures of a few small algebras, for which we introduce a general ideal theory for forest algebras. This combines ideas from the work of Bojanczyk and Walukiewicz for the analogous logics on binary trees and from early work of Stiffler on wreath product of finite semigroups.
ActiveMonitor: Non-blocking Monitor Executions for Increased Parallelism
Venue: arXiv cs.DC 2014
Year: 2014

We present a set of novel ideas on design and implementation of monitor objects for multi-threaded programs. Our approach has two main goals: (a) increase parallelism in monitor objects and thus provide performance gains (shorter runtimes) for multi-threaded programs, and (b) introduce constructs that allow programmers to easily write monitor-based multi-threaded programs that can achieve these performance gains. We describe the concepts of our framework, called ActiveMonitor, and its prototype implementation using futures. We evaluate its performance in terms of runtimes of multi-threaded programs on linked-list, bounded-buffer, and other fundamental problems implemented in Java. We compare the runtimes of our implementation against implementations using Java's reentrant locks, recently proposed automatic signaling framework AutoSynch, and some other techniques from the literature. The results of of the evaluation indicate that monitors based on our framework provide significant gains in runtime performance in comparison to traditional monitors implemented using Java's reentrant locks.
Optimization of Signal-to-Noise-and-Distortion Ratio for Dynamic Range Limited Nonlinearities
Venue: arXiv cs.IT 2014
Year: 2014

Many components used in signal processing and communication applications, such as power amplifiers and analog-to-digital converters, are nonlinear and have a finite dynamic range. The nonlinearity associated with these devices distorts the input, which can degrade the overall system performance. Signal-to-noise-and-distortion ratio (SNDR) is a common metric to quantify the performance degradation. One way to mitigate nonlinear distortions is by maximizing the SNDR. In this paper, we analyze how to maximize the SNDR of the nonlinearities in optical wireless communication (OWC) systems. Specifically, we answer the question of how to optimally predistort a double-sided memory-less nonlinearity that has both a "turn-on" value and a maximum "saturation" value. We show that the SNDR-maximizing response given the constraints is a double-sided limiter with a certain linear gain and a certain bias value. Both the gain and the bias are functions of the probability density function (PDF) of the input signal and the noise power. We also find a lower bound of the nonlinear system capacity, which is given by the SDNR and an upper bound determined by dynamic signal-to-noise ratio (DSNR). An application of the results herein is to design predistortion linearization of nonlinear devices like light emitting diodes (LEDs).
Dynamic Nested Clustering for Parallel PHY-Layer Processing in Cloud-RANs
Venue: arXiv cs.IT 2014
Year: 2014

Featured by centralized processing and cloud based infrastructure, Cloud Radio Access Network (C-RAN) is a promising solution to achieve an unprecedented system capacity in future wireless cellular networks. The huge capacity gain mainly comes from the centralized and coordinated signal processing at the cloud server. However, full-scale coordination in a large-scale C-RAN requires the processing of very large channel matrices, leading to high computational complexity and channel estimation overhead. To resolve this challenge, we exploit the near-sparsity of large C-RAN channel matrices, and derive a unified theoretical framework for clustering and parallel processing. Based on the framework, we propose a dynamic nested clustering (DNC) algorithm that not only greatly improves the system scalability in terms of baseband-processing and channel-estimation complexity, but also is amenable to various parallel processing strategies for different data center architectures. With the proposed algorithm, we show that the computation time for the optimal linear detector is greatly reduced from $O(N^3)$ to no higher than $O(N^{\frac{42}{23}})$, where $N$ is the number of RRHs in C-RAN.
Computing With Contextual Numbers
Venue: arXiv cs.CE 2014
Year: 2014

Self Organizing Map (SOM) has been applied into several classical modeling tasks including clustering, classification, function approximation and visualization of high dimensional spaces. The final products of a trained SOM are a set of ordered (low dimensional) indices and their associated high dimensional weight vectors. While in the above-mentioned applications, the final high dimensional weight vectors play the primary role in the computational steps, from a certain perspective, one can interpret SOM as a nonparametric encoder, in which the final low dimensional indices of the trained SOM are pointer to the high dimensional space. We showed how using a one-dimensional SOM, which is not common in usual applications of SOM, one can develop a nonparametric mapping from a high dimensional space to a continuous one-dimensional numerical field. These numerical values, called contextual numbers, are ordered in a way that in a given context, similar numbers refer to similar high dimensional states. Further, as these numbers can be treated similarly to usual continuous numbers, they can be replaced with their corresponding high dimensional states within any data driven modeling problem. As a potential application, we showed how using contextual numbers could be used for the problem of high dimensional spatiotemporal dynamics.
Text to Multi-level MindMaps: A Novel Method for Hierarchical Visual Abstraction of Natural Language Text
Venue: arXiv cs.CL 2014
Year: 2014

MindMapping is a well-known technique used in note taking, which encourages learning and studying. MindMapping has been manually adopted to help present knowledge and concepts in a visual form. Unfortunately, there is no reliable automated approach to generate MindMaps from Natural Language text. This work firstly introduces MindMap Multilevel Visualization concept which is to jointly visualize and summarize textual information. The visualization is achieved pictorially across multiple levels using semantic information (i.e. ontology), while the summarization is achieved by the information in the highest levels as they represent abstract information in the text. This work also presents the first automated approach that takes a text input and generates a MindMap visualization out of it. The approach could visualize text documents in multilevel MindMaps, in which a high-level MindMap node could be expanded into child MindMaps. \ignore{ As far as we know, this is the first work that view MindMapping as a new approach to jointly summarize and visualize textual information.} The proposed method involves understanding of the input text and converting it into intermediate Detailed Meaning Representation (DMR). The DMR is then visualized with two modes; Single level or Multiple levels, which is convenient for larger text. The generated MindMaps from both approaches were evaluated based on Human Subject experiments performed on Amazon Mechanical Turk with various parameter settings.
SADDLE: A Modular Design Automation Framework for Cluster Supercomputers and Data Centres
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we present SADDLE, a modular framework for automated design of cluster supercomputers and data centres. In contrast with commonly used approaches that operate on logic gate level (Verilog, VHDL) or board level (such as EDA tools), SADDLE works at a much higher level of abstraction: its building blocks are ready-made servers, network switches, power supply systems and so on. Modular approach provides the potential to include low-level tools as elements of SADDLE's design workflow, moving towards the goal of electronic system level (ESL) design automation. Designs produced by SADDLE include project documentation items such as bills of materials and wiring diagrams, providing a formal specification of a computer system and streamlining assembly operations.
Early Development of UVM based Verification Environment of Image Signal Processing Designs using TLM Reference Model of RTL
Venue: arXiv cs.SE 2014
Year: 2014

With semiconductor industry trend of smaller the better, from an idea to a final product, more innovation on product portfolio and yet remaining competitive and profitable are few criteria which are culminating into pressure and need for more and more innovation for CAD flow, process management and project execution cycle. Project schedules are very tight and to achieve first silicon success is key for projects. This necessitates quicker verification with better coverage matrix. Quicker Verification requires early development of the verification environment with wider test vectors without waiting for RTL to be available. In this paper, we are presenting a novel approach of early development of reusable multi-language verification flow, by addressing four major activities of verification like Early creation of Executable Specification, Early creation of Verification Environment, Early development of test vectors and Better and increased Re-use of blocks. Although this paper focuses on early development of UVM based Verification Environment of Image Signal Processing designs using TLM Reference Model of RTL, same concept can be extended for non-image signal processing designs. Main Keywords are SystemVerilog, SystemC, Transaction Level Modeling, Universal Verification Methodology (UVM), Processor model, Universal Verification Component (UVC), Reference Model.
A class of hopping patterns with minimal collisions
Venue: arXiv cs.IT 2014
Year: 2014

In \cite{VTC} three metrics for hopping pattern performance evaluation is proposed: column period, maximal collision ratio, maximal continual collision number, a lower bound of maximal continual collision number is given also. In this paper we give a lower bound of maximal collision ratio, a class of hopping pattern whose both maximal collision ratio and maximal continual collision number fit the lower bounds is constructed also.
Efficient Interpolation-Based Decoding of Interleaved Subspace and Gabidulin Codes
Venue: arXiv cs.IT 2014
Year: 2014

An interpolation-based decoding scheme for interleaved subspace codes is presented. The scheme can be used as a (not necessarily polynomial-time) list decoder as well as a probabilistic unique decoder. Both interpretations allow to decode interleaved subspace codes beyond half the minimum subspace distance. Further, an efficient interpolation procedure for the required linearized multivariate polynomials is presented and a computationally- and memory-efficient root-finding algorithm for the probabilistic unique decoder is proposed. These two efficient algorithms can also be applied for accelerating the decoding of interleaved Gabidulin codes.
Mobile Device Identification via Sensor Fingerprinting
Venue: arXiv cs.CR 2014
Year: 2014

We demonstrate how the multitude of sensors on a smartphone can be used to construct a reliable hardware fingerprint of the phone. Such a fingerprint can be used to de-anonymize mobile devices as they connect to web sites, and as a second factor in identifying legitimate users to a remote server. We present two implementations: one based on analyzing the frequency response of the speakerphone-microphone system, and another based on analyzing device-specific accelerometer calibration errors. Our accelerometer-based fingerprint is especially interesting because the accelerometer is accessible via JavaScript running in a mobile web browser without requesting any permissions or notifying the user. We present the results of the most extensive sensor fingerprinting experiment done to date, which measured sensor properties from over 10,000 mobile devices. We show that the entropy from sensor fingerprinting is sufficient to uniquely identify a device among thousands of devices, with low probability of collision.
The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
Venue: arXiv cs.CG 2014
Year: 2014

Many well-known graph drawing techniques, including force directed drawings, spectral graph layouts, multidimensional scaling, and circle packings, have algebraic formulations. However, practical methods for producing such drawings ubiquitously use iterative numerical approximations rather than constructing and then solving algebraic expressions representing their exact solutions. To explain this phenomenon, we use Galois theory to show that many variants of these problems have solutions that cannot be expressed by nested radicals or nested roots of low-degree polynomials. Hence, such solutions cannot be computed exactly even in extended computational models that include such operations.
Performance Analysis and Location Optimization for Massive MIMO Systems with Circularly Distributed Antennas
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we analyze the achievable rate of the uplink of a single-cell multi-user distributed massive multiple-input-multiple-output (MIMO) system. The multiple users are equipped with single antenna and the base station (BS) is equipped with a large number of distributed antennas. We derive an analytical expression for the asymptotic ergodic achievable rate of the system under zero-forcing (ZF) detector. In particular, we consider circular antenna array, where the distributed BS antennas are located evenly on a circle, and derive an analytical expression and closed-form tight bounds for the achievable rate of an arbitrarily located user. Subsequently, closed-form bounds on the average achievable rate per user are obtained under the assumption that the users are uniformly located in the cell. Based on the bounds, we can understand the behavior of the system rate with respect to different parameters and find the optimal location of the circular BS antenna array that maximizes the average rate. Numerical results are provided to assess our analytical results and examine the impact of the number and the location of the BS antennas, the transmit power, and the path-loss exponent on system performance. It is shown that circularly distributed massive MIMO system largely outperforms centralized massive MIMO system.