OpenRaiser/Intern-Atlas huggingface dataset:
Randomized Frameproof Codes: Fingerprinting Plus Validation Minus Tracing
Venue: arXiv cs.IT 2008
Year: 2008

We propose randomized frameproof codes for content protection, which arise by studying a variation of the Boneh-Shaw fingerprinting problem. In the modified system, whenever a user tries to access his fingerprinted copy, the fingerprint is submitted to a validation algorithm to verify that it is indeed permissible before the content can be executed. We show an improvement in the achievable rates compared to deterministic frameproof codes and traditional fingerprinting codes. For coalitions of an arbitrary fixed size, we construct randomized frameproof codes which have an $O(n^2)$ complexity validation algorithm and probability of error $\exp(-Ω(n)),$ where $n$ denotes the length of the fingerprints. Finally, we present a connection between linear frameproof codes and minimal vectors for size-2 coalitions.
Quasi-Large Sparse-Sequence CDMA: Approach to Single-User Bound by Linearly-Complex LAS Detectors
Venue: arXiv cs.IT 2008
Year: 2008

We have proposed a quasi-large random-sequence (QLRS) CDMA where K users access a point through a common channel with spectral spreading factor N. Each bit is extended by a temporal spreading factor B and hopped on a BN-chip random sequence that is spread in time and frequency. Each user multiplexes and transmits B extended bits and the total channel load is alpha = K/N bits/s/Hz. The linearly-complex LAS detectors detect the transmitted bits. We have obtained that as B tends to infinity, if alpha < 1/2 - 1/(4ln2), each transmitted bit achieves the single-bit bound in BER in high SNR regime as if there was no interference bit. In simulation, when bit number BK >= 500, each bit can approach the single-bit bound for alpha as high as 1 bit/s/Hz. In this paper, we further propose the quasi-large sparse-sequence (QLSS) CDMA by replacing the dense sequence in QLRS-CDMA with sparse sequence. Simulation results show that when the nonzero chips are as few as 16, the BER is already near that of QLRS-CDMA while the complexity is significantly reduced due to sequence sparsity.
Automatic Verification of Correspondences for Security Protocols
Venue: arXiv cs.CR 2008
Year: 2008

We present a new technique for verifying correspondences in security protocols. In particular, correspondences can be used to formalize authentication. Our technique is fully automatic, it can handle an unbounded number of sessions of the protocol, and it is efficient in practice. It significantly extends a previous technique for the verification of secrecy. The protocol is represented in an extension of the pi calculus with fairly arbitrary cryptographic primitives. This protocol representation includes the specification of the correspondence to be verified, but no other annotation. This representation is then translated into an abstract representation by Horn clauses, which is used to prove the desired correspondence. Our technique has been proved correct and implemented. We have tested it on various protocols from the literature. The experimental results show that these protocols can be verified by our technique in less than 1 s.
Fun Boy Three Were Wrong: it is what you do, not the way that you do it
Venue: arXiv cs.HC 2008
Year: 2008

I revisit some classic publications on modularity, to show what problems its pioneers wanted to solve. These problems occur with spreadsheets too: to recognise them may help us avoid them.
On capacity of wireless ad hoc networks with MIMO MMSE receivers
Venue: arXiv cs.NI 2008
Year: 2008

Widely adopted at home, business places, and hot spots, wireless ad-hoc networks are expected to provide broadband services parallel to their wired counterparts in near future. To address this need, MIMO techniques, which are capable of offering several-fold increase in capacity, hold significant promise. Most previous work on capacity analysis of ad-hoc networks is based on an implicit assumption that each node has only one antenna. Core to the analysis therein is the characterization of a geometric area, referred to as the exclusion region, which quantizes the amount of spatial resource occupied by a link. When multiple antennas are deployed at each node, however, multiple links can transmit in the vicinity of each other simultaneously, as interference can now be suppressed by spatial signal processing. As such, a link no longer exclusively occupies a geometric area, making the concept of "exclusion region" not applicable any more. In this paper, we investigate link-layer throughput capacity of MIMO ad-hoc networks. In contrast to previous work, the amount of spatial resource occupied by each link is characterized by the actual interference it imposes on other links. To calculate the link-layer capacity, we first derive the probability distribution of post-detection SINR at a receiver. The result is then used to calculate the number of active links and the corresponding data rates that can be sustained within an area. Our analysis will serve as a guideline for the design of medium access protocols for MIMO ad-hoc networks. To the best of knowledge, this paper is the first attempt to characterize the capacity of MIMO ad-hoc networks by considering the actual PHY-layer signal and interference model.
Time Warp Edit Distance
Venue: arXiv cs.IR 2008
Year: 2008

