OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Channel MAC Protocol for Full-Duplex Cognitive Radio Networks with Optimized Access Control and Load Balancing
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a multi-channel full-duplex Medium Access Control (MAC) protocol for cognitive radio networks (MFDC-MAC). Our design exploits the fact that full-duplex (FD) secondary users (SUs) can perform spectrum sensing and access simultaneously, and we employ the randomized dynamic channel selection for load balancing among channels and the standard backoff mechanism for contention resolution on each available channel. Then, we develop a mathematical model to analyze the throughput performance of the proposed MFDC-MAC protocol. Furthermore, we study the protocol configuration optimization to maximize the network throughput where we show that this optimization can be performed in two steps, namely optimization of access and transmission parameters on each channel and optimization of channel selection probabilities of the users. Such optimization aims at achieving efficient self-interference management for FD transceivers, sensing overhead control, and load balancing among the channels. Numerical results demonstrate the impacts of different protocol parameters and the importance of parameter optimization on the throughput performance as well as the significant performance gain of the proposed design compared to traditional design.
Cellular Underwater Wireless Optical CDMA Network: Potentials and Challenges
Venue: arXiv cs.NI 2016
Year: 2016

Underwater wireless optical communications is an emerging solution to the expanding demand for broadband links in oceans and seas. In this paper, a cellular underwater wireless optical code division multiple-access (UW-OCDMA) network is proposed to provide broadband links for commercial and military applications. The optical orthogonal codes (OOC) are employed as signature codes of underwater mobile users. Fundamental key aspects of the network such as its backhaul architecture, its potential applications and its design challenges are presented. In particular, the proposed network is used as infrastructure of centralized, decentralized and relay-assisted underwater sensor networks for high-speed real-time monitoring. Furthermore, a promising underwater localization and positioning scheme based on this cellular network is presented. Finally, probable design challenges such as cell edge coverage, blockage avoidance, power control and increasing the network capacity are addressed.
Reverse Nearest Neighbor Heat Maps: A Tool for Influence Exploration
Venue: arXiv cs.DB 2016
Year: 2016

We study the problem of constructing a reverse nearest neighbor (RNN) heat map by finding the RNN set of every point in a two-dimensional space. Based on the RNN set of a point, we obtain a quantitative influence (i.e., heat) for the point. The heat map provides a global view on the influence distribution in the space, and hence supports exploratory analyses in many applications such as marketing and resource management. To construct such a heat map, we first reduce it to a problem called Region Coloring (RC), which divides the space into disjoint regions within which all the points have the same RNN set. We then propose a novel algorithm named CREST that efficiently solves the RC problem by labeling each region with the heat value of its containing points. In CREST, we propose innovative techniques to avoid processing expensive RNN queries and greatly reduce the number of region labeling operations. We perform detailed analyses on the complexity of CREST and lower bounds of the RC problem, and prove that CREST is asymptotically optimal in the worst case. Extensive experiments with both real and synthetic data sets demonstrate that CREST outperforms alternative algorithms by several orders of magnitude.
A Short Note on Improved Logic Circuits in a Hexagonal Minesweeper
Venue: arXiv cs.CC 2016
Year: 2016

This paper aims to present an advanced version of PP-hardness proof of Minesweeper by Bondt. The advancement includes improved Minesweeper configurations for 'logic circuits' in a hexagonal Minesweeper. To do so, I demonstrate logical uncertainty in Minesweeper, which ironically allows a possibility to make some Boolean operators. The fact that existing hexagonal logic circuits did not clearly distinguish the true and false signal needs an improved form of a hexagonal wire. I introduce new forms of logic circuits such as NOT, AND, OR gates, a curve and a splitter of wires. Moreover, these new logic circuits complement Bondt's proof for PP-hardness of Minesweeper by giving a new figure.
Solving rank-constrained semidefinite programs in exact arithmetic
Venue: arXiv cs.SY 2016
Year: 2016

We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix is fixed, the complexity is polynomial in the number of variables. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We also implement it in Maple and discuss practical experiments.
Faster Longest Common Extension Queries in Strings over General Alphabets
Venue: arXiv cs.DS 2016
Year: 2016

