OpenRaiser/Intern-Atlas huggingface dataset:
A brief survey on deep belief networks and introducing a new object oriented toolbox (DeeBNet)
Venue: arXiv cs.CV 2016
Year: 2016

Nowadays, this is very popular to use the deep architectures in machine learning. Deep Belief Networks (DBNs) are deep architectures that use stack of Restricted Boltzmann Machines (RBM) to create a powerful generative model using training data. DBNs have many ability like feature extraction and classification that are used in many applications like image processing, speech processing and etc. This paper introduces a new object oriented MATLAB toolbox with most of abilities needed for the implementation of DBNs. In the new version, the toolbox can be used in Octave. According to the results of the experiments conducted on MNIST (image), ISOLET (speech), and 20 Newsgroups (text) datasets, it was shown that the toolbox can learn automatically a good representation of the input from unlabeled data with better discrimination between different classes. Also on all datasets, the obtained classification errors are comparable to those of state of the art classifiers. In addition, the toolbox supports different sampling methods (e.g. Gibbs, CD, PCD and our new FEPCD method), different sparsity methods (quadratic, rate distortion and our new normal method), different RBM types (generative and discriminative), using GPU, etc. The toolbox is a user-friendly open source software and is freely available on the website http://ceit.aut.ac.ir/~keyvanrad/DeeBNet%20Toolbox.html .
Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends
Venue: arXiv cs.CG 2016
Year: 2016

Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straight-line drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing. In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic.
Fractional repetition codes with flexible repair from combinatorial designs
Venue: arXiv cs.IT 2016
Year: 2016

Fractional repetition (FR) codes are a class of regenerating codes for distributed storage systems with an exact (table-based) repair process that is also uncoded, i.e., upon failure, a node is regenerated by simply downloading packets from the surviving nodes. In our work, we present constructions of FR codes based on Steiner systems and resolvable combinatorial designs such as affine geometries, Hadamard designs and mutually orthogonal Latin squares. The failure resilience of our codes can be varied in a simple manner. We construct codes with normalized repair bandwidth ($β$) strictly larger than one; these cannot be obtained trivially from codes with $β= 1$. Furthermore, we present the Kronecker product technique for generating new codes from existing ones and elaborate on their properties. FR codes with locality are those where the repair degree is smaller than the number of nodes contacted for reconstructing the stored file. For these codes we establish a tradeoff between the local repair property and failure resilience and construct codes that meet this tradeoff. Much of prior work only provided lower bounds on the FR code rate. In our work, for most of our constructions we determine the code rate for certain parameter ranges.
Achievable Degrees-of-Freedom of the K-user SISO Interference Channel with Blind Interference Alignment using Staggered Antenna Switching
Venue: arXiv cs.IT 2016
Year: 2016

In this letter, we present the first characterization for the achievable Degrees-of-Freedom (DoF) by Blind Interference Alignment (BIA) using staggered antenna switching in the $K$-user Gaussian Interference Channel. In such scheme, each transmitter is equipped with one conventional antenna and each receiver is equipped with one reconfigurable (multi-mode) antenna. Assuming that the channel is known to the receivers only, we show that BIA can achieve $\frac{2K}{K+2}$ DoF, which surpasses the sum DoF achieved by previously known interference alignment schemes with delayed channel state information at transmitters (CSIT). This result implies that the sum DoF is upper bounded by 2, which means that the best we can do with BIA is to double the DoF achieved by orthogonal multiple access schemes. Moreover, we propose an algorithm to generate the transmit beamforming vectors and the reconfigurable antenna switching patterns, and apply this algorithm to the 4-user SISO Interference Channel, showing that $\frac{4}{3}$ sum DoF is achievable.
Scattered packings of cycles
Venue: arXiv cs.DM 2016
Year: 2016

We consider the problem Scattered Cycles which, given a graph $G$ and two positive integers $r$ and $\ell$, asks whether $G$ contains a collection of $r$ cycles that are pairwise at distance at least $\ell$. This problem generalizes the problem Disjoint Cycles which corresponds to the case $\ell = 1$. We prove that when parameterized by $r$, $\ell$, and the maximum degree $Δ$, the problem Scattered Cycles admits a kernel on $24 \ell^2 Δ^\ell r \log(8 \ell^2 Δ^\ell r)$ vertices. We also provide a $(16 \ell^2 Δ^\ell)$-kernel for the case $r=2$ and a $(148 Δr \log r)$-kernel for the case $\ell = 1$. Our proofs rely on two simple reduction rules and a careful analysis.
Towards Optimal Algorithms for Prediction with Expert Advice
Venue: arXiv cs.LG 2016
Year: 2016

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for $2$ and $3$ experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of $4$ experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.
The effect of a finite time horizon in the durable good monopoly problem with atomic consumers
Venue: arXiv cs.GT 2016
Year: 2016