This technical report details a family of time warp distances on the set of discrete time series. This family is constructed as an editing distance whose elementary operations apply on linear segments. A specific parameter allows controlling the stiffness of the elastic matching. It is well suited for the processing of event data for which each data sample is associated with a timestamp, not necessarily obtained according to a constant sampling rate. Some properties verified by these distances are proposed and proved in this report.
Directive words of episturmian words: equivalences and normalization
Venue: arXiv cs.DM 2008
Year: 2008

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing a common episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
Spreadsheet Structure Discovery with Logic Programming
Venue: arXiv cs.SE 2008
Year: 2008

Our term "structure discovery" denotes the recovery of structure, such as the grouping of cells, that was intended by a spreadsheet's author but is not explicit in the spreadsheet. We are implementing structure discovery tools in the logic-programming language Prolog for our spreadsheet analysis program Model Master, by writing grammars for spreadsheet structures. The objective is an "intelligent structure monitor" to run beside Excel, allowing users to reconfigure spreadsheets to the representational needs of the task at hand. This could revolutionise spreadsheet "best practice". We also describe a formulation of spreadsheet reverse-engineering based on "arrows".
Analysis of the Karmarkar-Karp Differencing Algorithm
Venue: arXiv cs.NA 2008
Year: 2008

The Karmarkar-Karp differencing algorithm is the best known polynomial time heuristic for the number partitioning problem, fundamental in both theoretical computer science and statistical physics. We analyze the performance of the differencing algorithm on random instances by mapping it to a nonlinear rate equation. Our analysis reveals strong finite size effects that explain why the precise asymptotics of the differencing solution is hard to establish by simulations. The asymptotic series emerging from the rate equation satisfies all known bounds on the Karmarkar-Karp algorithm and projects a scaling $n^{-c\ln n}$, where $c=1/(2\ln2)=0.7213...$. Our calculations reveal subtle relations between the algorithm and Fibonacci-like sequences, and we establish an explicit identity to that effect.
Some properties of the Ukrainian writing system
Venue: arXiv cs.CL 2008
Year: 2008

We investigate the grapheme-phoneme relation in Ukrainian and some properties of the Ukrainian version of the Cyrillic alphabet.
A Simple Yao-Yao-Based Spanner of Bounded Degree
Venue: arXiv cs.CG 2008
Year: 2008

It is a standing open question to decide whether the Yao-Yao structure for unit disk graphs (UDGs) is a length spanner of not. This question is highly relevant to the topology control problem for wireless ad hoc networks. In this paper we make progress towards resolving this question by showing that the Yao-Yao structure is a length spanner for UDGs of bounded aspect ratio. We also propose a new local algorithm, called Yao-Sparse-Sink, based on the Yao-Sink method introduced by Li, Wan, Wang and Frieder, that computes a (1+e)-spanner of bounded degree for a given UDG and for given e > 0. The Yao-Sparse-Sink method enables an efficient local computation of sparse sink trees. Finally, we show that all these structures for UDGs -- Yao, Yao-Yao, Yao-Sink and Yao-Sparse-Sink -- have arbitrarily large weight.
DSP Based System for Real time Voice Synthesis Applications Development
Venue: arXiv cs.SD 2008
Year: 2008

This paper describes an experimental system designed for development of real time voice synthesis applications. The system is composed from a DSP coprocessor card, equipped with an TMS320C25 or TMS320C50 chip, voice acquisition module (ADDA2),host computer (IBM-PC compatible), software specific tools.
Networks become navigable as nodes move and forget
Venue: arXiv cs.DS 2008
Year: 2008

We propose a dynamical process for network evolution, aiming at explaining the emergence of the small world phenomenon, i.e., the statistical observation that any pair of individuals are linked by a short chain of acquaintances computable by a simple decentralized routing algorithm, known as greedy routing. Previously proposed dynamical processes enabled to demonstrate experimentally (by simulations) that the small world phenomenon can emerge from local dynamics. However, the analysis of greedy routing using the probability distributions arising from these dynamics is quite complex because of mutual dependencies. In contrast, our process enables complete formal analysis. It is based on the combination of two simple processes: a random walk process, and an harmonic forgetting process. Both processes reflect natural behaviors of the individuals, viewed as nodes in the network of inter-individual acquaintances. We prove that, in k-dimensional lattices, the combination of these two processes generates long-range links mutually independently distributed as a k-harmonic distribution. We analyze the performances of greedy routing at the stationary regime of our process, and prove that the expected number of steps for routing from any source to any target in any multidimensional lattice is a polylogarithmic function of the distance between the two nodes in the lattice. Up to our knowledge, these results are the first formal proof that navigability in small worlds can emerge from a dynamical process for network evolution. Our dynamical process can find practical applications to the design of spatial gossip and resource location protocols.
The Complexity of Testing Properties of Simple Games
Venue: arXiv cs.GT 2008
Year: 2008

Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of ``yea'' votes yield passage of the issue at hand. A collection of ``yea'' voters forms a winning coalition. We are interested on performing a complexity analysis of problems on such games depending on the game representation. We consider four natural explicit representations, winning, loosing, minimal winning, and maximal loosing. We first analyze the computational complexity of obtaining a particular representation of a simple game from a different one. We show that some cases this transformation can be done in polynomial time while the others require exponential time. The second question is classifying the complexity for testing whether a game is simple or weighted. We show that for the four types of representation both problem can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. In this way, we analyze strongness, properness, decisiveness and homogeneity, which are desirable properties to be fulfilled for a simple game.
Femtocell Networks: A Survey
Venue: arXiv cs.NI 2008
Year: 2008