Longest common extension queries (often called longest common prefix queries) constitute a fundamental building block in multiple string algorithms, for example computing runs and approximate pattern matching. We show that a sequence of $q$ LCE queries for a string of size $n$ over a general ordered alphabet can be realized in $O(q \log \log n+n\log^*n)$ time making only $O(q+n)$ symbol comparisons. Consequently, all runs in a string over a general ordered alphabet can be computed in $O(n \log \log n)$ time making $O(n)$ symbol comparisons. Our results improve upon a solution by Kosolobov (Information Processing Letters, 2016), who gave an algorithm with $O(n \log^{2/3} n)$ running time and conjectured that $O(n)$ time is possible. We make a significant progress towards resolving this conjecture. Our techniques extend to the case of general unordered alphabets, when the time increases to $O(q\log n + n\log^*n)$. The main tools are difference covers and the disjoint-sets data structure.
Counting Constraints in Flat Array Fragments
Venue: arXiv cs.LO 2016
Year: 2016

We identify a fragment of Presburger arithmetic enriched with free function symbols and cardinality constraints for interpreted sets, which is amenable to automated analysis. We establish decidability and complexity results for such a fragment and we implement our algorithms. The experiments run in discharging proof obligations coming from invariant checking and bounded model-checking benchmarks show the practical feasibility of our decision procedure.
Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field
Venue: arXiv cs.SC 2016
Year: 2016

We address the question of computing one selected term of an algebraic power series. In characteristic zero, the best algorithm currently known for computing the $N$th coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in $\sqrt{N}$. We show that over a prime field of positive characteristic $p$, the complexity can be lowered to $O(\log N)$. The mathematical basis for this dramatic improvement is a classical theorem stating that a formal power series with coefficients in a finite field is algebraic if and only if the sequence of its coefficients can be generated by an automaton. We revisit and enhance two constructive proofs of this result for finite prime fields. The first proof uses Mahler equations, whose sizes appear to be prohibitively large. The second proof relies on diagonals of rational functions; we turn it into an efficient algorithm, of complexity linear in $\log N$ and quasi-linear in $p$.
On pattern matching with k mismatches and few don't cares
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of pattern matching with $k$ mismatches, where there can be don't care or wild card characters in the pattern. Specifically, given a pattern $P$ of length $m$ and a text $T$ of length $n$, we want to find all occurrences of $P$ in $T$ that have no more than $k$ mismatches. The pattern can have don't care characters, which match any character. Without don't cares, the best known algorithm for pattern matching with $k$ mismatches has a runtime of $O(n\sqrt{k \log k})$. With don't cares in the pattern, the best deterministic algorithm has a runtime of $O(nk polylog m)$. Therefore, there is an important gap between the versions with and without don't cares. In this paper we give an algorithm whose runtime increases with the number of don't cares. We define an {\em island} to be a maximal length substring of $P$ that does not contain don't cares. Let $q$ be the number of islands in $P$. We present an algorithm that runs in $O(n\sqrt{k\log m}+n\min\{\sqrt[3]{qk\log^2 m},\sqrt{q\log m}\})$ time. If the number of islands $q$ is $O(k)$ this runtime becomes $O(n\sqrt{k\log m})$, which essentially matches the best known runtime for pattern matching with $k$ mismatches without don't cares. If the number of islands $q$ is $O(k^2)$, this algorithm is asymptotically faster than the previous best algorithm for pattern matching with $k$ mismatches with don't cares in the pattern.
Hybrid Beamforming for Massive MIMO Backhaul (Working Title)
Venue: arXiv cs.IT 2016
Year: 2016

The uplink where both the transmitter and receiver can use a large antenna array is considered. This is proposed as a method of antenna offloading and connecting small cell access points (SCAP) in a Two-Tier cellular network. Due to having a limited number of RF-chains, hybrid beamformers are designed where phase-only processing is done at the RF-band, followed by digital processing at the baseband. The proposed receiver is a row combiner that clusters sufficiently correlated antenna elements, and its' performance is compared against random projection via a Discrete Fourier Transform (DFT) matrix. The analogue to the row combiner is a column spreader, which is dependent on the transmit correlation, and repeats the transmitted signal over antenna elements that are correlated. A key benefit of this approach is to reduce the number of phase shifters used, while outperforming the DFT scheme. When only the transmitter has correlation and is RF-chain limited, the baseband precoding vectors are shown to be the eigenvectors of the effective transmit correlation matrix. Depending on the channel correlation, this matrix can be approximated to have a tridiagonal Toeplitz structure with the proposed column spreader (CS). The resulting eigenvalues have a closed form solution which allows us to characterize the sum rate of the system. Most interestingly, the associated eigenvectors do not require knowledge of the effective transmit correlation matrix to be calculated using an Eigenvalue Decomposition (EVD) method.
Optimality and Rate-Compatibility for Erasure-Coded Packet Transmissions when Fading Channel Diversity Increases with Packet Length
Venue: arXiv cs.IT 2016
Year: 2016