A durable good is a long-lasting good that can be consumed repeatedly over time, and a duropolist is a monopolist in the market of a durable good. In 1972, Ronald Coase conjectured that a duropolist who lacks commitment power cannot sell the good above the competitive price if the time between periods approaches zero. Coase's counterintuitive conjecture was later proven by Gul et al. (1986) under an infinite time horizon model with non-atomic consumers. Remarkably, the situation changes dramatically for atomic consumers and an infinite time horizon. Bagnoli et al. (1989) showed the existence of a subgame-perfect Nash equilibrium where the duropolist extracts all the consumer surplus. Observe that, in these cases, duropoly profits are either arbitrarily smaller or arbitrarily larger than the corresponding static monopoly profits -- the profit a monopolist for an equivalent consumable good could generate. In this paper we show that the result of Bagnoli et al. (1989) is in fact driven by the infinite time horizon. Indeed, we prove that for finite time horizons and atomic agents, in any equilibrium satisfying the standard skimming property, duropoly profits are at most an additive factor more than static monopoly profits. In particular, duropoly profits are always at least static monopoly profits but never exceed twice the static monopoly profits. Finally we show that, for atomic consumers, equilibria may exist that do not satisfy the skimming property. For two time periods, we prove that amongst all equilibria that maximize duropoly profits, at least one of them satisfies the skimming property. We conjecture that this is true for any number of time period.
Towards a Compiler for Reals
Venue: arXiv cs.PL 2016
Year: 2016

Numerical software, common in scientific computing or embedded systems, inevitably uses an approximation of the real arithmetic in which most algorithms are designed. In many domains, roundoff errors are not the only source of inaccuracy and measurement and other input errors further increase the uncertainty of the computed results. Adequate tools are needed to help users select suitable approximations, especially for safety-critical applications. We present the source-to-source compiler Rosa which takes as input a real-valued program with error specifications and synthesizes code over an appropriate floating-point or fixed-point data type. The main challenge of such a compiler is a fully automated, sound and yet accurate enough numerical error estimation. We present a unified technique for floating-point and fixed-point arithmetic of various precisions which can handle nonlinear arithmetic, determine closed- form symbolic invariants for unbounded loops and quantify the effects of discontinuities on numerical errors. We evaluate Rosa on a number of benchmarks from scientific computing and embedded systems and, comparing it to state-of-the-art in automated error estimation, show it presents an interesting trade-off between accuracy and performance.
Measuring impact in research evaluations: A thorough discussion of methods for, effects of, and problems with impact measurements
Venue: arXiv cs.DL 2016
Year: 2016

Impact of science is one of the most important topics in scientometrics. Recent developments show a fundamental change in impact measurements from impact on science to impact on society. Since impact measurement is currently in a state of far reaching changes, this paper describes recent developments and facing problems in this area. For that the results of key publications (dealing with impact measurement) are discussed. The paper discusses how impact is generally measured within science and beyond (section 2), which effects impact measurements have on the science system (section 3), and which problems are associated with impact measurement (section 4). The problems associated with impact measurement constitute the focus of this paper: Science is marked by inequality, random chance, anomalies, the right to make mistakes, unpredictability, and a high significance of extreme events, which might distort impact measurements. Scientometricians as the producer of impact scores and decision makers as their consumers should be aware of these problems and should consider them in the generation and interpretation of bibliometric results, respectively.
Estimating Open Access Mandate Effectiveness: The MELIBEA Score
Venue: arXiv cs.DL 2016
Year: 2016

MELIBEA is a Spanish database that uses a composite formula with eight weighted conditions to estimate the effectiveness of Open Access mandates (registered in ROARMAP). We analyzed 68 mandated institutions for publication years 2011-2013 to determine how well the MELIBEA score and its individual conditions predict what percentage of published articles indexed by Web of Knowledge is deposited in each institution's OA repository, and when. We found a small but significant positive correlation (0.18) between MELIBEA score and deposit percentage. We also found that for three of the eight MELIBEA conditions (deposit timing, internal use, and opt-outs), one value of each was strongly associated with deposit percentage or deposit latency (immediate deposit required, deposit required for performance evaluation, unconditional opt-out allowed for the OA requirement but no opt-out for deposit requirement). When we updated the initial values and weights of the MELIBEA formula for mandate effectiveness to reflect the empirical association we had found, the score's predictive power doubled (.36). There are not yet enough OA mandates to test further mandate conditions that might contribute to mandate effectiveness, but these findings already suggest that it would be useful for future mandates to adopt these three conditions so as to maximize their effectiveness, and thereby the growth of OA.
Toward the Hanani-Tutte Theorem for Clustered Graphs
Venue: arXiv cs.CG 2016
Year: 2016

