OpenRaiser/Intern-Atlas huggingface dataset:
Face-Guarding Polyhedra
Venue: arXiv cs.CG 2014
Year: 2014

We study the Art Gallery Problem for face guards in polyhedral environments. The problem can be informally stated as: how many (not necessarily convex) windows should we place on the external walls of a dark building, in order to completely illuminate its interior? We consider both closed and open face guards (i.e., faces with or without their boundary), and we study several classes of polyhedra, including orthogonal polyhedra, 4-oriented polyhedra, and 2-reflex orthostacks. We give upper and lower bounds on the minimum number of faces required to guard the interior of a given polyhedron in each of these classes, in terms of the total number of its faces, f. In several cases our bounds are tight: f/6 open face guards for orthogonal polyhedra and 2-reflex orthostacks, and f/4 open face guards for 4-oriented polyhedra. Additionally, for closed face guards in 2-reflex orthostacks, we give a lower bound of (f+3)/9 and an upper bound of (f+1)/7. Then we show that it is NP-hard to approximate the minimum number of (closed or open) face guards within a factor of Omega(log f), even for polyhedra that are orthogonal and simply connected. We also obtain the same hardness results for polyhedral terrains. Along the way we discuss some applications, arguing that face guards are not a reasonable model for guards patrolling on the surface of a polyhedron.
Secrecy Transmission on Block Fading Channels: Theoretical Limits and Performance of Practical Codes
Venue: arXiv cs.IT 2014
Year: 2014

We consider a system where an agent (Alice) aims at transmitting a message to a second agent (Bob) over a set of parallel channels, while keeping it secret from a third agent (Eve) by using physical layer security techniques. We assume that Alice perfectly knows the set of channels with respect to Bob, but she has only a statistical knowledge of the channels with respect to Eve. We derive bounds on the achievable outage secrecy rates, by considering coding either within each channel or across all parallel channels. Transmit power is adapted to the channel conditions, with a constraint on the average power over the whole transmission. We also focus on the maximum cumulative outage secrecy rate that can be achieved. Moreover, in order to assess the performance in a real life scenario, we consider the use of practical error correcting codes. We extend the definitions of security gap and equivocation rate, previously applied to the single additive white Gaussian noise channel, to Rayleigh distributed parallel channels, on the basis of the error rate targets and the outage probability. Bounds on these metrics are also derived, taking into account the statistics of the parallel channels. Numerical results are provided, that confirm the feasibility of the considered physical layer security techniques.
Assessing the Potential of Ride-Sharing Using Mobile and Social Data
Venue: arXiv cs.CY 2014
Year: 2014

Ride-sharing on the daily home-work-home commute can help individuals save on gasoline and other car-related costs, while at the same time it can reduce traffic and pollution. This paper assesses the potential of ride-sharing for reducing traffic in a city, based on mobility data extracted from 3G Call Description Records (CDRs, for the cities of Barcelona and Madrid) and from Online Social Networks (Twitter, collected for the cities of New York and Los Angeles). We first analyze these data sets to understand mobility patterns, home and work locations, and social ties between users. We then develop an efficient algorithm for matching users with similar mobility patterns, considering a range of constraints. The solution provides an upper bound to the potential reduction of cars in a city that can be achieved by ride-sharing. We use our framework to understand the different constraints and city characteristics on this potential benefit. For example, our study shows that traffic in the city of Madrid can be reduced by 59% if users are willing to share a ride with people who live and work within 1 km; if they can only accept a pick-up and drop-off delay up to 10 minutes, this potential benefit drops to 24%; if drivers also pick up passengers along the way, this number increases to 53%. If users are willing to ride only with people they know ("friends" in the CDR and OSN data sets), the potential of ride-sharing becomes negligible; if they are willing to ride with friends of friends, the potential reduction is up to 31%.
Spectrum Sharing for Device-to-Device Communication in Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses two fundamental and interrelated issues in device-to-device (D2D) enhanced cellular networks. The first issue is how D2D users should access spectrum, and we consider two choices: overlay (orthogonal spectrum between D2D and cellular UEs) and underlay (non-orthogonal). The second issue is how D2D users should choose between communicating directly or via the base station, a choice that depends on distance between the potential D2D transmitter and receiver. We propose a tractable hybrid network model where the positions of mobiles are modeled by random spatial Poisson point process, with which we present a general analytical approach that allows a unified performance evaluation for these questions. Then, we derive analytical rate expressions and apply them to optimize the two D2D spectrum sharing scenarios under a weighted proportional fair utility function. We find that as the proportion of potential D2D mobiles increases, the optimal spectrum partition in the overlay is almost invariant (when D2D mode selection threshold is large) while the optimal spectrum access factor in the underlay decreases. Further, from a coverage perspective, we reveal a tradeoff between the spectrum access factor and the D2D mode selection threshold in the underlay: as more D2D links are allowed (due to a more relaxed mode selection threshold), the network should actually make less spectrum available to them to limit their interference.
Robust Logistic Regression using Shift Parameters (Long Version)
Venue: arXiv cs.AI 2014
Year: 2014

