OpenRaiser/Intern-Atlas huggingface dataset:
The Evolution of Sex through the Baldwin Effect
Venue: arXiv cs.NE 2017
Year: 2017

This paper suggests that the fundamental haploid-diploid cycle of eukaryotic sex exploits a rudimentary form of the Baldwin effect. With this explanation for the basic cycle, the other associated phenomena can be explained as evolution tuning the amount and frequency of learning experienced by an organism. Using the well-known NK model of fitness landscapes it is shown that varying landscape ruggedness varies the benefit of the haploid-diploid cycle, whether based upon endomitosis or syngamy. The utility of pre-meiotic doubling and recombination during the cycle are also shown to vary with landscape ruggedness. This view is suggested as underpinning, rather than contradicting, many existing explanations for sex.
Quasi-matrix-free hybrid multigrid on dynamically adaptive Cartesian grids
Venue: arXiv cs.NA 2017
Year: 2017

We present a family of spacetree-based multigrid realizations using the tree's multiscale nature to derive coarse grids. They align with matrix-free geometric multigrid solvers as they never assemble the system matrices which is cumbersome for dynamically adaptive grids and full multigrid. The most sophisticated realizations use BoxMG to construct operator-dependent prolongation and restriction in combination with Galerkin/Petrov-Galerkin coarse-grid operators. This yields robust solvers for nontrivial elliptic problems. We embed the algebraic, problem- and grid-dependent multigrid operators as stencils into the grid and evaluate all matrix-vector products in-situ throughout the grid traversals. While such an approach is not literally matrix-free---the grid carries the matrix---we propose to switch to a hierarchical representation of all operators. Only differences of algebraic operators to their geometric counterparts are held. These hierarchical differences can be stored and exchanged with small memory footprint. Our realizations support arbitrary dynamically adaptive grids while they vertically integrate the multilevel operations through spacetree linearization. This yields good memory access characteristics, while standard colouring of mesh entities with domain decomposition allows us to use parallel manycore clusters. All realization ingredients are detailed such that they can be used by other codes.
On User Association in Multi-Tier Full-Duplex Cellular Networks
Venue: arXiv cs.IT 2017
Year: 2017

We address the user association problem in multi-tier in-band full-duplex (FD) networks. Specifically, we consider the case of decoupled user association (DUA) in which users (UEs) are not necessarily served by the same base station (BS) for uplink (UL) and downlink (DL) transmissions. Instead, UEs can simultaneously associate to different BSs based on two independent weighted path-loss user association criteria for UL and DL. We use stochastic geometry to develop a comprehensive modeling framework for the proposed system model where BSs and UEs are spatially distributed according to independent point processes. We derive closed-form expressions for the mean rate utility in FD, half-duplex (HD) DL, and HD UL networks as well as the mean rate utility of legacy nodes with only HD capabilities in a multi-tier FD network. We formulate and solve an optimization problem that aims at maximizing the mean rate utility of the FD network by optimizing the DL and UL user association criteria. We investigate the effects of different network parameters including the spatial density of BSs and power control parameter. We also investigate the effect of imperfect self-interference cancellation (SIC) and show that it is more severe at UL, where there exist minimum required SIC capabilities for BSs and UEs for which FD networks are preferable to HD networks; otherwise, HD networks are preferable. In addition, we discuss several special cases and provide guidelines on the possible extensions of the proposed framework. We conclude that DUA outperforms coupled user association (CUA) in which UEs associate to the same BS for both UL and DL transmissions.
Nash Social Welfare Approximation for Strategic Agents
Venue: arXiv cs.GT 2017
Year: 2017

The fair division of resources is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist fair mechanisms despite strategic behavior of the agents. A fundamental objective function used for measuring fair outcomes is the Nash social welfare, defined as the geometric mean of the agent utilities. This objective function is maximized by widely known solution concepts such as Nash bargaining and the competitive equilibrium with equal incomes. In this work we focus on the question of (approximately) implementing the Nash social welfare. The starting point of our analysis is the Fisher market, a fundamental model of an economy, whose benchmark is precisely the (weighted) Nash social welfare. We begin by studying two extreme classes of valuations functions, namely perfect substitutes and perfect complements, and find that for perfect substitutes, the Fisher market mechanism has a constant approximation: at most 2 and at least e1e. However, for perfect complements, the Fisher market does not work well, its bound degrading linearly with the number of players. Strikingly, the Trading Post mechanism---an indirect market mechanism also known as the Shapley-Shubik game---has significantly better performance than the Fisher market on its own benchmark. Not only does Trading Post achieve an approximation of 2 for perfect substitutes, but this bound holds for all concave utilities and becomes arbitrarily close to optimal for Leontief utilities (perfect complements), where it reaches $(1+ε)$ for every $ε> 0$. Moreover, all the Nash equilibria of the Trading Post mechanism are pure for all concave utilities and satisfy an important notion of fairness known as proportionality.
Asymptotic Comparison of ML and MAP Detectors for Multidimensional Constellations
Venue: arXiv cs.IT 2017
Year: 2017