A message composed of packets is transmitted using erasure and channel coding over a fading channel with no feedback. For this scenario, the paper explores the trade-off between the redundancies allocated to the packet-level erasure code and the channel code, along with an objective of a low probability of failure to recover the message. To this end, we consider a fading model that we term proportional-diversity block fading (PD block fading). For a fixed overall code rate and transmit power, we formulate an optimization problem to numerically find the optimal channel-coding rate (and thus the optimal erasure-coding rate) that minimizes the probability of failure for various approximations of the problem. Furthermore, an interpretation of the results from an incremental redundancy point of view shows how rate-compatibility affects the possible trajectories of the failure probability as a function of the overall code rate. Our numerical results suggest that an optimal, rateless, hybrid coding scheme for a single-user wireless system over the PD block-fading channel should have the rate of the erasure code approach one.
Gender, Productivity, and Prestige in Computer Science Faculty Hiring Networks
Venue: arXiv cs.SI 2016
Year: 2016

Women are dramatically underrepresented in computer science at all levels in academia and account for just 15% of tenure-track faculty. Understanding the causes of this gender imbalance would inform both policies intended to rectify it and employment decisions by departments and individuals. Progress in this direction, however, is complicated by the complexity and decentralized nature of faculty hiring and the non-independence of hires. Using comprehensive data on both hiring outcomes and scholarly productivity for 2659 tenure-track faculty across 205 Ph.D.-granting departments in North America, we investigate the multi-dimensional nature of gender inequality in computer science faculty hiring through a network model of the hiring process. Overall, we find that hiring outcomes are most directly affected by (i) the relative prestige between hiring and placing institutions and (ii) the scholarly productivity of the candidates. After including these, and other features, the addition of gender did not significantly reduce modeling error. However, gender differences do exist, e.g., in scholarly productivity, postdoctoral training rates, and in career movements up the rankings of universities, suggesting that the effects of gender are indirectly incorporated into hiring decisions through gender's covariates. Furthermore, we find evidence that more highly ranked departments recruit female faculty at higher than expected rates, which appears to inhibit similar efforts by lower ranked departments. These findings illustrate the subtle nature of gender inequality in faculty hiring networks and provide new insights to the underrepresentation of women in computer science.
Perceiving Mass in Mixed Reality through Pseudo-Haptic Rendering of Newton's Third Law
Venue: arXiv cs.HC 2016
Year: 2016

In mixed reality, real objects can be used to interact with virtual objects. However, unlike in the real world, real objects do not encounter any opposite reaction force when pushing against virtual objects. The lack of reaction force during manipulation prevents users from perceiving the mass of virtual objects. Although this could be addressed by equipping real objects with force-feedback devices, such a solution remains complex and impractical.In this work, we present a technique to produce an illusion of mass without any active force-feedback mechanism. This is achieved by simulating the effects of this reaction force in a purely visual way. A first study demonstrates that our technique indeed allows users to differentiate light virtual objects from heavy virtual objects. In addition, it shows that the illusion is immediately effective, with no prior training. In a second study, we measure the lowest mass difference (JND) that can be perceived with this technique. The effectiveness and ease of implementation of our solution provides an opportunity to enhance mixed reality interaction at no additional cost.
Algorithms for Simultaneous Padé Approximations
Venue: arXiv cs.SC 2016
Year: 2016

We describe how to solve simultaneous Padé approximations over a power series ring $K[[x]]$ for a field $K$ using $O~(n^{ω- 1} d)$ operations in $K$, where $d$ is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches. Both algorithms return a reduced sub-bases that generates the complete set of solutions to the input approximations problem that satisfy the given degree constraints. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.
On the p-adic stability of the FGLM algorithm
Venue: arXiv cs.SC 2016
Year: 2016

Nowadays, many strategies to solve polynomial systems use the computation of a Gr{ö}bner basis for the graded reverse lexicographical ordering, followed by a change of ordering algorithm to obtain a Gr{ö}bner basis for the lexicographical ordering. The change of ordering algorithm is crucial for these strategies. We study the p-adic stability of the main change of ordering algorithm, FGLM. We show that FGLM is stable and give explicit upper bound on the loss of precision occuring in its execution. The variant of FGLM designed to pass from the grevlex ordering to a Gr{ö}bner basis in shape position is also stable. Our study relies on the application of Smith Normal Form computations for linear algebra.
Unsupervised High-level Feature Learning by Ensemble Projection for Semi-supervised Image Classification and Image Clustering
Venue: arXiv cs.CV 2016
Year: 2016

