OpenRaiser/Intern-Atlas huggingface dataset:
Spam: It's Not Just for Inboxes and Search Engines! Making Hirsch h-index Robust to Scientospam
Venue: arXiv cs.DL 2008
Year: 2008

What is the 'level of excellence' of a scientist and the real impact of his/her work upon the scientific thinking and practising? How can we design a fair, an unbiased metric -- and most importantly -- a metric robust to manipulation?
Analysis and Counterexamples Regarding Yatsenko's Polynomial-Time Algorithm for Solving the Traveling Salesman Problem
Venue: arXiv cs.CC 2008
Year: 2008

Yatsenko gives a polynomial-time algorithm for solving the traveling salesman problem. We examine the correctness of the algorithm and its construction. We also comment on Yatsenko's evaluation of the algorithm.
Certifying floating-point implementations using Gappa
Venue: arXiv cs.NA 2008
Year: 2008

High confidence in floating-point programs requires proving numerical properties of final and intermediate values. One may need to guarantee that a value stays within some range, or that the error relative to some ideal value is well bounded. Such work may require several lines of proof for each line of code, and will usually be broken by the smallest change to the code (e.g. for maintenance or optimization purpose). Certifying these programs by hand is therefore very tedious and error-prone. This article discusses the use of the Gappa proof assistant in this context. Gappa has two main advantages over previous approaches: Its input format is very close to the actual C code to validate, and it automates error evaluation and propagation using interval arithmetic. Besides, it can be used to incrementally prove complex mathematical properties pertaining to the C code. Yet it does not require any specific knowledge about automatic theorem proving, and thus is accessible to a wide community. Moreover, Gappa may generate a formal proof of the results that can be checked independently by a lower-level proof assistant like Coq, hence providing an even higher confidence in the certification of the numerical code. The article demonstrates the use of this tool on a real-size example, an elementary function with correctly rounded output.
Finite-state concurrent programs can be expressed pairwise
Venue: arXiv cs.LO 2008
Year: 2008

We present a \emph{pairwise normal form} for finite-state shared memory concurrent programs: all variables are shared between exactly two processes, and the guards on transitions are conjunctions of conditions over this pairwise shared state. This representation has been used to efficiently (in polynomial time) synthesize and model-check correctness properties of concurrent programs. Our main result is that any finite state concurrent program can be transformed into pairwise normal form. Specifically, if $Q$ is an arbitrary finite-state shared memory concurrent program, then there exists a finite-state shared memory concurrent program $P$ expressed in pairwise normal form such that $P$ is strongly bisimilar to $Q$. Our result is constructive: we give an algorithm for producing $P$, given $Q$.
Impact of Errors in Operational Spreadsheets
Venue: arXiv cs.CY 2008
Year: 2008

All users of spreadsheets struggle with the problem of errors. Errors are thought to be prevalent in spreadsheets, and in some instances they have cost organizations millions of dollars. In a previous study of 50 operational spreadsheets we found errors in 0.8% to 1.8% of all formula cells, depending on how errors are defined. In the current study we estimate the quantitative impacts of errors in 25 operational spreadsheets from five different organizations. We find that many errors have no quantitative impact on the spreadsheet. Those that have an impact often affect unimportant portions of the spreadsheet. The remaining errors do sometimes have substantial impacts on key aspects of the spreadsheet. This paper provides the first fully-documented evidence on the quantitative impact of errors in operational spreadsheets.
A Constrained Channel Coding Approach to Joint Communication and Channel Estimation
Venue: arXiv cs.IT 2008
Year: 2008

A joint communication and channel state estimation problem is investigated, in which reliable information transmission over a noisy channel, and high-fidelity estimation of the channel state, are simultaneously sought. The tradeoff between the achievable information rate and the estimation distortion is quantified by formulating the problem as a constrained channel coding problem, and the resulting capacity-distortion function characterizes the fundamental limit of the joint communication and channel estimation problem. The analytical results are illustrated through case studies, and further issues such as multiple cost constraints, channel uncertainty, and capacity per unit distortion are also briefly discussed.
Increasing GP Computing Power via Volunteer Computing
Venue: arXiv cs.DC 2008
Year: 2008

This paper describes how it is possible to increase GP Computing Power via Volunteer Computing (VC) using the BOINC framework. Two experiments using well-known GP tools -Lil-gp & ECJ- are performed in order to demonstrate the benefit of using VC in terms of computing power and speed up. Finally we present an extension of the model where any GP tool or framework can be used inside BOINC regardless of its programming language, complexity or required operating system.
DSL development based on target meta-models. Using AST transformations for automating semantic analysis in a textual DSL framework
Venue: arXiv cs.PL 2008
Year: 2008

