OpenRaiser/Intern-Atlas huggingface dataset:
True Peer Review
Venue: arXiv cs.DL 2012
Year: 2012

In computer science, conferences and journals conduct peer review in order to decide what to publish. Many have pointed out the inherent weaknesses in peer review, including those of bias, quality, and accountability. Many have suggested and adopted refinements of peer review, for instance, double blind peer review with author rebuttals. In this essay, I argue that peer review as currently practiced conflates the sensible idea of getting comments on a paper with the irrevocably-flawed one that we either accept or reject the paper, which I term gatekeeping. If we look at the two separately, then it is clear that the ills associated with current peer review systems are not due to the practice of getting comments, but due to the practice of gatekeeping. True peer review constitutes my proposal for replacing existing peer review systems. It embraces the idea of open debate on the merits of a paper; however, it rejects unequivocally the exercise of gatekeeping. True peer review offers all the benefits of current peer review systems but has none of its weaknesses. True peer review will lead to a truly engaged community of researchers and therefore better science.
Slow Down & Sleep for Profit in Online Deadline Scheduling
Venue: arXiv cs.DS 2012
Year: 2012

We present and study a new model for energy-aware and profit-oriented scheduling on a single processor. The processor features dynamic speed scaling as well as suspension to a sleep mode. Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines. On the arrival of a new job, the scheduler may either accept or reject the job. Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values. Here, power consumption at speed $s$ is given by $P(s)=s^α+β$ and the energy investment is power integrated over time. Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs $γ$. The objective is to minimize the total value of rejected jobs plus the total energy. Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models. We show that \emph{rejection-oblivious} schedulers (whose rejection decisions are not based on former decisions) have -- in contrast to the model without sleep states -- an unbounded competitive ratio w.r.t\text{.} the processor parameters $α$ and $β$. It turns out that the worst-case performance of such schedulers depends linearly on the jobs' value densities (the ratio between a job's value and its work). We give an algorithm whose competitiveness nearly matches this lower bound. If the maximum value density is not too large, the competitiveness becomes $α^α+2eα$. Also, we show that it suffices to restrict the value density of low-value jobs only. Using a technique from \cite{Chan:2010} we transfer our results to processors with a fixed maximum speed.
Notes on random reals
Venue: arXiv cs.CC 2012
Year: 2012

The theory of random real numbers is exceedingly well-developed, and fascinating from many points of view. It is also quite challenging mathematically. The present notes are intended as no more than a gateway to the larger theory. They review just the most elementary part of the theory (bearing on Kolmogorov- and ML-randomness). We hope that the simple arguments presented here will encourage the enterprising student to examine richer treatments of the subject available elsewhere, notably, in Downey and Hirschfeldt (2010).
Control Design for Markov Chains under Safety Constraints: A Convex Approach
Venue: arXiv cs.SY 2012
Year: 2012

This paper focuses on the design of time-invariant memoryless control policies for fully observed controlled Markov chains, with a finite state space. Safety constraints are imposed through a pre-selected set of forbidden states. A state is qualified as safe if it is not a forbidden state and the probability of it transitioning to a forbidden state is zero. The main objective is to obtain control policies whose closed loop generates the maximal set of safe recurrent states, which may include multiple recurrent classes. A design method is proposed that relies on a finitely parametrized convex program inspired on entropy maximization principles. A numerical example is provided and the adoption of additional constraints is discussed.
Full Abstraction for the Resource Lambda Calculus with Tests, through Taylor Expansion
Venue: arXiv cs.LO 2012
Year: 2012

We study the semantics of a resource-sensitive extension of the lambda calculus in a canonical reflexive object of a category of sets and relations, a relational version of Scott's original model of the pure lambda calculus. This calculus is related to Boudol's resource calculus and is derived from Ehrhard and Regnier's differential extension of Linear Logic and of the lambda calculus. We extend it with new constructions, to be understood as implementing a very simple exception mechanism, and with a "must" parallel composition. These new operations allow to associate a context of this calculus with any point of the model and to prove full abstraction for the finite sub-calculus where ordinary lambda calculus application is not allowed. The result is then extended to the full calculus by means of a Taylor Expansion formula. As an intermediate result we prove that the exception mechanism is not essential in the finite sub-calculus.
Agent-based Exploration of Wirings of Biological Neural Networks: Position Paper
Venue: arXiv cs.NE 2012
Year: 2012