This paper investigates the problem of image classification with limited or no annotations, but abundant unlabeled data. The setting exists in many tasks such as semi-supervised image classification, image clustering, and image retrieval. Unlike previous methods, which develop or learn sophisticated regularizers for classifiers, our method learns a new image representation by exploiting the distribution patterns of all available data for the task at hand. Particularly, a rich set of visual prototypes are sampled from all available data, and are taken as surrogate classes to train discriminative classifiers; images are projected via the classifiers; the projected values, similarities to the prototypes, are stacked to build the new feature vector. The training set is noisy. Hence, in the spirit of ensemble learning we create a set of such training sets which are all diverse, leading to diverse classifiers. The method is dubbed Ensemble Projection (EP). EP captures not only the characteristics of individual images, but also the relationships among images. It is conceptually simple and computationally efficient, yet effective and flexible. Experiments on eight standard datasets show that: (1) EP outperforms previous methods for semi-supervised image classification; (2) EP produces promising results for self-taught image classification, where unlabeled samples are a random collection of images rather than being from the same distribution as the labeled ones; and (3) EP improves over the original features for image clustering. The code of the method is available on the project page.
Optimal Real-Time Bidding Frameworks Discussion
Venue: arXiv cs.GT 2016
Year: 2016

This note is a complementary material for the solution of optimal real-time bidding function in paper "Optimal Real-Time Bidding for Display Advertising, KDD 2014", where the estimated cost is taken as the bid price, i.e., the upper bound of the true cost. Here we discuss a more general bid optimisation framework with various utility and cost functions.
A Provably Correct MPC Approach to Safety Control of Urban Traffic Networks
Venue: arXiv cs.SY 2016
Year: 2016

Model predictive control (MPC) is a popular strategy for urban traffic management that is able to incorporate physical and user defined constraints. However, the current MPC methods rely on finite horizon predictions that are unable to guarantee desirable behaviors over long periods of time. In this paper we design an MPC strategy that is guaranteed to keep the evolution of a network in a desirable yet arbitrary -safe- set, while optimizing a finite horizon cost function. Our approach relies on finding a robust controlled invariant set inside the safe set that provides an appropriate terminal constraint for the MPC optimization problem. An illustrative example is included.
Toward Rapid Transformation of Ideas into Software
Venue: arXiv cs.SE 2016
Year: 2016

A key mission of computer science is to enable people realize their creative ideas as naturally and painlessly as possible. Software engineering is at the center of this mission -- software technologies enable reification of ideas into working systems. As computers become ubiquitous, both in availability and the aspects of human lives they touch, the quantity and diversity of ideas also rapidly grow. Our programming systems and technologies need to evolve to make this reification process -- transforming ideas to software -- as quick and accessible as possible. The goal of this paper is twofold. First, it advocates and highlights the "transforming ideas to software" mission as a moonshot for software engineering research. This is a long-term direction for the community, and there is no silver bullet that can get us there. To make this mission a reality, as a community, we need to improve the status quo across many dimensions. Thus, the second goal is to outline a number of directions to modernize our contemporary programming technologies for decades to come, describe work that has been undertaken along those vectors, and pinpoint critical challenges.
Do Cascades Recur?
Venue: arXiv cs.SI 2016
Year: 2016

Cascades of information-sharing are a primary mechanism by which content reaches its audience on social media, and an active line of research has studied how such cascades, which form as content is reshared from person to person, develop and subside. In this paper, we perform a large-scale analysis of cascades on Facebook over significantly longer time scales, and find that a more complex picture emerges, in which many large cascades recur, exhibiting multiple bursts of popularity with periods of quiescence in between. We characterize recurrence by measuring the time elapsed between bursts, their overlap and proximity in the social network, and the diversity in the demographics of individuals participating in each peak. We discover that content virality, as revealed by its initial popularity, is a main driver of recurrence, with the availability of multiple copies of that content helping to spark new bursts. Still, beyond a certain popularity of content, the rate of recurrence drops as cascades start exhausting the population of interested individuals. We reproduce these observed patterns in a simple model of content recurrence simulated on a real social network. Using only characteristics of a cascade's initial burst, we demonstrate strong performance in predicting whether it will recur in the future.
Secure Index Coding: Existence and Construction
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the construction of weakly-secure index codes for a sender to send messages to multiple receivers with side information in the presence of an eavesdropper. We derive a sufficient and necessary condition for the existence of index codes that are secure against an eavesdropper with access to any subset of messages of cardinality $t$, for any fixed $t$. In contrast to the benefits of using random keys in secure network coding, we prove that random keys do not promote security in three classes of index-coding instances.