OpenRaiser/Intern-Atlas huggingface dataset:
Lemmings is PSPACE-complete
Venue: arXiv cs.GT 2015
Year: 2015

Lemmings is a computer puzzle game developed by DMA Design and published by Psygnosis in 1991, in which the player has to guide a tribe of lemming creatures to safety through a hazardous landscape, by assigning them specific skills that modify their behavior in different ways. In this paper we study the optimization problem of saving the highest number of lemmings in a given landscape with a given number of available skills. We prove that the game is PSPACE-complete, even if there is only one lemming to save, and only Builder and Basher skills are available. We thereby settle an open problem posed by Cormode in 2004, and again by Forisek in 2010. However we also prove that, if we restrict the game to levels in which the available Builder skills are only polynomially many (and there is any number of other skills), then the game is solvable in NP. Similarly, if the available Basher, Miner, and Digger skills are polynomially many, the game is solvable in NP. Furthermore, we show that saving the maximum number of lemmings is APX-hard, even when only one type of skill is available, whatever this skill is. This contrasts with the membership in P of the decision problem restricted to levels with no "deadly areas" (such as water or traps) and only Climber and Floater skills, as previously established by Cormode.
Classic Nintendo Games are (Computationally) Hard
Venue: arXiv cs.CC 2015
Year: 2015

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versions of Super Mario Bros. 1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokemon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.
FEAST Eigenvalue Solver v3.0 User Guide
Venue: arXiv cs.MS 2015
Year: 2015

The FEAST eigensolver package is a free high-performance numerical library for solving the Hermitian and non-Hermitian eigenvalue problems, and obtaining all the eigenvalues and (right/left) eigenvectors within a given search interval or arbitrary contour in the complex plane. Its originality lies with a new transformative numerical approach to the traditional eigenvalue algorithm design - the FEAST algorithm. The FEAST eigensolver combines simplicity and efficiency and it offers many important capabilities for achieving high performance, robustness, accuracy, and scalability on parallel architectures. FEAST is both a comprehensive library package, and an easy to use software. It includes flexible reverse communication interfaces and ready to use predefined interfaces for dense, banded and sparse systems. The current version v3.0 of the FEAST package can address both Hermitian and non-Hermitian eigenvalue problems (real symmetric, real non-symmetric, complex Hermitian, complex symmetric, or complex general systems) on both shared-memory and distributed memory architectures (i.e contains both FEAST-SMP and FEAST-MPI packages). This User's guide provides instructions for installation setup, a detailed description of the FEAST interfaces and a large number of examples.
Analytical Models for Power Networks: The case of the Western US and ERCOT grids
Venue: arXiv cs.SI 2015
Year: 2015

The topological structure of the power grid plays a key role in the reliable delivery of electricity and price settlement in the electricity market. Incorporation of new energy sources and loads into the grid over time has led to its structural and geographical expansion and can affect its stable operation. This paper presents an intuitive analytical model for the temporal evolution of large grids and uses it to understand common structural features observed in grids across America. In particular, key graph parameters like degree distribution, graph diameter, betweenness centralities, eigen-spread and clustering coefficients, as well as graph processes like infection propagation are used to quantify the model's benefits through comparison with the Western US and ERCOT power grids. The most significant contribution of the developed model is its analytical tractability, that provides a closed form expression for the nodal degree distribution observed in large grids. The discussed model can be used to generate realistic test cases to analyze topological effects on grid functioning and new grid technologies.
Simultaneous Embedding of Planar Graphs
Venue: arXiv cs.DS 2015
Year: 2015

Simultaneous embedding is concerned with simultaneously representing a series of graphs sharing some or all vertices. This forms the basis for the visualization of dynamic graphs and thus is an important field of research. Recently there has been a great deal of work investigating simultaneous embedding problems both from a theoretical and a practical point of view. We survey recent work on this topic.
Flip Distance Between Triangulations of a Planar Point Set is APX-Hard
Venue: arXiv cs.CG 2015
Year: 2015