This paper describes an approach to creating textual syntax for Do- main-Specific Languages (DSL). We consider target meta-model to be the main artifact and hence to be developed first. The key idea is to represent analysis of textual syntax as a sequence of transformations. This is made by explicit opera- tions on abstract syntax trees (ATS), for which a simple language is proposed. Text-to-model transformation is divided into two parts: text-to-AST (developed by openArchitectureWare [1]) and AST-to-model (proposed by this paper). Our approach simplifies semantic analysis and helps to generate as much as possi- ble.
Factorization in categories of systems of linear partial differential equations
Venue: arXiv cs.SC 2008
Year: 2008

We start with elementary algebraic theory of factorization of linear ordinary differential equations developed in the period 1880-1930. After exposing these classical results we sketch more sophisticated algorithmic approaches developed in the last 20 years. The main part of this paper is devoted to modern generalizations of the notion of factorization to the case of systems of linear partial differential equations and their relation with explicit solvability of nonlinear partial differential equations based on some constructions from the theory of abelian categories.
A new key exchange cryptosystem
Venue: arXiv cs.CR 2008
Year: 2008

In this paper, we will present a new key exchange cryptosystem based on linear algebra, which take less operations but weaker in security than Diffie-Hellman's one.
Two graph isomorphism polytopes
Venue: arXiv cs.CC 2008
Year: 2008

The convex hull $ψ_{n,n}$ of certain $(n!)^2$ tensors was considered recently in connection with graph isomorphism. We consider the convex hull $ψ_n$ of the $n!$ diagonals among these tensors. We show: 1. The polytope $ψ_n$ is a face of $ψ_{n,n}$. 2. Deciding if a graph $G$ has a subgraph isomorphic to $H$ reduces to optimization over $ψ_n$. 3. Optimization over $ψ_n$ reduces to optimization over $ψ_{n,n}$. In particular, this implies that the subgraph isomorphism problem reduces to optimization over $ψ_{n,n}$.
Toward the Graphics Turing Scale on a Blue Gene Supercomputer
Venue: arXiv cs.GR 2008
Year: 2008

We investigate raytracing performance that can be achieved on a class of Blue Gene supercomputers. We measure a 822 times speedup over a Pentium IV on a 6144 processor Blue Gene/L. We measure the computational performance as a function of number of processors and problem size to determine the scaling performance of the raytracing calculation on the Blue Gene. We find nontrivial scaling behavior at large number of processors. We discuss applications of this technology to scientific visualization with advanced lighting and high resolution. We utilize three racks of a Blue Gene/L in our calculations which is less than three percent of the the capacity of the worlds largest Blue Gene computer.
Extensions to Network Flow Interdiction on Planar Graphs
Venue: arXiv cs.DM 2008
Year: 2008

Network flow interdiction analysis studies by how much the value of a maximum flow in a network can be diminished by removing components of the network constrained to some budget. Although this problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work we introduce pseudo-polynomial algorithms which overcome some of the restrictions of previous methods. We propose a planarity-preserving transformation that allows to incorporate vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a pseudo-polynomial algorithm is introduced for the problem of determining the minimal interdiction budget which is at least needed to make it impossible to satisfy the demand of all sink nodes, on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the source nodes equals the sum of the demands at the sink nodes. Furthermore we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers. However it is still not known if either of these problems can be solved in polynomial time.
Ideal synchronizer for marked pairs in fork-join network
Venue: arXiv cs.DM 2008
Year: 2008

We introduce a new functional element (synchronizer for marked pairs) meant to join results of parallel processing in two-branch fork-join queueing network. Approximations for distribution of sojourn time at the synchronizer are derived along with a validity domain. Calculations are performed assuming that: arrivals to the network form a Poisson process, each branch operates like an M/M/N queueing system. It is shown that mean sojourn time at a real synchronizer node is bounded below by the value, defined by parameters of the network (which contains the synchronizer) and does not depend upon performance and particular properties of the synchronizer.
Policies of System Level Pipeline Modeling
Venue: arXiv cs.AR 2008
Year: 2008

