OpenRaiser/Intern-Atlas huggingface dataset:
Dynamics, robustness and fragility of trust
Venue: arXiv cs.CR 2008
Year: 2008

Trust is often conveyed through delegation, or through recommendation. This makes the trust authorities, who process and publish trust recommendations, into an attractive target for attacks and spoofing. In some recent empiric studies, this was shown to lead to a remarkable phenomenon of *adverse selection*: a greater percentage of unreliable or malicious web merchants were found among those with certain types of trust certificates, then among those without. While such findings can be attributed to a lack of diligence in trust authorities, or even to conflicts of interest, our analysis of trust dynamics suggests that public trust networks would probably remain vulnerable even if trust authorities were perfectly diligent. The reason is that the process of trust building, if trust is not breached too often, naturally leads to power-law distributions: the rich get richer, the trusted attract more trust. The evolutionary processes with such distributions, ubiquitous in nature, are known to be robust with respect to random failures, but vulnerable to adaptive attacks. We recommend some ways to decrease the vulnerability of trust building, and suggest some ideas for exploration.
Ranking Catamorphisms and Unranking Anamorphisms on Hereditarily Finite Datatypes
Venue: arXiv cs.SC 2008
Year: 2008

Using specializations of unfold and fold on a generic tree data type we derive unranking and ranking functions providing natural number encodings for various Hereditarily Finite datatypes. In this context, we interpret unranking operations as instances of a generic anamorphism and ranking operations as instances of the corresponding catamorphism. Starting with Ackerman's Encoding from Hereditarily Finite Sets to Natural Numbers we define pairings and tuple encodings that provide building blocks for a theory of Hereditarily Finite Functions. The more difficult problem of ranking and unranking Hereditarily Finite Permutations is then tackled using Lehmer codes and factoradics. The self-contained source code of the paper, as generated from a literate Haskell program, is available at \url{http://logic.csci.unt.edu/tarau/research/2008/fFUN.zip}. Keywords: ranking/unranking, pairing/tupling functions, Ackermann encoding, hereditarily finite sets, hereditarily finite functions, permutations and factoradics, computational mathematics, Haskell data representations
Capacity Regions and Bounds for a Class of Z-interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

We define a class of Z-interference channels for which we obtain a new upper bound on the capacity region. The bound exploits a technique first introduced by Korner and Marton. A channel in this class has the property that, for the transmitter-receiver pair that suffers from interference, the conditional output entropy at the receiver is invariant with respect to the transmitted codewords. We compare the new capacity region upper bound with the Han/Kobayashi achievable rate region for interference channels. This comparison shows that our bound is tight in some cases, thereby yielding specific points on the capacity region as well as sum capacity for certain Z-interference channels. In particular, this result can be used as an alternate method to obtain sum capacity of Gaussian Z-interference channels. We then apply an additional restriction on our channel class: the transmitter-receiver pair that suffers from interference achieves its maximum output entropy with a single input distribution irrespective of the interference distribution. For these channels we show that our new capacity region upper bound coincides with the Han/Kobayashi achievable rate region, which is therefore capacity-achieving. In particular, for these channels superposition encoding with partial decoding is shown to be optimal and a single-letter characterization for the capacity region is obtained.
Policy and Legal Challenges of Virtual Worlds and Social Network Sites
Venue: arXiv cs.CY 2008
Year: 2008

This paper addresses policy challenges of complex virtual environments such as virtual worlds, social network sites, and massive multiplayer online games. The complexity of these environments--apparent by the rich user interactions and sophisticated user-generated content that they offer--poses unique challenges for policy management and compliance. These challenges are also impacting the life cycle of the software system that implements the virtual environment. The goal of this paper is to identify and sketch important legal and policy challenges of virtual environments and how they affect stakeholders (i.e., operators, users, and lawmakers). Given the increasing significance of virtual environments, we expect that tackling these challenges will become increasingly important in the future.
Encompression Using Two-dimensional Cellular Automata Rules
Venue: arXiv cs.DM 2008
Year: 2008

In this paper, we analyze the algebraic structure of some null boundary as well as some periodic boundary 2-D Cellular Automata (CA) rules by introducing a new matrix multiplication operation using only AND, OR instead of most commonly used AND, EX-OR. This class includes any CA whose rule, when written as an algebra, is a finite Abelean cyclic group in case of periodic boundary and a finite commutative cyclic monoid in case of null boundary CA respectively. The concept of 1-D Multiple Attractor Cellular Automata (MACA) is extended to 2-D. Using the family of 2-D MACA and the finite Abelian cyclic group, an efficient encompression algorithm is proposed for binary images.
The finite harmonic oscillator and its applications to sequences, communication and radar
Venue: arXiv cs.IT 2008
Year: 2008