In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set $S$ in the Euclidean plane and two triangulations $T_1$ and $T_2$ of $S$, it is an APX-hard problem to minimize the number of edge flips to transform $T_1$ to $T_2$.
Improving Two-Way Selective Decode-and-forward Wireless Relaying with Energy-Efficient One-bit Soft Forwarding
Venue: arXiv cs.IT 2015
Year: 2015

Motivated by applications such as battery-operated wireless sensor networks (WSN), we propose an easy-to-implement energy-efficient two-way relaying scheme. In particular, we address the challenge of improving the standard two-way selective decode-and-forward protocol (TW-SDF) in terms of block-error-rate (BLER) with minor additional complexity and energy consumption. By following the principle of soft relaying, our solution is the two-way one-bit soft forwarding (TW-1bSF) protocol in which the relay forwards the one-bit quantization of a posterior information metric about the transmitted bits, associated with an appropriately designed reliability parameter. In WSN-related standards (such as IEEE802.15.6 and Bluetooth), block codes are adopted instead of convolutional and other sophisticated codes, due to their efficient decoder hardware implementation. As the second main contribution, we derive tight upper bounds on the BLER performance for both TW-SDF and TW-1bSF, when the two-way relaying network employs block codes and hard decoding. The error probability analysis confirms the superiority of TW-1bSF. Moreover, we derive the asymptotic performance gain of TW-1bSF over TW-SDF, which further suggests that the proposed protocol is a good choice, especially when long block codes are used.
Bounded Model Checking of Temporal Formulas with Alloy
Venue: arXiv cs.SE 2015
Year: 2015

Alloy is formal modeling language based on first-order relational logic, with no specific support for specifying reactive systems. We propose the usage of temporal logic to specify such systems, and show how bounded model checking can be performed with the Alloy Analyzer.
Constructing the L2-Graph for Robust Subspace Learning and Subspace Clustering
Venue: arXiv cs.CV 2015
Year: 2015

Under the framework of graph-based learning, the key to robust subspace clustering and subspace learning is to obtain a good similarity graph that eliminates the effects of errors and retains only connections between the data points from the same subspace (i.e., intra-subspace data points). Recent works achieve good performance by modeling errors into their objective functions to remove the errors from the inputs. However, these approaches face the limitations that the structure of errors should be known prior and a complex convex problem must be solved. In this paper, we present a novel method to eliminate the effects of the errors from the projection space (representation) rather than from the input space. We first prove that $\ell_1$-, $\ell_2$-, $\ell_{\infty}$-, and nuclear-norm based linear projection spaces share the property of Intra-subspace Projection Dominance (IPD), i.e., the coefficients over intra-subspace data points are larger than those over inter-subspace data points. Based on this property, we introduce a method to construct a sparse similarity graph, called L2-Graph. The subspace clustering and subspace learning algorithms are developed upon L2-Graph. Experiments show that L2-Graph algorithms outperform the state-of-the-art methods for feature extraction, image clustering, and motion segmentation in terms of accuracy, robustness, and time efficiency.
Multiuser Diversity for the Cognitive Uplink with Generalized Fading and Reduced Primary's Cooperation
Venue: arXiv cs.IT 2015
Year: 2015

In cognitive multiple access networks, feedback is an important mechanism to convey secondary transmitter primary base station (STPB) channel gains from the primary base station (PBS) to the secondary base station (SBS). This paper investigates the optimal sum-rate capacity scaling laws for cognitive multiple access networks in feedback limited communication scenarios. First, an efficient feedback protocol called $K$-smallest channel gains ($K$-SCGs) feedback protocol is proposed in which the PBS feeds back the $\K$ smallest out of $N$ STPB channel gains to the SBS. Second, the sum-rate performance of the $K$-SCG feedback protocol is studied for three network types when transmission powers of secondary users (SUs) are optimally allocated. The network types considered are total-power-and-interference-limited (TPIL), interference-limited (IL) and individual-power-and-interference-limited (IPIL) networks. For each network type studied, we provide a sufficient condition on $\K$ such that the $K$-SCG feedback protocol is {\em asymptotically} optimal in the sense that the secondary network sum-rate scaling behavior under the $K$-SCG feedback protocol is the same with that under the full-feedback protocol. We allow distributions of secondary-transmitter-secondary-base-station (STSB), and STPB channel power gains to belong to a fairly general class of distributions called class $\mathcal{C}$-distributions that includes commonly used fading models.
Rank Centrality: Ranking from Pair-wise Comparisons
Venue: arXiv cs.LG 2015
Year: 2015