Pipelining is a well understood and often used implementation technique for increasing the performance of a hardware system. We develop several SystemC/C++ modeling techniques that allow us to quickly model, simulate, and evaluate pipelines. We employ a small domain specific language (DSL) based on resource usage patterns that automates the drudgery of boilerplate code needed to configure connectivity in simulation models. The DSL is embedded directly in the host modeling language SystemC/C++. Additionally we develop several techniques for parameterizing a pipeline's behavior based on policies of function, communication, and timing (performance modeling).
Analysis of Non-binary Hybrid LDPC Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we analyse asymptotically a new class of LDPC codes called Non-binary Hybrid LDPC codes, which has been recently introduced. We use density evolution techniques to derive a stability condition for hybrid LDPC codes, and prove their threshold behavior. We study this stability condition to conclude on asymptotic advantages of hybrid LDPC codes compared to their non-hybrid counterparts.
Decentralized Two-Hop Opportunistic Relaying With Limited Channel State Information
Venue: arXiv cs.IT 2008
Year: 2008

A network consisting of $n$ source-destination pairs and $m$ relays is considered. Focusing on the large system limit (large $n$), the throughput scaling laws of two-hop relaying protocols are studied for Rayleigh fading channels. It is shown that, under the practical constraints of single-user encoding-decoding scheme, and partial channel state information (CSI) at the transmitters (via integer-value feedback from the receivers), the maximal throughput scales as $\log n$ even if full relay cooperation is allowed. Furthermore, a novel decentralized opportunistic relaying scheme with receiver CSI, partial transmitter CSI, and no relay cooperation, is shown to achieve the optimal throughput scaling law of $\log n$.
On the Minimum Spanning Tree for Directed Graphs with Potential Weights
Venue: arXiv cs.DM 2008
Year: 2008

In general the problem of finding a miminum spanning tree for a weighted directed graph is difficult but solvable. There are a lot of differences between problems for directed and undirected graphs, therefore the algorithms for undirected graphs cannot usually be applied to the directed case. In this paper we examine the kind of weights such that the problems are equivalent and a minimum spanning tree of a directed graph may be found by a simple algorithm for an undirected graph.
Removing the Stiffness of Elastic Force from the Immersed Boundary Method for the 2D Stokes Equations
Venue: arXiv cs.CE 2008
Year: 2008

The Immersed Boundary method has evolved into one of the most useful computational methods in studying fluid structure interaction. On the other hand, the Immersed Boundary method is also known to suffer from a severe timestep stability restriction when using an explicit time discretization. In this paper, we propose several efficient semi-implicit schemes to remove this stiffness from the Immersed Boundary method for the two-dimensional Stokes flow. First, we obtain a novel unconditionally stable semi-implicit discretization for the immersed boundary problem. Using this unconditionally stable discretization as a building block, we derive several efficient semi-implicit schemes for the immersed boundary problem by applying the Small Scale Decomposition to this unconditionally stable discretization. Our stability analysis and extensive numerical experiments show that our semi-implicit schemes offer much better stability property than the explicit scheme. Unlike other implicit or semi-implicit schemes proposed in the literature, our semi-implicit schemes can be solved explicitly in the spectral space. Thus the computational cost of our semi-implicit schemes is comparable to that of an explicit scheme, but with a much better stability property.
A Truthful Mechanism for Offline Ad Slot Scheduling
Venue: arXiv cs.GT 2008
Year: 2008

We consider the "Offline Ad Slot Scheduling" problem, where advertisers must be scheduled to "sponsored search" slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. As far as we can tell, this is the first treatment of sponsored search that directly incorporates both multiple slots and budget constraints into an analysis of incentives. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence is variable over the auction. The price stops when the set of bidders that can afford that price pack exactly into a block of ad slots, at which point the mechanism allocates that block and continues on the remaining slots. To prove our result on the equilibrium of the revenue-maximizing mechanism, we first show that a greedy algorithm suffices to solve the revenue-maximizing linear program; we then use this insight to prove that bidders allocated in the same block of our mechanism have no incentive to deviate from bidding the fixed price of that block.
iBOA: The Incremental Bayesian Optimization Algorithm
Venue: arXiv cs.NE 2008
Year: 2008

This paper proposes the incremental Bayesian optimization algorithm (iBOA), which modifies standard BOA by removing the population of solutions and using incremental updates of the Bayesian network. iBOA is shown to be able to learn and exploit unrestricted Bayesian networks using incremental techniques for updating both the structure as well as the parameters of the probabilistic model. This represents an important step toward the design of competent incremental estimation of distribution algorithms that can solve difficult nearly decomposable problems scalably and reliably.
Thinking is Bad: Implications of Human Error Research for Spreadsheet Research and Practice
Venue: arXiv cs.HC 2008
Year: 2008

In the spreadsheet error community, both academics and practitioners generally have ignored the rich findings produced by a century of human error research. These findings can suggest ways to reduce errors; we can then test these suggestions empirically. In addition, research on human error seems to suggest that several common prescriptions and expectations for reducing errors are likely to be incorrect. Among the key conclusions from human error research are that thinking is bad, that spreadsheets are not the cause of spreadsheet errors, and that reducing errors is extremely difficult.
Enterprise Spreadsheet Management: A Necessary Good
Venue: arXiv cs.CY 2008
Year: 2008