Annotation errors can significantly hurt classifier performance, yet datasets are only growing noisier with the increased use of Amazon Mechanical Turk and techniques like distant supervision that automatically generate labels. In this paper, we present a robust extension of logistic regression that incorporates the possibility of mislabelling directly into the objective. Our model can be trained through nearly the same means as logistic regression, and retains its efficiency on high-dimensional datasets. Through named entity recognition experiments, we demonstrate that our approach can provide a significant improvement over the standard model when annotation errors are present.
Convexity of Decentralized Controller Synthesis
Venue: arXiv cs.SY 2014
Year: 2014

In decentralized control problems, a standard approach is to specify the set of allowable decentralized controllers as a closed subspace of linear operators. This then induces a corresponding set of Youla parameters. Previous work has shown that quadratic invariance of the controller set implies that the set of Youla parameters is convex. In this paper, we prove the converse. We thereby show that the only decentralized control problems for which the set of Youla parameters is convex are those which are quadratically invariant. We further show that under additional assumptions, quadratic invariance is necessary and sufficient for the set of achievable closed-loop maps to be convex. We give two versions of our results. The first applies to bounded linear operators on a Banach space and the second applies to (possibly unstable) causal LTI systems in discrete or continuous time.
Complexity Classes as Mathematical Axioms II
Venue: arXiv cs.CC 2014
Year: 2014

The second author previously discussed how classical complexity separation conjectures, we call them "axioms", have implications in three manifold topology: polynomial length stings of operations which preserve certain Jones polynomial evaluations cannot produce exponential simplifications of link diagrams. In this paper, we continue this theme, exploring now more subtle separation axioms for quantum complexity classes. Surprisingly, we now find that similar strings are unable to effect even linear simplifications of the diagrams.
On the Number of Closed Factors in a Word
Venue: arXiv cs.FL 2014
Year: 2014

A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special. We investigate the structure of closed factors of words. We show that a word of length $n$ contains at least $n+1$ distinct closed factors, and characterize those words having exactly $n+1$ closed factors. Furthermore, we show that a word of length $n$ can contain $Θ(n^{2})$ many distinct closed factors.
A Case Study in Coordination Programming: Performance Evaluation of S-Net vs Intel's Concurrent Collections
Venue: arXiv cs.PL 2014
Year: 2014

We present a programming methodology and runtime performance case study comparing the declarative data flow coordination language S-Net with Intel's Concurrent Collections (CnC). As a coordination language S-Net achieves a near-complete separation of concerns between sequential software components implemented in a separate algorithmic language and their parallel orchestration in an asynchronous data flow streaming network. We investigate the merits of S-Net and CnC with the help of a relevant and non-trivial linear algebra problem: tiled Cholesky decomposition. We describe two alternative S-Net implementations of tiled Cholesky factorization and compare them with two CnC implementations, one with explicit performance tuning and one without, that have previously been used to illustrate Intel CnC. Our experiments on a 48-core machine demonstrate that S-Net manages to outperform CnC on this problem.
Optimal Decentralized State-Feedback Control with Sparsity and Delays
Venue: arXiv cs.SY 2014
Year: 2014

This work presents the solution to a class of decentralized linear quadratic state-feedback control problems, in which the plant and controller must satisfy the same combination of delay and sparsity constraints. Using a novel decomposition of the noise history, the control problem is split into independent subproblems that are solved using dynamic programming. The approach presented herein both unifies and generalizes many existing results.
Minimal forbidden induced subgraphs of graphs of bounded clique-width and bounded linear clique-width
Venue: arXiv cs.DM 2014
Year: 2014

In the study of full bubble model graphs of bounded clique-width and bounded linear clique-width, we determined complete sets of forbidden induced subgraphs, that are minimal in the class of full bubble model graphs. In this note, we show that (almost all of) these graphs are minimal in the class of all graphs. As a corollary, we can give sets of minimal forbidden induced subgraphs for graphs of bounded clique-width and for graphs of bounded linear clique-width for arbitrary bounds.
Mining Attribute-based Access Control Policies
Venue: arXiv cs.CR 2014
Year: 2014