The surest way to increase the system capacity of a wireless link is by getting the transmitter and receiver closer to each other, which creates the dual benefits of higher quality links and more spatial reuse. In a network with nomadic users, this inevitably involves deploying more infrastructure, typically in the form of microcells, hotspots, distributed antennas, or relays. A less expensive alternative is the recent concept of femtocells, also called home base-stations, which are data access points installed by home users get better indoor voice and data coverage. In this article, we overview the technical and business arguments for femtocells, and describe the state-of-the-art on each front. We also describe the technical challenges facing femtocell networks, and give some preliminary ideas for how to overcome them.
The Future of Scientific Simulations: from Artificial Life to Artificial Cosmogenesis
Venue: arXiv cs.AI 2008
Year: 2008

This philosophical paper explores the relation between modern scientific simulations and the future of the universe. We argue that a simulation of an entire universe will result from future scientific activity. This requires us to tackle the challenge of simulating open-ended evolution at all levels in a single simulation. The simulation should encompass not only biological evolution, but also physical evolution (a level below) and cultural evolution (a level above). The simulation would allow us to probe what would happen if we would "replay the tape of the universe" with the same or different laws and initial conditions. We also distinguish between real-world and artificial-world modelling. Assuming that intelligent life could indeed simulate an entire universe, this leads to two tentative hypotheses. Some authors have argued that we may already be in a simulation run by an intelligent entity. Or, if such a simulation could be made real, this would lead to the production of a new universe. This last direction is argued with a careful speculative philosophical approach, emphasizing the imperative to find a solution to the heat death problem in cosmology. The reader is invited to consult Annex 1 for an overview of the logical structure of this paper. -- Keywords: far future, future of science, ALife, simulation, realization, cosmology, heat death, fine-tuning, physical eschatology, cosmological natural selection, cosmological artificial selection, artificial cosmogenesis, selfish biocosm hypothesis, meduso-anthropic principle, developmental singularity hypothesis, role of intelligent life.
Algebraic-geometric codes from vector bundles and their decoding
Venue: arXiv cs.IT 2008
Year: 2008

Algebraic-geometric codes can be constructed by evaluating a certain set of functions on a set of distinct rational points of an algebraic curve. The set of functions that are evaluated is the linear space of a given divisor or, equivalently, the set of section of a given line bundle. Using arbitrary rank vector bundles on algebraic curves, we propose a natural generalization of the above construction. Our codes can also be seen as interleaved versions of classical algebraic-geometric codes. We show that the algorithm of Brown, Minder and Shokrollahi can be extended to this new class of codes and it corrects any number of errors up to $t^{*} - g/2$, where $t^{*}$ is the designed correction capacity of the code and $g$ is the curve genus.
22-Step Collisions for SHA-2
Venue: arXiv cs.CR 2008
Year: 2008

In this note, we provide the first 22-step collisions for SHA-256 and SHA-512. Detailed technique of generating these collisions will be provided in the next revision of this note.
Treewidth computation and extremal combinatorics
Venue: arXiv cs.DS 2008
Year: 2008

For a given graph G and integers b,f >= 0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most n\binom{b+f}{b} such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G - compute the treewidth of G in time O(1.7549^n) by making use of exponential space and in time O(2.6151^n) and polynomial space; - decide in time O(({\frac{2n+k+1}{3})^{k+1}\cdot kn^6}) if the treewidth of G is at most k; - list all minimal separators of G in time O(1.6181^n) and all potential maximal cliques of G in time O(1.7549^n). This significantly improves previous algorithms for these problems.
NCore: Architecture and Implementation of a Flexible, Collaborative Digital Library
Venue: arXiv cs.DL 2008
Year: 2008