The understanding of human central nervous system depends on knowledge of its wiring. However, there are still gaps in our understanding of its wiring due to technical difficulties. While some information is coming out from human experiments, medical research is lacking of simulation models to put current findings together to obtain the global picture and to predict hypotheses to lead future experiments. Agent-based modeling and simulation (ABMS) is a strong candidate for the simulation model. In this position paper, we discuss the current status of "neural wiring" and "ABMS in biological systems". In particular, we discuss that the ABMS context provides features required for exploration of biological neural wiring.
Music Recommendation System for Million Song Dataset Challenge
Venue: arXiv cs.IR 2012
Year: 2012

In this paper a system that took 8th place in Million Song Dataset challenge is described. Given full listening history for 1 million of users and half of listening history for 110000 users participatints should predict the missing half. The system proposed here uses memory-based collaborative filtering approach and user-based similarity. MAP@500 score of 0.15037 was achieved.
Combining Schemes for Hybrid ARQ with Interference-Aware Successive Decoding
Venue: arXiv cs.IT 2012
Year: 2012

For decades, cellular networks have greatly evolved to support high data rates over reliable communication. Hybrid automatic-repeat-request (ARQ) is one of the techniques to make such improvement possible. However, this advancement is reduced at the cell edge where interference is not negligible. In order to overcome the challenge at the cell edge, the concept of interference-aware receiver has been recently proposed in which both desired and interference signals are successively decoded, called interference-aware successive decoding (IASD). Although IASD is the advanced receiver technology, interference signals are out of the mobile station's control so that they cannot be requested by the mobile station. For this reason, this paper proposes new combining schemes for the IASD receiver, which operate with hybrid ARQ in a bit level or in a symbol level. In addition, this paper compares the memory requirement among the proposed combining schemes and analyzes the impact of discrete modulation on the proposed scheme. Simulation results presents the superiority of the proposed combining schemes and shows the improvement in terms of the number of transmission.
Expander-like Codes based on Finite Projective Geometry
Venue: arXiv cs.IT 2012
Year: 2012

We present a novel error correcting code and decoding algorithm which have construction similar to expander codes. The code is based on a bipartite graph derived from the subsumption relations of finite projective geometry, and Reed-Solomon codes as component codes. We use a modified version of well-known Zemor's decoding algorithm for expander codes, for decoding our codes. By derivation of geometric bounds rather than eigenvalue bounds, it has been proved that for practical values of the code rate, the random error correction capability of our codes is much better than those derived for previously studied graph codes, including Zemor's bound. MATLAB simulations further reveal that the average case performance of this code is 10 times better than these geometric bounds obtained, in almost 99% of the test cases. By exploiting the symmetry of projective space lattices, we have designed a corresponding decoder that has optimal throughput. The decoder design has been prototyped on Xilinx Virtex 5 FPGA. The codes are designed for potential applications in secondary storage media. As an application, we also discuss usage of these codes to improve the burst error correction capability of CD-ROM decoder.
SSL Enhancement
Venue: arXiv cs.CR 2012
Year: 2012

With the development of e-commerce, ssl protocol is more and more widely applied to various network services. It is one of key technologies to keep user's data in secure transmission via internet. This document majorly focuses on "SSLStrip" which generates the most recent attack in the secure network connections. It strips out all the secure connections to unsecure plain connection. In this article we depict this attack and to nullify it, we have proposed a technique cum practical solution to strengthen data security by developing mozilla-firefox add-on and servlet code which will strengthen our defense against the https hijacking attacks.
A short note on the kissing number of the lattice in Gaussian wiretap coding
Venue: arXiv cs.CR 2012
Year: 2012

We show that on an $n=24m+8k$-dimensional even unimodular lattice, if the shortest vector length is $\geq 2m$, then as the number of vectors of length $2m$ decreases, the secrecy gain increases. We will also prove a similar result on general unimodular lattices. Furthermore, assuming the conjecture by Belfiore and Solé, we will calculate the difference between inverses of secrecy gains as the number of vectors varies. Finally, we will show by an example that there exist two lattices in the same dimension with the same shortest vector length and the same kissing number, but different secrecy gains.
Strategy complexity of finite-horizon Markov decision processes and simple stochastic games
Venue: arXiv cs.GT 2012
Year: 2012