Attribute-based access control (ABAC) provides a high level of flexibility that promotes security and information sharing. ABAC policy mining algorithms have potential to significantly reduce the cost of migration to ABAC, by partially automating the development of an ABAC policy from an access control list (ACL) policy or role-based access control (RBAC) policy with accompanying attribute data. This paper presents an ABAC policy mining algorithm. To the best of our knowledge, it is the first ABAC policy mining algorithm. Our algorithm iterates over tuples in the given user-permission relation, uses selected tuples as seeds for constructing candidate rules, and attempts to generalize each candidate rule to cover additional tuples in the user-permission relation by replacing conjuncts in attribute expressions with constraints. Our algorithm attempts to improve the policy by merging and simplifying candidate rules, and then it selects the highest-quality candidate rules for inclusion in the generated policy.
The straight line complexity of small factorials and primorials
Venue: arXiv cs.CC 2014
Year: 2014

In this paper we determine the straight-line complexity of $n!$ for $n\leq 22$ and give bounds for the complexities up to $n=46$. In the same way we determine the straight-line complexity of the product of the first primes up to $p=31$ and gives bounds for $p\leq 43$. Our results are based on an exhaustive computer search of the short length straight-line programs.
MYE: Missing Year Estimation in Academic Social Networks
Venue: arXiv cs.DL 2014
Year: 2014