A classical problem in digital communications is to evaluate the symbol error probability (SEP) and bit error probability (BEP) of a multidimensional constellation over an additive white Gaussian noise channel. In this paper, we revisit this problem for nonequally likely symbols and study the asymptotic behavior of the optimal maximum a posteriori (MAP) detector. Exact closed-form asymptotic expressions for SEP and BEP for arbitrary constellations and input distributions are presented. The well-known union bound is proven to be asymptotically tight under general conditions. The performance of the practically relevant maximum likelihood (ML) detector is also analyzed. Although the decision regions with MAP detection converge to the ML regions at high signal-to-noise ratios, the ratio between the MAP and ML detector in terms of both SEP and BEP approach a constant, which depends on the constellation and a priori probabilities. Necessary and sufficient conditions for asymptotic equivalence between the MAP and ML detectors are also presented.
Nonlinear Self-Interference Cancellation for Full-Duplex Radios: From Link- and System-Level Performance Perspectives
Venue: arXiv cs.IT 2017
Year: 2017

One of the promising technologies for LTE Evolution is full-duplex radio, an innovation is expected to double the spectral efficiency. To realize full-duplex in practice, the main challenge is overcoming self-interference, and to do so, researchers have developed self-interference cancellation techniques. Since most wireless transceivers use power amplifiers, especially in cellular systems, researchers have revealed the importance of nonlinear self-interference cancellation. In this article, we first explore several nonlinear digital self-interference cancellation techniques. We then propose a low complexity pre-calibration-based nonlinear digital self-interference cancellation technique. Next we discuss issues about reference signal allocation and the overhead of each technique. For performance evaluations, we carry out extensive measurements through a real-time prototype and link-/system-level simulations. For link-level analysis, we measure the amount of cancelled self-interference for each technique. We also evaluate system-level performances through 3D ray-tracing-based simulations. Numerical results confirm the significant performance improvement over a half-duplex system even in interference-limited indoor environments.
Universal Random Access Error Exponents for Codebooks of Different Word-Lengths
Venue: arXiv cs.IT 2017
Year: 2017

Csiszár's channel coding theorem for multiple codebooks is generalized allowing the codeword lenghts differ across codebooks. Also in this case, for each codebook an error exponent can be achieved that equals the random coding exponent for this codebook alone, in addition, erasure detection failure probability tends to 0. This is proved even for sender and receiver not knowing the channel. As a corollary, a substantial improvement is obtained when the sender knows the channel.
Collaborative Training of Tensors for Compositional Distributional Semantics
Venue: arXiv cs.CL 2017
Year: 2017

Type-based compositional distributional semantic models present an interesting line of research into functional representations of linguistic meaning. One of the drawbacks of such models, however, is the lack of training data required to train each word-type combination. In this paper we address this by introducing training methods that share parameters between similar words. We show that these methods enable zero-shot learning for words that have no training data at all, as well as enabling construction of high-quality tensors from very few training examples per word.
Tight lower bounds for the complexity of multicoloring
Venue: arXiv cs.DS 2017
Year: 2017

In the multicoloring problem, also known as ($a$:$b$)-coloring or $b$-fold coloring, we are given a graph G and a set of $a$ colors, and the task is to assign a subset of $b$ colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to the Kneser graph $KG_{a,b}$, and gives relaxations approaching the fractional chromatic number. We study the complexity of determining whether a graph has an ($a$:$b$)-coloring. Our main result is that this problem does not admit an algorithm with running time $f(b)\cdot 2^{o(\log b)\cdot n}$, for any computable $f(b)$, unless the Exponential Time Hypothesis (ETH) fails. A $(b+1)^n\cdot \text{poly}(n)$-time algorithm due to Nederlof [2008] shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a $2^{O(n+h)}$ algorithm unless ETH fails, even if the target graph is required to be a Kneser graph. This refines the understanding given by the recent lower bound of Cygan et al. [SODA 2016]. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström [Canad. Math. Bull., 1965], which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we prove that the running time of the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for the r-monomial detection problem are optimal under ETH.
End-to-end training of object class detectors for mean average precision
Venue: arXiv cs.CV 2017
Year: 2017