The weak variant of Hanani-Tutte theorem says that a graph is planar, if it can be drawn in the plane so that every pair of edges cross an even number of times. Moreover, we can turn such a drawing into an embedding without changing the order in which edges leave the vertices. We prove a generalization of the weak Hanani-Tutte theorem that also easily implies the monotone variant of the weak Hanani-Tutte theorem by Pach and Tóth. Thus, our result can be thought of as a common generalization of these two neat results. In other words, we prove the weak Hanani-Tutte theorem for strip clustered graphs, whose clusters are linearly ordered vertical strips in the plane and edges join only vertices in the same cluster or in neighboring clusters with respect to this order. In order to prove our main result we first obtain a forbidden substructure characterization of embedded strip clustered planar graphs. The Hanani-Tutte theorem says that a graph is planar, if it can be drawn in the plane so that every pair of edges not sharing a vertex cross an even number of times. We prove the variant of Hanani-Tutte theorem for strip clustered graphs if the underlying abstract graph is three connected or a tree. In the case of trees our result implies that c-planarity for flat clustered graphs with three clusters is solvable in a polynomial time if the underlying abstract graph is a tree. The proof of the latter result combines our forbidden substructure characterization of embedded strip clustered planar graphs with Tucker's characterization of 0-1 matrices with consecutive ones property.
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate
Venue: arXiv cs.PL 2016
Year: 2016

We present a new method for inferring complexity properties for a class of programs in the form of flowcharts annotated with loop information. Specifically, our method can (soundly and completely) decide if computed values are polynomially bounded as a function of the input; and similarly for the running time. Such complexity properties are undecidable for a Turing-complete programming language, and a common work-around in program analysis is to settle for sound but incomplete solutions. In contrast, we consider a class of programs that is Turing-incomplete, but strong enough to include several challenges for this kind of analysis. For a related language that has well-structured syntax, similar to Meyer and Ritchie's LOOP programs, the problem has been previously proved to be decidable. The analysis relied on the compositionality of programs, hence the challenge in obtaining similar results for flowchart programs with arbitrary control-flow graphs. Our answer to the challenge is twofold: first, we propose a class of loop-annotated flowcharts, which is more general than the class of flowcharts that directly represent structured programs; secondly, we present a technique to reuse the ideas from the work on tructured programs and apply them to such flowcharts. The technique is inspired by the classic translation of non-deterministic automata to regular expressions, but we obviate the exponential cost of constructing such an expression, obtaining a polynomial-time analysis. These ideas may well be applicable to other analysis problems.
Pipelined Iterative Solvers with Kernel Fusion for Graphics Processing Units
Venue: arXiv cs.MS 2016
Year: 2016

We revisit the implementation of iterative solvers on discrete graphics processing units and demonstrate the benefit of implementations using extensive kernel fusion for pipelined formulations over conventional implementations of classical formulations. The proposed implementations with both CUDA and OpenCL are freely available in ViennaCL and are shown to be competitive with or even superior to other solver packages for graphics processing units. Highest performance gains are obtained for small to medium-sized systems, while our implementations are on par with vendor-tuned implementations for very large systems. Our results are especially beneficial for transient problems, where many small to medium-sized systems instead of a single big system need to be solved.
ChoiceGAPs: Competitive Diffusion as a Massive Multi-Player Game in Social Networks
Venue: arXiv cs.LO 2016
Year: 2016

