OpenRaiser/Intern-Atlas huggingface dataset:
Error Correcting Coding for a Non-symmetric Ternary Channel
Venue: arXiv cs.IT 2009
Year: 2009

Ternary channels can be used to model the behavior of some memory devices, where information is stored in three different levels. In this paper, error correcting coding for a ternary channel where some of the error transitions are not allowed, is considered. The resulting channel is non-symmetric, therefore classical linear codes are not optimal for this channel. We define the maximum-likelihood (ML) decoding rule for ternary codes over this channel and show that it is complex to compute, since it depends on the channel error probability. A simpler alternative decoding rule which depends only on code properties, called $\da$-decoding, is then proposed. It is shown that $\da$-decoding and ML decoding are equivalent, i.e., $\da$-decoding is optimal, under certain conditions. Assuming $\da$-decoding, we characterize the error correcting capabilities of ternary codes over the non-symmetric ternary channel. We also derive an upper bound and a constructive lower bound on the size of codes, given the code length and the minimum distance. The results arising from the constructive lower bound are then compared, for short sizes, to optimal codes (in terms of code size) found by a clique-based search. It is shown that the proposed construction method gives good codes, and that in some cases the codes are optimal.
Firewall Configuration Errors Revisited
Venue: arXiv cs.CR 2009
Year: 2009

The first quantitative evaluation of the quality of corporate firewall configurations appeared in 2004, based on Check Point FireWall-1 rule-sets. In general that survey indicated that corporate firewalls were often enforcing poorly written rule-sets, containing many mistakes. The goal of this work is to revisit the first survey. The current study is much larger. Moreover, for the first time, the study includes configurations from two major vendors. The study also introduce a novel "Firewall Complexity" (FC) measure, that applies to both types of firewalls. The findings of the current study indeed validate the 2004 study's main observations: firewalls are (still) poorly configured, and a rule-set's complexity is (still) positively correlated with the number of detected risk items. Thus we can conclude that, for well-configured firewalls, ``small is (still) beautiful''. However, unlike the 2004 study, we see no significant indication that later software versions have fewer errors (for both vendors).
What is instrumentality in new digital msuical devices ? A contribution from cognitive linguistics and psychology
Venue: arXiv cs.HC 2009
Year: 2009

As far as music is concerned, instruments have always been part of a cultural ?landscape? (on technical, expressive and symbolic levels). The present contribution explores the changes brought about by the shift that occurred during the 20th century, from mechanical to digital instruments (also named ?virtual instruments?). First and foremost, a short recall of some historical steps of the technological developments that have renewed our relationship to sound, music, and instruments will be presented. Second, an analysis of different discourses and terminologies presently used in the domains of musicology and computer music will account for the evolution of the notion of instrumentality.
Performance Bounds for Expander-based Compressed Sensing in the presence of Poisson Noise
Venue: arXiv cs.IT 2009
Year: 2009

This paper provides performance bounds for compressed sensing in the presence of Poisson noise using expander graphs. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. In this paper, we develop a novel sensing paradigm based on expander graphs and propose a MAP algorithm for recovering sparse or compressible signals from Poisson observations. The geometry of the expander graphs and the positivity of the corresponding sensing matrices play a crucial role in establishing the bounds on the signal reconstruction error of the proposed algorithm. The geometry of the expander graphs makes them provably superior to random dense sensing matrices, such as Gaussian or partial Fourier ensembles, for the Poisson noise model. We support our results with experimental demonstrations.
Situational Method Engineering: Fundamentals and Experiences
Venue: arXiv cs.SE 2009
Year: 2009

The work presented in this paper is related to the area of Situational Method Engineering (SME) which focuses on project-specific method construction. We propose a faceted framework to understand and classify issues in system development SME. The framework identifies four different but complementary viewpoints. Each view allows us to capture a particular aspect of situational methods. Inter-relationships between these views show how they influence each other. In order to study, understand and classify a particular view of SME in its diversity, we associate a set of facets with each view. As a facet allows an in-depth description of one specific aspect of SME, the views show the variety and diversity of these aspects.
Method Chunks Selection by Multicriteria Techniques: an Extension of the Assembly-based Approach
Venue: arXiv cs.SE 2009
Year: 2009