We present a method for training CNN-based object class detectors directly using mean average precision (mAP) as the training loss, in a truly end-to-end fashion that includes non-maximum suppression (NMS) at training time. This contrasts with the traditional approach of training a CNN for a window classification loss, then applying NMS only at test time, when mAP is used as the evaluation metric in place of classification accuracy. However, mAP following NMS forms a piecewise-constant structured loss over thousands of windows, with gradients that do not convey useful information for gradient descent. Hence, we define new, general gradient-like quantities for piecewise constant functions, which have wide applicability. We describe how to calculate these efficiently for mAP following NMS, enabling to train a detector based on Fast R-CNN directly for mAP. This model achieves equivalent performance to the standard Fast R-CNN on the PASCAL VOC 2007 and 2012 datasets, while being conceptually more appealing as the very same model and loss are used at both training and test time.
Opinion Dynamics in Networks: Convergence, Stability and Lack of Explosion
Venue: arXiv cs.SI 2017
Year: 2017

Inspired by the work of [Kempe, Kleinberg, Oren, Slivkins, EC13] we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of Kempe et. al. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of Kempe et. al., as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et. al. dynamics as well. Next, we extend the model of Kempe et. al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than a parameter $ε$. We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in $1/ε$.
Nonlinear Stabilization via Control Contraction Metrics: a Pseudospectral Approach for Computing Geodesics
Venue: arXiv cs.SY 2017
Year: 2017

Real-time nonlinear stabilization techniques are often limited by inefficient or intractable online and/or offline computations, or a lack guarantee for global stability. In this paper, we explore the use of Control Contraction Metrics (CCM) for nonlinear stabilization because it offers tractable offline computations that give formal guarantees for global stability. We provide a method to solve the associated online computation for a CCM controller - a pseudospectral method to find a geodesic. Through a case study of a stiff nonlinear system, we highlight two key benefits: (i) using CCM for nonlinear stabilization and (ii) rapid online computations amenable to real-time implementation. We compare the performance of a CCM controller with other popular feedback control techniques, namely the Linear Quadratic Regulator (LQR) and Nonlinear Model Predictive Control (NMPC). We show that a CCM controller using a pseudospectral approach for online computations is a middle ground between the simplicity of LQR and stability guarantees for NMPC.
Spectrum-based Software Fault Localization: A Survey of Techniques, Advances, and Challenges
Venue: arXiv cs.SE 2017
Year: 2017

Despite being one of the most basic tasks in software development, debugging is still performed in a mostly manual way, leading to high cost and low performance. To address this problem, researchers have studied promising approaches, such as Spectrum-based Fault Localization (SFL) techniques, which pinpoint program elements more likely to contain faults. This survey discusses the state-of-the-art of SFL, including the different techniques that have been proposed, the type and number of faults they address, the types of spectra they use, the programs they utilize in their validation, the testing data that support them, and their use at industrial settings. Notwithstanding the advances, there are still challenges for the industry to adopt these techniques, which we analyze in this paper. SFL techniques should propose new ways to generate reduced sets of suspicious entities, combine different spectra to fine-tune the fault localization ability, use strategies to collect fine-grained coverage levels from suspicious coarser levels for balancing execution costs and output precision, and propose new techniques to cope with multiple-fault programs. Moreover, additional user studies are needed to understand better how SFL techniques can be used in practice. We conclude by presenting a concept map about topics and challenges for future research in SFL.
Probability of Partially Decoding Network-Coded Messages
Venue: arXiv cs.IT 2017
Year: 2017