In bibliometrics studies, a common challenge is how to deal with incorrect or incomplete data. However, given a large volume of data, there often exists certain relationships between the data items that can allow us to recover missing data items and correct erroneous data. In this paper, we study a particular problem of this sort - estimating the missing year information associated with publications (and hence authors' years of active publication). We first propose a simple algorithm that only makes use of the "direct" information, such as paper citation/reference relationships or paper-author relationships. The result of this simple algorithm is used as a benchmark for comparison. Our goal is to develop algorithms that increase both the coverage (the percentage of missing year papers recovered) and accuracy (mean absolute error of the estimated year to the real year). We propose some advanced algorithms that extend inference by information propagation. For each algorithm, we propose three versions according to the given academic social network type: a) Homogeneous (only contains paper citation links), b) Bipartite (only contains paper-author relations), and, c) Heterogeneous (both paper citation and paper-author relations). We carry out experiments on the three public data sets (MSR Libra, DBLP and APS), and evaluated by applying the K-fold cross validation method. We show that the advanced algorithms can improve both coverage and accuracy.
An Exploratory Ethnographic Study of Issues and Concerns with Whole Genome Sequencing
Venue: arXiv cs.CR 2014
Year: 2014

Progress in Whole Genome Sequencing (WGS) will soon allow a large number of individuals to have their genome fully sequenced. This lays the foundations to improve modern healthcare, enabling a new era of personalized medicine where diagnosis and treatment is tailored to the patient's genetic makeup. It also allows individuals motivated by personal curiosity to have access to their genetic information, and use it, e.g., to trace their ancestry. However, the very same progress also amplifies a number of ethical and privacy concerns, that stem from the unprecedented sensitivity of genomic information and that are not well studied. This paper presents an exploratory ethnographic study of users' perception of privacy and ethical issues with WGS, as well as their attitude toward different WGS programs. We report on a series of semi-structured interviews, involving 16 participants, and analyze the results both quantitatively and qualitatively. Our analysis shows that users exhibit common trust concerns and fear of discrimination, and demand to retain strict control over their genetic information. Finally, we highlight the need for further research in the area and follow-up studies that build on our initial findings.
Near-Optimal Adaptive Compressed Sensing
Venue: arXiv cs.IT 2014
Year: 2014

This paper proposes a simple adaptive sensing and group testing algorithm for sparse signal recovery. The algorithm, termed Compressive Adaptive Sense and Search (CASS), is shown to be near-optimal in that it succeeds at the lowest possible signal-to-noise-ratio (SNR) levels, improving on previous work in adaptive compressed sensing. Like traditional compressed sensing based on random non-adaptive design matrices, the CASS algorithm requires only k log n measurements to recover a k-sparse signal of dimension n. However, CASS succeeds at SNR levels that are a factor log n less than required by standard compressed sensing. From the point of view of constructing and implementing the sensing operation as well as computing the reconstruction, the proposed algorithm is substantially less computationally intensive than standard compressed sensing. CASS is also demonstrated to perform considerably better in practice through simulation. To the best of our knowledge, this is the first demonstration of an adaptive compressed sensing algorithm with near-optimal theoretical guarantees and excellent practical performance. This paper also shows that methods like compressed sensing, group testing, and pooling have an advantage beyond simply reducing the number of measurements or tests -- adaptive versions of such methods can also improve detection and estimation performance when compared to non-adaptive direct (uncompressed) sensing.
Codes on Graphs: Fundamentals
Venue: arXiv cs.IT 2014
Year: 2014

This paper develops a fundamental theory of realizations of linear and group codes on general graphs using elementary group theory, including basic group duality theory. Principal new and extended results include: normal realization duality; analysis of systems-theoretic properties of fragments of realizations and their connections; "minimal = trim and proper" theorem for cycle-free codes; results showing that all constraint codes except interface nodes may be assumed to be trim and proper, and that the interesting part of a cyclic realization is its "2-core;" notions of observability and controllability for fragments, and related tests; relations between state-trimness and controllability, and dual state-trimness and observability.
Reliability and Secrecy Functions of the Wiretap Channel under Cost Constraint
Venue: arXiv cs.IT 2014
Year: 2014

The wiretap channel has been devised and studied first by Wyner, and subsequently extended to the case with non-degraded general wiretap channels by Csiszar and Korner. Focusing mainly on the Poisson wiretap channel with cost constraint, we newly introduce the notion of reliability and security functions as a fundamental tool to analyze and/or design the performance of an efficient wiretap channel system. Compact formulae for those functions are explicitly given for stationary memoryless wiretap channels. It is also demonstrated that, based on such a pair of reliability and security functions, we can control the tradeoff between reliability and security (usually conflicting), both with exponentially decreasing rates as block length n becomes large. Two ways to do so are given on the basis of concatenation and rate exchange. In this framework, the notion of the δ secrecy capacity is defined and shown to attain the strongest security standard among others. The maximized vs. averaged security measures is also discussed.
Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
Venue: arXiv cs.IT 2014
Year: 2014

This paper determines to within a single measurement the minimum number of measurements required to successfully reconstruct a signal drawn from a Gaussian mixture model in the low-noise regime. The method is to develop upper and lower bounds that are a function of the maximum dimension of the linear subspaces spanned by the Gaussian mixture components. The method not only reveals the existence or absence of a minimum mean-squared error (MMSE) error floor (phase transition) but also provides insight into the MMSE decay via multivariate generalizations of the MMSE dimension and the MMSE power offset, which are a function of the interaction between the geometrical properties of the kernel and the Gaussian mixture. These results apply not only to standard linear random Gaussian measurements but also to linear kernels that minimize the MMSE. It is shown that optimal kernels do not change the number of measurements associated with the MMSE phase transition, rather they affect the sensed power required to achieve a target MMSE in the low-noise regime. Overall, our bounds are tighter and sharper than standard bounds on the minimum number of measurements needed to recover sparse signals associated with a union of subspaces model, as they are not asymptotic in the signal dimension or signal sparsity.
On IEEE 802.11: Wireless LAN Technology
Venue: arXiv cs.NI 2014
Year: 2014

Network technologies are traditionally based on wireline solutions. But the introduction of the IEEE 802.11 standards have made a huge impact on the market such that laptops, PCs, printers, cellphones, and VoIP phones, MP3 players in our homes, in offices and even in public areas have incorporated the wireless LAN technology. Wireless broadband technologies nowadays provide unlimited broadband access to users which were previously offered only to wireline users. In this paper, we review and summarize one of the emerging wireless broadband technology i.e. IEEE 802.11,which is a set of physical layer standard for implementing wireless local area network computer communication in the 2.4,3.6,5 and 60GHz frequency band. They fix technology issues or add functionality which is expected to be required by future applications. Though some of the earlier versions of these technologies are obsolete (such as HiperLAN) now but still we have included them in this review for the sake of completeness.
Image color transfer to evoke different emotions based on color combinations
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, a color transfer framework to evoke different emotions for images based on color combinations is proposed. The purpose of this color transfer is to change the "look and feel" of images, i.e., evoking different emotions. Colors are confirmed as the most attractive factor in images. In addition, various studies in both art and science areas have concluded that other than single color, color combinations are necessary to evoke specific emotions. Therefore, we propose a novel framework to transfer color of images based on color combinations, using a predefined color emotion model. The contribution of this new framework is three-fold. First, users do not need to provide reference images as used in traditional color transfer algorithms. In most situations, users may not have enough aesthetic knowledge or path to choose desired reference images. Second, because of the usage of color combinations instead of single color for emotions, a new color transfer algorithm that does not require an image library is proposed. Third, again because of the usage of color combinations, artifacts that are normally seen in traditional frameworks using single color are avoided. We present encouraging results generated from this new framework and its potential in several possible applications including color transfer of photos and paintings.