This paper presents the arguments and supporting business metrics for Enterprise Spreadsheet Management to be seen as a necessary good. These arguments are divided into a summary of external business drivers that make it necessary and the good that may be delivered to business spreadsheet users involved in repetitive manual processes.
Capacity of Sparse Wideband Channels with Partial Channel Feedback
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the ergodic capacity of wideband multipath channels with limited feedback. Our work builds on recent results that have established the possibility of significant capacity gains in the wideband/low-SNR regime when there is perfect channel state information (CSI) at the transmitter. Furthermore, the perfect CSI benchmark gain can be obtained with the feedback of just one bit per channel coefficient. However, the input signals used in these methods are peaky, that is, they have a large peak-to-average power ratios. Signal peakiness is related to channel coherence and many recent measurement campaigns show that, in contrast to previous assumptions, wideband channels exhibit a sparse multipath structure that naturally leads to coherence in time and frequency. In this work, we first show that even an instantaneous power constraint is sufficient to achieve the benchmark gain when perfect CSI is available at the receiver. In the more realistic non-coherent setting, we study the performance of a training-based signaling scheme. We show that multipath sparsity can be leveraged to achieve the benchmark gain under both average as well as instantaneous power constraints as long as the channel coherence scales at a sufficiently fast rate with signal space dimensions. We also present rules of thumb on choosing signaling parameters as a function of the channel parameters so that the full benefits of sparsity can be realized.
A Recommender System based on the Immune Network
Venue: arXiv cs.NE 2008
Year: 2008

The immune system is a complex biological system with a highly distributed, adaptive and self-organising nature. This paper presents an artificial immune system (AIS) that exploits some of these characteristics and is applied to the task of film recommendation by collaborative filtering (CF). Natural evolution and in particular the immune system have not been designed for classical optimisation. However, for this problem, we are not interested in finding a single optimum. Rather we intend to identify a sub-set of good matches on which recommendations can be based. It is our hypothesis that an AIS built on two central aspects of the biological immune system will be an ideal candidate to achieve this: Antigen - antibody interaction for matching and antibody - antibody interaction for diversity. Computational results are presented in support of this conjecture and compared to those found by other CF techniques.
Partnering Strategies for Fitness Evaluation in a Pyramidal Evolutionary Algorithm
Venue: arXiv cs.NE 2008
Year: 2008

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes for (sub-)fitness evaluation purposes are examined for two multiple-choice optimisation problems. It is shown that random partnering strategies perform best by providing better sampling and more diversity.
On the Scaling Window of Model RB
Venue: arXiv cs.CC 2008
Year: 2008

This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by $r_{cr}$ or $p_{cr}$. For this model, we establish the scaling window $W(n,δ)=(r_{-}(n,δ), r_{+}(n,δ))$ such that the probability of a random instance being satisfiable is greater than $1-δ$ for $r<r_{-}(n,δ)$ and is less than $δ$ for $r>r_{+}(n,δ)$. Specifically, we obtain the following result $$W(n,δ)=(r_{cr}-Θ(\frac{1}{n^{1-ε}\ln n}), \ r_{cr}+Θ(\frac{1}{n\ln n})),$$ where $0\leqε<1$ is a constant. A similar result with respect to the other parameter $p$ is also obtained. Since the instances generated by model RB have been shown to be hard at the threshold, this is the first attempt, as far as we know, to analyze the scaling window of such a model with hard instances.
Framework for 3D TransRectal Ultrasound
Venue: arXiv cs.OH 2008
Year: 2008

Prostate biopsies are mainly performed under 2D TransRectal UltraSound (TRUS) control by sampling the prostate according to a predefined pattern. In case of first biopsies, this pattern follows a random systematic plan. Sometimes, repeat biopsies can be needed to target regions unsampled by previous biopsies or resample critical regions (for example in case of cancer expectant management or previous prostatic intraepithelial neoplasia findings). From a clinical point of view, it could be useful to control the 3D spatial distribution of theses biopsies inside the prostate. Modern 3D-TRUS probes allow acquiring high-quality volumes of the prostate in few seconds. We developed a framework to track the prostate in 3D TRUS images. It means that if one acquires a reference volume at the beginning of the session and another during each biopsy, it is possible to determine the relationship between the prostate in the reference and the others volumes by aligning images. We used this tool to evaluate the ability of a single operator (a young urologist assistant professor) to perform a pattern of 12 biopsies under 2D TRUS guidance.