A novel system, called the oscillator system, consisting of order of p^3 functions (signals) on the finite field F_p; with p an odd prime, is described and studied. The new functions are proved to satisfy good auto-correlation, cross-correlation and low peak-to-average power ratio properties. Moreover, the oscillator system is closed under the operation of discrete Fourier transform. Applications of the oscillator system for discrete radar and digital communication theory are explained. Finally, an explicit algorithm to construct the oscillator system is presented.
Algorithmic Pricing via Virtual Valuations
Venue: arXiv cs.GT 2008
Year: 2008

Algorithmic pricing is the computational problem that sellers (e.g., in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami et al. (2005) propose this problem and give logarithmic approximations (in the number of consumers) when each consumer's values for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic inapproximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter settings; however, logarithmic approximations are inadequate for this purpose. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this problem. Here a consumer has a valuation for each different item and their value for a set of items is simply the maximum value they have for any item in the set. We assume that the preferences of the consumers are drawn from a distribution, the standard assumption in economics; furthermore, the setting of a specific set of customers with known preferences, which is employed in all prior work in algorithmic pricing, is a special case of this general problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.
A Very Efficient Scheme for Estimating Entropy of Data Streams Using Compressed Counting
Venue: arXiv cs.DS 2008
Year: 2008

Compressed Counting (CC)} was recently proposed for approximating the $α$th frequency moments of data streams, for $0<α\leq 2$. Under the relaxed strict-Turnstile model, CC dramatically improves the standard algorithm based on symmetric stable random projections}, especially as $α\to 1$. A direct application of CC is to estimate the entropy, which is an important summary statistic in Web/network measurement and often serves a crucial "feature" for data mining. The Rényi entropy and the Tsallis entropy are functions of the $α$th frequency moments; and both approach the Shannon entropy as $α\to 1$. A recent theoretical work suggested using the $α$th frequency moment to approximate the Shannon entropy with $α=1+δ$ and very small $|δ|$ (e.g., $<10^{-4}$). In this study, we experiment using CC to estimate frequency moments, Rényi entropy, Tsallis entropy, and Shannon entropy, on real Web crawl data. We demonstrate the variance-bias trade-off in estimating Shannon entropy and provide practical recommendations. In particular, our experiments enable us to draw some important conclusions: (1) As $α\to 1$, CC dramatically improves {\em symmetric stable random projections} in estimating frequency moments, Rényi entropy, Tsallis entropy, and Shannon entropy. The improvements appear to approach "infinity." (2) Using {\em symmetric stable random projections} and $α= 1+δ$ with very small $|δ|$ does not provide a practical algorithm because the required sample size is enormous.
Correctness is not enough
Venue: arXiv cs.SE 2008
Year: 2008

The usual aim of spreadsheet audit is to verify correctness. There are two problems with this: first, it is often difficult to tell whether the spreadsheets in question are correct, and second, even if they are, they may still give the wrong results. These problems are explained in this paper, which presents the key criteria for judging a spreadsheet and discusses how those criteria can be achieved
Lower Bounds on the Rate-Distortion Function of LDGM Codes
Venue: arXiv cs.IT 2008
Year: 2008

A recent line of work has focused on the use of low-density generator matrix (LDGM) codes for lossy source coding. In this paper, wedevelop a generic technique for deriving lower bounds on the rate-distortion functions of binary linear codes, with particular interest on the effect of bounded degrees. The underlying ideas can be viewing as the source coding analog of the classical result of Gallager, providing bounds for channel coding over the binary symmetric channel using bounded degree LDPC codes. We illustrate this method for different random ensembles of LDGM codes, including the check-regular ensemble and bit-check-regular ensembles, by deriving explicit lower bounds on their rate-distortion performance as a function of the degrees.
Networking in the Physical World
Venue: arXiv cs.NI 2008
Year: 2008