The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding `scores' for each object (e.g. player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pair-wise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pair-wise comparisons) in which each object has an associated score which determines the probabilistic outcomes of pair-wise comparisons between objects. In terms of the pair-wise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g. each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order-optimal.
Separation of Routing and Scheduling in Backpressure-Based Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

Backpressure routing and scheduling, with its throughput-optimal operation guarantee, is a promising technique to improve throughput in wireless multi-hop networks. Although backpressure is conceptually viewed as layered, the decisions of routing and scheduling are made jointly, which imposes several challenges in practice. In this work, we present Diff-Max, an approach that separates routing and scheduling and has three strengths: (i) Diff-Max improves throughput significantly, (ii) the separation of routing and scheduling makes practical implementation easier by minimizing cross-layer operations; i.e., routing is implemented in the network layer and scheduling is implemented in the link layer, and (iii) the separation of routing and scheduling leads to modularity; i.e., routing and scheduling are independent modules in Diff-Max, and one can continue to operate even if the other does not. Our approach is grounded in a network utility maximization (NUM) formulation and its solution. Based on the structure of Diff-Max, we propose two practical schemes: Diff-subMax and wDiff-subMax. We demonstrate the benefits of our schemes through simulation in ns-2.
Recognition of collapsible complexes is NP-complete
Venue: arXiv cs.CG 2015
Year: 2015

We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.
Self-Organizing Flows in Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Social networks offer users new means of accessing information, essentially relying on "social filtering", i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to the interested users. Our motivation in this paper is to measure to what extent self-organization of the social network results in efficient social filtering. To this end we introduce flow games, a simple abstraction that models network formation under selfish user dynamics, featuring user-specific interests and budget of attention. In the context of homogeneous user interests, we show that selfish dynamics converge to a stable network structure (namely a pure Nash equilibrium) with close-to-optimal information dissemination. We show in contrast, for the more realistic case of heterogeneous interests, that convergence, if it occurs, may lead to information dissemination that can be arbitrarily inefficient, as captured by an unbounded "price of anarchy". Nevertheless the situation differs when users' interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set.
Concentration of Measure Inequalities in Information Theory, Communications and Coding (Second Edition)
Venue: arXiv cs.IT 2015
Year: 2015

During the last two decades, concentration inequalities have been the subject of exciting developments in various areas, including convex geometry, functional analysis, statistical physics, high-dimensional statistics, pure and applied probability theory, information theory, theoretical computer science, and learning theory. This monograph focuses on some of the key modern mathematical tools that are used for the derivation of concentration inequalities, on their links to information theory, and on their various applications to communications and coding. In addition to being a survey, this monograph also includes various new recent results derived by the authors. The first part of the monograph introduces classical concentration inequalities for martingales, as well as some recent refinements and extensions. The power and versatility of the martingale approach is exemplified in the context of codes defined on graphs and iterative decoding algorithms, as well as codes for wireless communication. The second part of the monograph introduces the entropy method, an information-theoretic technique for deriving concentration inequalities. The basic ingredients of the entropy method are discussed first in the context of logarithmic Sobolev inequalities, which underlie the so-called functional approach to concentration of measure, and then from a complementary information-theoretic viewpoint based on transportation-cost inequalities and probability in metric spaces. Some representative results on concentration for dependent random variables are briefly summarized, with emphasis on their connections to the entropy method. Finally, we discuss several applications of the entropy method to problems in communications and coding, including strong converses, empirical distributions of good channel codes, and an information-theoretic converse for concentration of measure.
Topic Extraction and Bundling of Related Scientific Articles
Venue: arXiv cs.IR 2015
Year: 2015

Automatic classification of scientific articles based on common characteristics is an interesting problem with many applications in digital library and information retrieval systems. Properly organized articles can be useful for automatic generation of taxonomies in scientific writings, textual summarization, efficient information retrieval etc. Generating article bundles from a large number of input articles, based on the associated features of the articles is tedious and computationally expensive task. In this report we propose an automatic two-step approach for topic extraction and bundling of related articles from a set of scientific articles in real-time. For topic extraction, we make use of Latent Dirichlet Allocation (LDA) topic modeling techniques and for bundling, we make use of hierarchical agglomerative clustering techniques. We run experiments to validate our bundling semantics and compare it with existing models in use. We make use of an online crowdsourcing marketplace provided by Amazon called Amazon Mechanical Turk to carry out experiments. We explain our experimental setup and empirical results in detail and show that our method is advantageous over existing ones.
Introduction to Redberry: a computer algebra system designed for tensor manipulation
Venue: arXiv cs.SC 2015
Year: 2015

In this paper we introduce Redberry --- an open source computer algebra system with native support of tensorial expressions. It provides basic computer algebra tools (algebraic manipulations, substitutions, basic simplifications etc.) which are aware of specific features of indexed expressions: contractions of indices, permutational symmetries, multiple index types etc. Redberry supports conventional \LaTeX-style input notation for tensorial expressions. The high energy physics package includes tools for Feynman diagrams calculation: Dirac and SU(N) algebra, Levi-Civita simplifications and tools for one-loop calculations in quantum field theory. In the paper we give detailed overview of Redberry features: from basic manipulations with tensors to real Feynman diagrams calculation, accompanied by many examples. Redberry is written in Java 7 and provides convenient Groovy-based user interface inside the high-level general purpose programming language environment. Redberry is available from http://redberry.cc
On the Capacity of Channels with Timing Synchronization Errors
Venue: arXiv cs.IT 2015
Year: 2015

We consider a new formulation of a class of synchronization error channels and derive analytical bounds and numerical estimates for the capacity of these channels. For the binary channel with only deletions, we obtain an expression for the symmetric information rate in terms of subsequence weights which reduces to a tight lower bound for small deletion probabilities. We are also able to exactly characterize the Markov-1 rate for the binary channel with only replications. For a channel that introduces deletions as well as replications of input symbols, we design approximating channels that parameterize the state space and show that the information rates of these approximate channels approach that of the deletion-replication channel as the state space grows. For the case of the channel where deletions and replications occur with the same probabilities, a stronger result in the convergence of mutual information rates is shown. The numerous advantages this new formulation presents are explored.
Directed Information on Abstract Spaces: Properties and Variational Equalities
Venue: arXiv cs.IT 2015
Year: 2015

Directed information or its variants are utilized extensively in the characterization of the capacity of channels with memory and feedback, nonanticipative lossy data compression, and their generalizations to networks. In this paper, we derive several functional and topological properties of directed information for general abstract alphabets (complete separable metric spaces) using the topology of weak convergence of probability measures. These include convexity of the set of consistent distributions, which uniquely define causally conditioned distributions, convexity and concavity of directed information with respect to the sets of consistent distributions, weak compactness of these sets of distributions, their joint distributions and their marginals. Furthermore, we show lower semicontinuity of directed information, and under certain conditions we also establish continuity of directed information. Finally, we derive variational equalities for directed information, including sequential versions. These may be viewed as the analogue of the variational equalities of mutual information (utilized in Blahut-Arimoto algorithm). In summary, we extend the basic functional and topological properties of mutual information to directed information. These properties are discussed in the context of extremum problems of directed information.
A Labelled Sequent Calculus for BBI: Proof Theory and Proof Search
Venue: arXiv cs.LO 2015
Year: 2015

We present a labelled sequent calculus for Boolean BI, a classical variant of O'Hearn and Pym's logic of Bunched Implication. The calculus is simple, sound, complete, and enjoys cut-elimination. We show that all the structural rules in our proof system, including those rules that manipulate labels, can be localised around applications of certain logical rules, thereby localising the handling of these rules in proof search. Based on this, we demonstrate a free variable calculus that deals with the structural rules lazily in a constraint system. A heuristic method to solve the constraints is proposed in the end, with some experimental results.