The work presented in this paper is related to the area of situational method engineering (SME). In this domain, approaches are developed accordingly to specific project specifications. We propose to adapt an existing method construction process, namely the assembly-based one. One of the particular features of assembly-based SME approach is the selection of method chunks. Our proposal is to offer a better guidance in the retrieval of chunks by the introduction of multicriteria techniques. To use them efficiently, we defined a typology of projects characteristics, in order to identify all their critical aspects, which will offer a priorisation to help the method engineer in the choice between similar chunks.
Throughput Limits of IEEE 802.11 and IEEE 802.15.3
Venue: arXiv cs.NI 2009
Year: 2009

IEEE 802.11 and IEEE 802.15.3 are wireless standards originally designed for wireless local area network (WLAN) and wireless personal area network (WPAN). This paper studies MAC throughput analysis of both standards. We present a comparative analysis of both standards in terms of MAC throughput and bandwidth efficiency. Numerical results show that the performance of IEEE 802.15.3 transcends IEEE 802.11 in all cases.
An extendible User-Command Framework based on tagging system
Venue: arXiv cs.HC 2009
Year: 2009

Memorizing the user commands has been a problem since long. In this study we try to propose solutions to overcome two problems - the problem of selecting appropriate commands names during application development and the problem of memorizing these command names. The proposed solution includes a framework in which the applications can plug into, to get their application commands and corresponding tags in to the new command execution application.We also propose a mechanism where user can generate her own set of tags for a command and share those with peers.
Industrial-Strength Formally Certified SAT Solving
Venue: arXiv cs.LO 2009
Year: 2009

Boolean Satisfiability (SAT) solvers are now routinely used in the verification of large industrial problems. However, their application in safety-critical domains such as the railways, avionics, and automotive industries requires some form of assurance for the results, as the solvers can (and sometimes do) have bugs. Unfortunately, the complexity of modern, highly optimized SAT solvers renders impractical the development of direct formal proofs of their correctness. This paper presents an alternative approach where an untrusted, industrial-strength, SAT solver is plugged into a trusted, formally certified, SAT proof checker to provide industrial-strength certified SAT solving. The key novelties and characteristics of our approach are (i) that the checker is automatically extracted from the formal development, (ii), that the combined system can be used as a standalone executable program independent of any supporting theorem prover, and (iii) that the checker certifies any SAT solver respecting the agreed format for satisfiability and unsatisfiability claims. The core of the system is a certified checker for unsatisfiability claims that is formally designed and verified in Coq. We present its formal design and outline the correctness proofs. The actual standalone checker is automatically extracted from the the Coq development. An evaluation of the certified checker on a representative set of industrial benchmarks from the SAT Race Competition shows that, albeit it is slower than uncertified SAT checkers, it is significantly faster than certified checkers implemented on top of an interactive theorem prover.
A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem
Venue: arXiv cs.DS 2009
Year: 2009

Given a directed graph $G=(V,A)$, the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree (i.e., an out-branching) with as many leaves as possible. By designing a Branch-and-Reduced algorithm combined with the Measure & Conquer technique for running time analysis, we show that the problem can be solved in time $\Oh^*(1.9043^n)$ using polynomial space. Hitherto, there have been only few examples. Provided exponential space this run time upper bound can be lowered to $\Oh^*(1.8139^n)$.
A Robust Control Framework for Malware Filtering
Venue: arXiv cs.CR 2009
Year: 2009

We study and develop a robust control framework for malware filtering and network security. We investigate the malware filtering problem by capturing the tradeoff between increased security on one hand and continued usability of the network on the other. We analyze the problem using a linear control system model with a quadratic cost structure and develop algorithms based on H infinity-optimal control theory. A dynamic feedback filter is derived and shown via numerical analysis to be an improvement over various heuristic approaches to malware filtering. The results are verified and demonstrated with packet level simulations on the Ns-2 network simulator.
Algorithms for Quantum Branching Programs Based on Fingerprinting
Venue: arXiv cs.CC 2009
Year: 2009

In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
How Creative Should Creators Be To Optimize the Evolution of Ideas? A Computational Model
Venue: arXiv cs.AI 2009
Year: 2009