In the literature there exists analytical expressions for the probability of a receiver decoding a transmitted source message that has been encoded using random linear network coding. In this work, we look into the probability that the receiver will decode at least a fraction of the source message, and present an exact solution to this problem for both non-systematic and systematic network coding. Based on the derived expressions, we investigate the potential of these two implementations of network coding for information-theoretic secure communication and progressive recovery of data.
Compressed sensing with corrupted Fourier measurements
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies a data recovery problem in compressed sensing (CS), given a measurement vector b with corruptions: b=Ax0+f0, can we recover x0 and f0 via the reweighted l1 minimization: minimize |x| + lambda*|f| subject to Ax+f=b? Here the m by n measurement matrix A is a partial Fourier matrix, x0 denotes the n dimensional ground true signal vector, f0 denotes the m-dimensional corrupted noise vector, it is assumed that a positive fraction of entries in the measurement vector b are corrupted by the non-zero entries of f0. This problem had been studied in literatures [1-3], unfortunately, certain random assumptions (which are often hard to meet in practice) are required for the signal x0 in these papers. In this paper, we show that x0 and f0 can be recovered exactly by the solution of the above reweighted l1 minimization with high probability provided that m>O(card(x0)log(n)log(n)) and n is prime, here card(x0) denotes the cardinality (number of non-zero entries) of x0. Except the sparsity, no extra assumption is needed for x0.
Shared multi-processor scheduling
Venue: arXiv cs.DM 2017
Year: 2017

We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job's completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private processor and shared processors, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.
Dappled tiling
Venue: arXiv cs.DM 2017
Year: 2017

We consider a certain tiling problem of a planar region in which there are no long horizontal or vertical strips consisting of copies of the same tile. Intuitively speaking, we would like to create a dappled pattern with two or more kinds of tiles. We give an efficient algorithm to turn any tiling into one satisfying the condition, and discuss its applications in texturing.
Multi-Camera Action Dataset for Cross-Camera Action Recognition Benchmarking
Venue: arXiv cs.CV 2017
Year: 2017

Action recognition has received increasing attention from the computer vision and machine learning communities in the last decade. To enable the study of this problem, there exist a vast number of action datasets, which are recorded under controlled laboratory settings, real-world surveillance environments, or crawled from the Internet. Apart from the "in-the-wild" datasets, the training and test split of conventional datasets often possess similar environments conditions, which leads to close to perfect performance on constrained datasets. In this paper, we introduce a new dataset, namely Multi-Camera Action Dataset (MCAD), which is designed to evaluate the open view classification problem under the surveillance environment. In total, MCAD contains 14,298 action samples from 18 action categories, which are performed by 20 subjects and independently recorded with 5 cameras. Inspired by the well received evaluation approach on the LFW dataset, we designed a standard evaluation protocol and benchmarked MCAD under several scenarios. The benchmark shows that while an average of 85% accuracy is achieved under the closed-view scenario, the performance suffers from a significant drop under the cross-view scenario. In the worst case scenario, the performance of 10-fold cross validation drops from 87.0% to 47.4%.
HyperLogLog Hyper Extended: Sketches for Concave Sublinear Frequency Statistics
Venue: arXiv cs.DS 2017
Year: 2017

One of the most common statistics computed over data elements is the number of distinct keys. A thread of research pioneered by Flajolet and Martin three decades ago culminated in the design of optimal approximate counting sketches, which have size that is double logarithmic in the number of distinct keys and provide estimates with a small relative error. Moreover, the sketches are composable, and thus suitable for streamed, parallel, or distributed computation. We consider here all statistics of the frequency distribution of keys, where a contribution of a key to the aggregate is concave and grows (sub)linearly with its frequency. These fundamental aggregations are very common in text, graphs, and logs analysis and include logarithms, low frequency moments, and capping statistics. We design composable sketches of double-logarithmic size for all concave sublinear statistics. Our design combines theoretical optimality and practical simplicity. In a nutshell, we specify tailored mapping functions of data elements to output elements so that our target statistics on the data elements is approximated by the (max-) distinct statistics of the output elements, which can be approximated using off-the-shelf sketches. Our key insight is relating these target statistics to the {\em complement Laplace} transform of the input frequencies.
Explicit Polyhedral Bounds on Network Coding Rate Regions via Entropy Function Region: Algorithms, Symmetry, and Computation
Venue: arXiv cs.IT 2017
Year: 2017

Automating the solutions of multiple network information theory problems, stretching from fundamental concerns such as determining all information inequalities and the limitations of linear codes, to applied ones such as designing coded networks, distributed storage systems, and caching systems, can be posed as polyhedral projections. These problems are demonstrated to exhibit multiple types of polyhedral symmetries. It is shown how these symmetries can be exploited to reduce the complexity of solving these problems through polyhedral projection.