We consider the problem of modeling competitive diffusion in real world social networks via the notion of ChoiceGAPs which combine choice logic programs due to Sacca` and Zaniolo and Generalized Annotated Programs due to Kifer and Subrahmanian. We assume that each vertex in a social network is a player in a multi-player game (with a huge number of players) - the choice part of the ChoiceGAPs describe utilities of players for acting in various ways based on utilities of their neighbors in those and other situations. We define multi-player Nash equilibrium for such programs - but because they require some conditions that are hard to satisfy in the real world, we introduce a new model-theoretic concept of strong equilibrium. We show that stable equilibria can capture all Nash equilibria. We prove a host of complexity (intractability) results for checking existence of strong equilibria (as well as related counting complexity results), together with algorithms to find them. We then identify a class of ChoiceGAPs for which stable equilibria can be polynomially computed. We develop algorithms for computing these equilibria under various restrictions. We come up with the important concept of an estimation query which can compute quantities w.r.t. a given strong equilibrium, and approximate ranges of values (answers) across the space of strong equilibria. Even though we show that computing range answers to estimation queries exactly is intractable, we are able to identify classes of estimation queries that can be answered in polynomial time. We report on experiments we conducted with a real-world FaceBook data set surrounding the 2013 Italian election showing that our algorithms have good predictive accuracy with an Area Under a ROC Curve that, on average, is over 0.76.
Tight tradeoffs for approximating palindromes in streams
Venue: arXiv cs.DS 2016
Year: 2016

We consider computing the longest palindrome in a text of length $n$ in the streaming model, where the characters arrive one-by-one, and we do not have random access to the input. While computing the answer exactly using sublinear memory is not possible in such a setting, one can still hope for a good approximation guarantee. We focus on the two most natural variants, where we aim for either additive or multiplicative approximation of the length of the longest palindrome. We first show that there is no point in considering Las Vegas algorithms in such a setting, as they cannot achieve sublinear space complexity. For Monte Carlo algorithms, we provide a lowerbound of $Ω(\frac{n}{E})$ bits for approximating the answer with additive error $E$, and $Ω(\frac{\log n}{\log(1+\varepsilon)})$ bits for approximating the answer with multiplicative error $(1+\varepsilon)$ for the binary alphabet. Then, we construct a generic Monte Carlo algorithm, which by choosing the parameters appropriately achieves space complexity matching up to a logarithmic factor for both variants. This substantially improves the previous results by Berenbrink et al. (STACS 2014) and essentially settles the space complexity.
Online Top-k-Position Monitoring of Distributed Data Streams
Venue: arXiv cs.DS 2016
Year: 2016

Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log Δ + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where Δ is upper bounded by the largest value observed by any node.
Achievable Rates for Shaped Bit-Metric Decoding
Venue: arXiv cs.IT 2016
Year: 2016

A new achievable rate for bit-metric decoding (BMD) is derived using random coding arguments. The rate expression can be evaluated for any input distribution, and in particular the bit-levels of binary input labels can be stochastically dependent. Probabilistic shaping with dependent bit-levels (shaped BMD), shaping of independent bit-levels (bit-shaped BMD) and uniformly distributed independent bit-levels (uniform BMD) are evaluated on the additive white Gaussian noise (AWGN) channel with Gray labeled bipolar amplitude shift keying (ASK). For 32-ASK at a rate of 3.8 bits/channel use, the gap to 32-ASK capacity is 0.008 dB for shaped BMD, 0.46 dB for bit-shaped BMD, and 1.42 dB for uniform BMD. These numerical results illustrate that dependence between the bit-levels is beneficial on the AWGN channel. The relation to the LM rate and the generalized mutual information (GMI) is discussed.
On Optimum Asymptotic Multiuser Efficiency of Randomly Spread CDMA
Venue: arXiv cs.IT 2016
Year: 2016

We extend the result by Tse and Verdú on the optimum asymptotic multiuser efficiency of randomly spread CDMA with Binary Phase Shift Keying (BPSK) input. Random Gaussian and random binary antipodal spreading are considered. We obtain the optimum asymptotic multiuser efficiency of a $K$-user system with spreading gain $N$ when $K$ and $N\rightarrow\infty$ and the loading factor, $\frac{K}{N}$, grows logarithmically with $K$ under some conditions. It is shown that the optimum detector in a Gaussian randomly spread CDMA system has a performance close to the single user system at high Signal to Noise Ratio (SNR) when $K$ and $N\rightarrow\infty$ and the loading factor, $\frac{K}{N}$, is kept less than $\frac{\log_3K}{2}$. Random binary antipodal matrices are also studied and a lower bound for the optimum asymptotic multiuser efficiency is obtained. Furthermore, we investigate the connection between detecting matrices in the coin weighing problem and optimum asymptotic multiuser efficiency. We obtain a condition such that for any binary input, an $N\times K$ random matrix whose entries are chosen randomly from a finite set, is a detecting matrix as $K$ and $N\rightarrow \infty$.
Engineering Art Galleries
Venue: arXiv cs.CG 2016
Year: 2016

The Art Gallery Problem is one of the most well-known problems in Computational Geometry, with a rich history in the study of algorithms, complexity, and variants. Recently there has been a surge in experimental work on the problem. In this survey, we describe this work, show the chronology of developments, and compare current algorithms, including two unpublished versions, in an exhaustive experiment. Furthermore, we show what core algorithmic ingredients have led to recent successes.