There are both benefits and drawbacks to creativity. In a social group it is not necessary for all members to be creative to benefit from creativity; some merely imitate or enjoy the fruits of others' creative efforts. What proportion should be creative? This paper contains a very preliminary investigation of this question carried out using a computer model of cultural evolution referred to as EVOC (for EVOlution of Culture). EVOC is composed of neural network based agents that evolve fitter ideas for actions by (1) inventing new ideas through modification of existing ones, and (2) imitating neighbors' ideas. The ideal proportion with respect to fitness of ideas occurs when thirty to forty percent of the individuals is creative. When creators are inventing 50% of iterations or less, mean fitness of actions in the society is a positive function of the ratio of creators to imitators; otherwise mean fitness of actions starts to drop when the ratio of creators to imitators exceeds approximately 30%. For all levels or creativity, the diversity of ideas in a population is positively correlated with the ratio of creative agents.
Memoryless Routing in Convex Subdivisions: Random Walks are Optimal
Venue: arXiv cs.CG 2009
Year: 2009

A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t, and the neighbourhood, N(v), of v. The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm A, there exists a convex subdivision on which A takes Omega(n^2) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by Bose etal (2002,2004) requires 2^{Ω(n)} time to route between some pair of vertices.
Optimal Partial Tiling of Manhattan Polyominoes
Venue: arXiv cs.DM 2009
Year: 2009

Finding an efficient optimal partial tiling algorithm is still an open problem. We have worked on a special case, the tiling of Manhattan polyominoes with dominoes, for which we give an algorithm linear in the number of columns. Some techniques are borrowed from traditional graph optimisation problems.
Sparse Eigenvectors of the Discrete Fourier Transform
Venue: arXiv cs.IT 2009
Year: 2009

We construct a basis of sparse eigenvectors for the N-dimensional discrete Fourier transform. The sparsity differs from the optimal by at most a factor of four. When N is a perfect square, the basis is orthogonal.
Environment and Planning B as a Journal: The interdisciplinarity of its environment and the citation impact
Venue: arXiv cs.DL 2009
Year: 2009

The citation impact of Environment and Planning B can be visualized using its citation relations with journals in its environment as the links of a network. The size of the nodes is varied in correspondence to the relative citation impact in this environment. Additionally, one can correct for the effect of within-journal "self"-citations. The network can be partitioned and clustered using algorithms from social network analysis. After transposing the matrix in terms of rows and columns, the citing patterns can be mapped analogously. Citing patterns reflect the activity of the community of authors who publish in the journal, while being cited indicates reception. Environment and Planning B is cited across the interface between the social sciences and the natural sciences, but its authors cite almost exclusively from the domain of the Social Science Citation Index.
Faster exponentials of power series
Venue: arXiv cs.SC 2009
Year: 2009

We describe a new algorithm for computing exp(f) where f is a power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the new algorithm costs (2.1666... + o(1)) M(n) to compute exp(f) to order n. This improves on the previous best result, namely (2.333... + o(1)) M(n).
Optimum estimation via gradients of partition functions and information measures: a statistical-mechanical perspective
Venue: arXiv cs.IT 2009
Year: 2009

In continuation to a recent work on the statistical--mechanical analysis of minimum mean square error (MMSE) estimation in Gaussian noise via its relation to the mutual information (the I-MMSE relation), here we propose a simple and more direct relationship between optimum estimation and certain information measures (e.g., the information density and the Fisher information), which can be viewed as partition functions and hence are amenable to analysis using statistical--mechanical techniques. The proposed approach has several advantages, most notably, its applicability to general sources and channels, as opposed to the I-MMSE relation and its variants which hold only for certain classes of channels (e.g., additive white Gaussian noise channels). We then demonstrate the derivation of the conditional mean estimator and the MMSE in a few examples. Two of these examples turn out to be generalizable to a fairly wide class of sources and channels. For this class, the proposed approach is shown to yield an approximate conditional mean estimator and an MMSE formula that has the flavor of a single-letter expression. We also show how our approach can easily be generalized to situations of mismatched estimation.
Some Models and Tools for Open Systems
Venue: arXiv cs.LO 2009
Year: 2009

In computer science, there is a distinction between closed systems, whose behavior is totally determined in advance, and open systems, that are systems maintaining a constant interaction with an unspecified environment. Closed systems are naturally modeled by transitions systems. Open systems have been modeled in various ways, including process algebras, I/O automata, ``modules'', and interfaces. Games provide a uniform setting in which all these models can be cast and compared. In this paper, we discuss the features and costs related to the game-based approach to open systems, referring to some of the existing models. Finally, we describe a new model of interface, called sociable interface, which is geared towards easier specification, improved reusability of models, and efficient symbolic implementation.
Re-Pair Compression of Inverted Lists
Venue: arXiv cs.IR 2009
Year: 2009