In this work we propose a network meta-architecture based on fundamental laws of physics and a physical model of computation. This meta-architecture may be used to frame discussions about novel network architectures as well as cross-layer alterations to the canonical network stack.
Distributed Source Coding using Abelian Group Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this work, we consider a distributed source coding problem with a joint distortion criterion depending on the sources and the reconstruction. This includes as a special case the problem of computing a function of the sources to within some distortion and also the classic Slepian-Wolf problem, Berger-Tung problem, Wyner-Ziv problem, Yeung-Berger problem and the Ahlswede-Korner-Wyner problem. While the prevalent trend in information theory has been to prove achievability results using Shannon's random coding arguments, using structured random codes offer rate gains over unstructured random codes for many problems. Motivated by this, we present a new achievable rate-distortion region for this problem for discrete memoryless sources based on "good" structured random nested codes built over abelian groups. We demonstrate rate gains for this problem over traditional coding schemes using random unstructured codes. For certain sources and distortion functions, the new rate region is strictly bigger than the Berger-Tung rate region, which has been the best known achievable rate region for this problem till now. Further, there is no known unstructured random coding scheme that achieves these rate gains. Achievable performance limits for single-user source coding using abelian group codes are also obtained as parts of the proof of the main coding theorem. As a corollary, we also prove that nested linear codes achieve the Shannon rate-distortion bound in the single-user setting.
Accelerating Scientific Computations with Mixed Precision Algorithms
Venue: arXiv cs.MS 2008
Year: 2008

On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. The approach presented here can apply not only to conventional processors but also to other technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the STI Cell BE processor. Results on modern processor architectures and the STI Cell BE are presented.
Investigation of the Zipf-plot of the extinct Meroitic language
Venue: arXiv cs.CL 2008
Year: 2008

The ancient and extinct language Meroitic is investigated using Zipf's Law. In particular, since Meroitic is still undeciphered, the Zipf law analysis allows us to assess the quality of current texts and possible avenues for future investigation using statistical techniques.
Building an interpretable fuzzy rule base from data using Orthogonal Least Squares Application to a depollution problem
Venue: arXiv cs.LG 2008
Year: 2008

In many fields where human understanding plays a crucial role, such as bioprocesses, the capacity of extracting knowledge from data is of critical importance. Within this framework, fuzzy learning methods, if properly used, can greatly help human experts. Amongst these methods, the aim of orthogonal transformations, which have been proven to be mathematically robust, is to build rules from a set of training data and to select the most important ones by linear regression or rank revealing techniques. The OLS algorithm is a good representative of those methods. However, it was originally designed so that it only cared about numerical performance. Thus, we propose some modifications of the original method to take interpretability into account. After recalling the original algorithm, this paper presents the changes made to the original method, then discusses some results obtained from benchmark problems. Finally, the algorithm is applied to a real-world fault detection depollution problem.
Analysis of the postulates produced by Karp's Theorem
Venue: arXiv cs.CC 2008
Year: 2008

This is the final article in a series of four articles. Richard Karp has proven that a deterministic polynomial time solution to K-SAT will result in a deterministic polynomial time solution to all NP-Complete problems. However, it is demonstrated that a deterministic polynomial time solution to any NP-Complete problem does not necessarily produce a deterministic polynomial time solution to all NP-Complete problems.
Codes on hypergraphs
Venue: arXiv cs.IT 2008
Year: 2008

Codes on hypergraphs are an extension of the well-studied family of codes on bipartite graphs. Bilu and Hoory (2004) constructed an explicit family of codes on regular t-partite hypergraphs whose minimum distance improves earlier estimates of the distance of bipartite-graph codes. They also suggested a decoding algorithm for such codes and estimated its error-correcting capability. In this paper we study two aspects of hypergraph codes. First, we compute the weight enumerators of several ensembles of such codes, establishing conditions under which they attain the Gilbert-Varshamov bound and deriving estimates of their distance. In particular, we show that this bound is attained by codes constructed on a fixed bipartite graph with a large spectral gap. We also suggest a new decoding algorithm of hypergraph codes that corrects a constant fraction of errors, improving upon the algorithm of Bilu and Hoory.
On the Growth Rate of the Weight Distribution of Irregular Doubly-Generalized LDPC Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, an expression for the asymptotic growth rate of the number of small linear-weight codewords of irregular doubly-generalized LDPC (D-GLDPC) codes is derived. The expression is compact and generalizes existing results for LDPC and generalized LDPC (GLDPC) codes. Assuming that there exist check and variable nodes with minimum distance 2, it is shown that the growth rate depends only on these nodes. An important connection between this new result and the stability condition of D-GLDPC codes over the BEC is highlighted. Such a connection, previously observed for LDPC and GLDPC codes, is now extended to the case of D-GLDPC codes.
Towards Loosely-Coupled Programming on Petascale Systems
Venue: arXiv cs.DC 2008
Year: 2008