Markov decision processes (MDPs) and simple stochastic games (SSGs) provide a rich mathematical framework to study many important problems related to probabilistic systems. MDPs and SSGs with finite-horizon objectives, where the goal is to maximize the probability to reach a target state in a given finite time, is a classical and well-studied problem. In this work we consider the strategy complexity of finite-horizon MDPs and SSGs. We show that for all $ε>0$, the natural class of counter-based strategies require at most $\log \log (\frac{1}ε) + n+1$ memory states, and memory of size $Ω(\log \log (\frac{1}ε) + n)$ is required. Thus our bounds are asymptotically optimal. We then study the periodic property of optimal strategies, and show a sub-exponential lower bound on the period for optimal strategies.
A Resource Intensive Traffic-Aware Scheme for Cluster-based Energy Conservation in Wireless Devices
Venue: arXiv cs.DC 2012
Year: 2012

Wireless traffic that is destined for a certain device in a network, can be exploited in order to minimize the availability and delay trade-offs, and mitigate the Energy consumption. The Energy Conservation (EC) mechanism can be node-centric by considering the traversed nodal traffic in order to prolong the network lifetime. This work describes a quantitative traffic-based approach where a clustered Sleep-Proxy mechanism takes place in order to enable each node to sleep according to the time duration of the active traffic that each node expects and experiences. Sleep-proxies within the clusters are created according to pairwise active-time comparison, where each node expects during the active periods, a requested traffic. For resource availability and recovery purposes, the caching mechanism takes place in case where the node for which the traffic is destined is not available. The proposed scheme uses Role-based nodes which are assigned to manipulate the traffic in a cluster, through the time-oriented backward difference traffic evaluation scheme. Simulation study is carried out for the proposed backward estimation scheme and the effectiveness of the end-to-end EC mechanism taking into account a number of metrics and measures for the effects while incrementing the sleep time duration under the proposed framework. Comparative simulation results show that the proposed scheme could be applied to infrastructure-less systems, providing energy-efficient resource exchange with significant minimization in the power consumption of each device.
Qualitative Modelling via Constraint Programming: Past, Present and Future
Venue: arXiv cs.CE 2012
Year: 2012

Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
How Many Potatoes are in a Mesh?
Venue: arXiv cs.DM 2012
Year: 2012

We consider the combinatorial question of how many convex polygons can be made by using the edges taken from a fixed triangulation of n vertices. For general triangulations, there can be exponentially many: we show a construction that has Omega(1.5028^n) convex polygons, and prove an O(1.62^n) upper bound in the worst case. If the triangulation is fat (every triangle has its angles lower-bounded by a constant delta>0), then there can be only polynomially many. We also consider the problem of counting convex outerplanar polygons (i.e., they contain no vertices of the triangulation in their interiors) in the same triangulations. In this setting, we get the same exponential bounds in general triangulations, and lower polynomial bounds in fat triangulations. If the triangulation is furthermore compact (the ratio between the longest and shortest distance between any two vertices is bounded), the bounds drop further to Theta (n^2) for general convex outerplanar polygons, and Theta (n) for fat convex outerplanar polygons.
A New Model of the Lifetime of Wireless Sensor Networks in Sea Water Communications
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we present a new model for the lifetime of wireless sensor networks used for sea water communications. The new model for power communications takes into consideration parameters such as power consumption for the active mode, power consumption for the sleep mode, power consumption for the transient mode, transmission period, transient mode duration, sleep mode duration, and active mode duration. The power communications model is incorporated in the life time model of wireless sensor networks. The life time model takes into consideration several parameters such as the total number of sensors, network size, percentage of sink nodes, location of sensors, the mobility of sensors, power consumption when nodes move and the power consumption of communications. The new model for power consumption in communications shows more accurate results about the lifetime of the sensor network in comparison with previously published results.
Edge Routing with Ordered Bundles
Venue: arXiv cs.CG 2012
Year: 2012

Edge bundling reduces the visual clutter in a drawing of a graph by uniting the edges into bundles. We propose a method of edge bundling drawing each edge of a bundle separately as in metro-maps and call our method ordered bundles. To produce aesthetically looking edge routes it minimizes a cost function on the edges. The cost function depends on the ink, required to draw the edges, the edge lengths, widths and separations. The cost also penalizes for too many edges passing through narrow channels by using the constrained Delaunay triangulation. The method avoids unnecessary edge-node and edge-edge crossings. To draw edges with the minimal number of crossings and separately within the same bundle we develop an efficient algorithm solving a variant of the metro-line crossing minimization problem. In general, the method creates clear and smooth edge routes giving an overview of the global graph structure, while still drawing each edge separately and thus enabling local analysis.
The Capacity of the Gaussian Cooperative Two-user Multiple Access Channel to within a Constant Gap
Venue: arXiv cs.IT 2012
Year: 2012