Compression of inverted lists with methods that support fast intersection operations is an active research topic. Most compression schemes rely on encoding differences between consecutive positions with techniques that favor small numbers. In this paper we explore a completely different alternative: We use Re-Pair compression of those differences. While Re-Pair by itself offers fast decompression at arbitrary positions in main and secondary memory, we introduce variants that in addition speed up the operations required for inverted list intersection. We compare the resulting data structures with several recent proposals under various list intersection algorithms, to conclude that our Re-Pair variants offer an interesting time/space tradeoff for this problem, yet further improvements are required for it to improve upon the state of the art.
Optimal strategies for computing symmetric Boolean functions in collocated networks
Venue: arXiv cs.IT 2009
Year: 2009

We address the problem of finding optimal strategies for computing Boolean symmetric functions. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements with zero error. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total bits to be communicated to perform the desired computation. We restrict attention to the class of symmetric Boolean functions, which only depend on the number of 1s among the n measurements. We define three classes of functions, namely threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and an order-optimal strategy with optimal preconstant for interval functions. Using these results, we can characterize the complexity of computing percentile type functions, which is of great interest. In our analysis, we use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools.
Flare: Architecture for rapid and easy development of Internet-based Applications
Venue: arXiv cs.NI 2009
Year: 2009

We propose an architecture, Flare, that is a structured and easy way to develop applications rapidly, in a multitude of languages, which make use of online storage of data and management of users. The architecture eliminates the need for server-side programming in most cases, creation and management of online database storage servers, re-creation of user management schemes and writing a lot of unnecessary code for accessing different web-based services using their APIs. A Web API provides a common API for various web-based services like Blogger [2], Wordpress, MSN Live, Facebook [3] etc. Access Libraries provided for major programming languages and platforms make it easy to develop applications using the Flare Web Service. We demonstrate a simple micro-blogging service developed using these APIs in two modes: a graphical browser-based mode, and a command-line mode in C++, which provide two different interfaces to the same account and data.
Co-occurrence Matrices and their Applications in Information Science: Extending ACA to the Web Environment
Venue: arXiv cs.IR 2009
Year: 2009

Co-occurrence matrices, such as co-citation, co-word, and co-link matrices, have been used widely in the information sciences. However, confusion and controversy have hindered the proper statistical analysis of this data. The underlying problem, in our opinion, involved understanding the nature of various types of matrices. This paper discusses the difference between a symmetrical co-citation matrix and an asymmetrical citation matrix as well as the appropriate statistical techniques that can be applied to each of these matrices, respectively. Similarity measures (like the Pearson correlation coefficient or the cosine) should not be applied to the symmetrical co-citation matrix, but can be applied to the asymmetrical citation matrix to derive the proximity matrix. The argument is illustrated with examples. The study then extends the application of co-occurrence matrices to the Web environment where the nature of the available data and thus data collection methods are different from those of traditional databases such as the Science Citation Index. A set of data collected with the Google Scholar search engine is analyzed using both the traditional methods of multivariate analysis and the new visualization software Pajek that is based on social network analysis and graph theory.
The Import and Export of Cognitive Science
Venue: arXiv cs.DL 2009
Year: 2009

From its inception, a large part of the motivation for Cognitive Science has been the need for an interdisciplinary journal for the study of minds and intelligent systems. One threat to the interdisciplinarity of Cognitive Science, both the field and journal, is that it may become, or already be, too dominated by psychologists. In 2005, psychology was a keyword for 51% of submissions, followed distantly by linguistics (17%), artificial intelligence (13%), neuroscience (10%), computer science (9%), and philosophy (8%). The Institute for Scientific Information (ISI) gathers data not only on how individual articles cite one another, but also on macroscopic citation patterns among journals. Journals or sets of journals can be considered as proxies for fields. As fields become established, they often create journals. By studying the patterns of citations among journals that cite and are cited by Cognitive Science, we can better: 1) appreciate the scholarly ecology surrounding the journal and the journals role within this ecology, 2) establish competitor and alternate journals, and 3) determine the natural clustering of fields related to cognitive science.