NCore is an open source architecture and software platform for creating flexible, collaborative digital libraries. NCore was developed by the National Science Digital Library (NSDL) project, and it serves as the central technical infrastructure for NSDL. NCore consists of a central Fedora-based digital repository, a specific data model, an API, and a set of backend services and frontend tools that create a new model for collaborative, contributory digital libraries. This paper describes NCore, presents and analyzes its architecture, tools and services; and reports on the experience of NSDL in building and operating a major digital library on it over the past year and the experience of the Digital Library for Earth Systems Education in porting their existing digital library and tools to the NCore platform.
Spatio-activity based object detection
Venue: arXiv cs.CV 2008
Year: 2008

We present the SAMMI lightweight object detection method which has a high level of accuracy and robustness, and which is able to operate in an environment with a large number of cameras. Background modeling is based on DCT coefficients provided by cameras. Foreground detection uses similarity in temporal characteristics of adjacent blocks of pixels, which is a computationally inexpensive way to make use of object coherence. Scene model updating uses the approximated median method for improved performance. Evaluation at pixel level and application level shows that SAMMI object detection performs better and faster than the conventional Mixture of Gaussians method.
Understanding Retail Productivity by Simulating Management Practise
Venue: arXiv cs.NE 2008
Year: 2008

Intelligent agents offer a new and exciting way of understanding the world of work. In this paper we apply agent-based modeling and simulation to investigate a set of problems in a retail context. Specifically, we are working to understand the relationship between human resource management practices and retail productivity. Despite the fact we are working within a relatively novel and complex domain, it is clear that intelligent agents could offer potential for fostering sustainable organizational capabilities in the future. Our research so far has led us to conduct case study work with a top ten UK retailer, collecting data in four departments in two stores. Based on our case study data we have built and tested a first version of a department store simulator. In this paper we will report on the current development of our simulator which includes new features concerning more realistic data on the pattern of footfall during the day and the week, a more differentiated view of customers, and the evolution of customers over time. This allows us to investigate more complex scenarios and to analyze the impact of various management practices.
Using Intelligent Agents to Understand Management Practices and Retail Productivity
Venue: arXiv cs.NE 2008
Year: 2008

Intelligent agents offer a new and exciting way of understanding the world of work. In this paper we apply agent-based modeling and simulation to investigate a set of problems in a retail context. Specifically, we are working to understand the relationship between human resource management practices and retail productivity. Despite the fact we are working within a relatively novel and complex domain, it is clear that intelligent agents could offer potential for fostering sustainable organizational capabilities in the future. The project is still at an early stage. So far we have conducted a case study in a UK department store to collect data and capture impressions about operations and actors within departments. Furthermore, based on our case study we have built and tested our first version of a retail branch simulator which we will present in this paper.
Investigating a Hybrid Metaheuristic For Job Shop Rescheduling
Venue: arXiv cs.NE 2008
Year: 2008

Previous research has shown that artificial immune systems can be used to produce robust schedules in a manufacturing environment. The main goal is to develop building blocks (antibodies) of partial schedules that can be used to construct backup solutions (antigens) when disturbances occur during production. The building blocks are created based upon underpinning ideas from artificial immune systems and evolved using a genetic algorithm (Phase I). Each partial schedule (antibody) is assigned a fitness value and the best partial schedules are selected to be converted into complete schedules (antigens). We further investigate whether simulated annealing and the great deluge algorithm can improve the results when hybridised with our artificial immune system (Phase II). We use ten fixed solutions as our target and measure how well we cover these specific scenarios.
Degrees of Freedom of the MIMO Interference Channel with Cooperation and Cognition
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we explore the benefits, in the sense of total (sum rate) degrees of freedom (DOF), of cooperation and cognitive message sharing for a two-user multiple-input-multiple-output (MIMO) Gaussian interference channel with $M_1$, $M_2$ antennas at transmitters and $N_1$, $N_2$ antennas at receivers. For the case of cooperation (including cooperation at transmitters only, at receivers only, and at transmitters as well as receivers), the DOF is $\min \{M_1+M_2, N_1+N_2, \max(M_1, N_2)), \max(M_2, N_1)\}$, which is the same as the DOF of the channel without cooperation. For the case of cognitive message sharing, the DOF is $\min \{M_1+M_2, N_1+N_2, (1-1_{T2})((1-1_{R2}) \max(M_1, N_2) + 1_{R2} (M_1+N_2)), (1-1_{T1})((1-1_{R1}) \max(M_2, N_1) + 1_{R1} (M_2+N_1)) \}$ where $1_{Ti} = 1$ $(0)$ when transmitter $i$ is (is not) a cognitive transmitter and $1_{Ri}$ is defined in the same fashion. Our results show that while both techniques may increase the sum rate capacity of the MIMO interference channel, only cognitive message sharing can increase the DOF. We also find that it may be more beneficial for a user to have a cognitive transmitter than to have a cognitive receiver.