The capacity region of the cooperative two-user Multiple Access Channel (MAC) in Gaussian noise is determined to within a constant gap for both the Full-Duplex (FD) and Half-Duplex (HD) case. The main contributions are: (a) for both FD and HD: unilateral cooperation suffices to achieve capacity to within a constant gap where only the user with the strongest link to the destination needs to engage in cooperation, (b) for both FD and HD: backward joint decoding is not necessary to achieve capacity to within a constant gap, and (c) for HD: time sharing between the case where the two users do not cooperate and the case where the user with the strongest link to the destination acts as pure relay for the other user suffices to achieve capacity to within a constant gap. These findings show that simple achievable strategies are approximately optimal for all channel parameters with interesting implications for practical cooperative schemes.
Linear-use CPS translations in the Enriched Effect Calculus
Venue: arXiv cs.LO 2012
Year: 2012

The enriched effect calculus (EEC) is an extension of Moggi's computational metalanguage with a selection of primitives from linear logic. This paper explores the enriched effect calculus as a target language for continuation-passing-style (CPS) translations in which the typing of the translations enforces the linear usage of continuations. We first observe that established call-by-value and call-by name linear-use CPS translations of simply-typed lambda-calculus into intuitionistic linear logic (ILL) land in the fragment of ILL given by EEC. These two translations are uniformly generalised by a single generic translation of the enriched effect calculus into itself. As our main theorem, we prove that the generic self-translation of EEC is involutive up to isomorphism. As corollaries, we obtain full completeness results, both for the generic translation, and for the original call-by-value and call-by-name translations.
Parallel Semi-Implicit Time Integrators
Venue: arXiv cs.DC 2012
Year: 2012

In this paper, we further develop a family of parallel time integrators known as Revisionist Integral Deferred Correction methods (RIDC) to allow for the semi-implicit solution of time dependent PDEs. Additionally, we show that our semi-implicit RIDC algorithm can harness the computational potential of multiple general purpose graphical processing units (GPUs) in a single node by utilizing existing CUBLAS libraries for matrix linear algebra routines in our implementation. In the numerical experiments, we show that our implementation computes a fourth order solution using four GPUs and four CPUs in approximately the same wall clock time as a first order solution computed using a single GPU and a single CPU.
On Cyclic DNA Codes
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers cyclic DNA codes of arbitrary length over the ring $R=\F_2[u]/u^4-1$. A mapping is given between the elements of $R$ and the alphabet $\{A,C,G,T\}$ which allows the additive stem distance to be extended to this ring. Cyclic codes over $R$ are designed such that their images under the mapping are also cyclic or quasi-cyclic of index 2. The additive distance and hybridization energy are functions of the neighborhood energy.
Sparsification of Motion-Planning Roadmaps by Edge Contraction
Venue: arXiv cs.RO 2012
Year: 2012

We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction - the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.
Deterministic algorithms for skewed matrix products
Venue: arXiv cs.DS 2012
Year: 2012

Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new {\em deterministic} matrix multiplication algorithms. Motivated by applications in data mining, we first consider the case of real-valued, nonnegative $n$-by-$n$ input matrices $A$ and $B$, and show how to obtain a deterministic approximation of the weights of individual entries, as well as the entrywise $p$-norm, of the product $AB$. The algorithm is simple, space efficient and runs in one pass over the input matrices. For a user defined $b \in (0, n^2)$ the algorithm runs in time $O(nb + n\cdot\text{Sort}(n))$ and space $O(n + b)$ and returns an approximation of the entries of $AB$ within an additive factor of $\|AB\|_{E1}/b$, where $\|C\|_{E1} = \sum_{i, j} |C_{ij}|$ is the entrywise 1-norm of a matrix $C$ and $\text{Sort}(n)$ is the time required to sort $n$ real numbers in linear space. Building upon a result by Berinde et al. we show that for skewed matrix products (a common situation in many real-life applications) the algorithm is more efficient and achieves better approximation guarantees than previously known randomized algorithms. When the input matrices are not restricted to nonnegative entries, we present a new deterministic group testing algorithm detecting nonzero entries in the matrix product with large absolute value. The algorithm is clearly outperformed by randomized matrix multiplication algorithms, but as a byproduct we obtain the first $O(n^{2 + \varepsilon})$-time deterministic algorithm for matrix products with $O(\sqrt{n})$ nonzero entries.