We have extended the Falkon lightweight task execution framework to make loosely coupled programming on petascale systems a practical and useful programming model. This work studies and measures the performance factors involved in applying this approach to enable the use of petascale systems by a broader user community, and with greater ease. Our work enables the execution of highly parallel computations composed of loosely coupled serial jobs with no modifications to the respective applications. This approach allows a new-and potentially far larger-class of applications to leverage petascale systems, such as the IBM Blue Gene/P supercomputer. We present the challenges of I/O performance encountered in making this model practical, and show results using both microbenchmarks and real applications from two domains: economic energy modeling and molecular dynamics. Our benchmarks show that we can scale up to 160K processor-cores with high efficiency, and can achieve sustained execution rates of thousands of tasks per second.
Realizing Fast, Scalable and Reliable Scientific Computations in Grid Environments
Venue: arXiv cs.DC 2008
Year: 2008

The practical realization of managing and executing large scale scientific computations efficiently and reliably is quite challenging. Scientific computations often involve thousands or even millions of tasks operating on large quantities of data, such data are often diversely structured and stored in heterogeneous physical formats, and scientists must specify and run such computations over extended periods on collections of compute, storage and network resources that are heterogeneous, distributed and may change constantly. We present the integration of several advanced systems: Swift, Karajan, and Falkon, to address the challenges in running various large scale scientific applications in Grid environments. Swift is a parallel programming tool for rapid and reliable specification, execution, and management of large-scale science and engineering workflows. Swift consists of a simple scripting language called SwiftScript and a powerful runtime system that is based on the CoG Karajan workflow engine and integrates the Falkon light-weight task execution service that uses multi-level scheduling and a streamlined dispatcher. We showcase the scalability, performance and reliability of the integrated system using application examples drawn from astronomy, cognitive neuroscience and molecular dynamics, which all comprise large number of fine-grained jobs. We show that Swift is able to represent dynamic workflows whose structures can only be determined during runtime and reduce largely the code size of various workflow representations using SwiftScript; schedule the execution of hundreds of thousands of parallel computations via the Karajan engine; and achieve up to 90% reduction in execution time when compared to traditional batch schedulers.
Flow Faster: Efficient Decision Algorithms for Probabilistic Simulations
Venue: arXiv cs.LO 2008
Year: 2008

Strong and weak simulation relations have been proposed for Markov chains, while strong simulation and strong probabilistic simulation relations have been proposed for probabilistic automata. However, decision algorithms for strong and weak simulation over Markov chains, and for strong simulation over probabilistic automata are not efficient, which makes it as yet unclear whether they can be used as effectively as their non-probabilistic counterparts. This paper presents drastically improved algorithms to decide whether some (discrete- or continuous-time) Markov chain strongly or weakly simulates another, or whether a probabilistic automaton strongly simulates another. The key innovation is the use of parametric maximum flow techniques to amortize computations. We also present a novel algorithm for deciding strong probabilistic simulation preorders on probabilistic automata, which has polynomial complexity via a reduction to an LP problem. When extending the algorithms for probabilistic automata to their continuous-time counterpart, we retain the same complexity for both strong and strong probabilistic simulations.
Free and Open Source Software for Development
Venue: arXiv cs.GL 2008
Year: 2008

Development organizations and International Non-Governmental Organizations have been emphasizing the high potential of Free and Open Source Software for the Less Developed Countries. Cost reduction, less vendor dependency and increased potential for local capacity development have been their main arguments. In spite of its advantages, Free and Open Source Software is not widely adopted at the African continent. In this book the authors will explore the grounds on with these expectations are based. Where do they come from and is there evidence to support these expectations? Over the past years several projects have been initiated and some good results have been achieved, but at the same time many challenges were encountered. What lessons can be drawn from these experiences and do these experiences contain enough evidence to support the high expectations? Several projects and their achievements will be considered. In the final part of the book the future of Free and Open Source Software for Development will be explored. Special attention is given to the African continent since here challenges are highest. What is the role of Free and open Source Software for Development and how do we need to position and explore the potential? What are the threats? The book aims at professionals that are engaged in the design and implementation of ICT for Development (ICT4D) projects and want to improve their understanding of the role Free and Open Source Software can play.