OpenRaiser/Intern-Atlas huggingface dataset:
Space-time codes with controllable ML decoding complexity for any number of transmit antennas
Venue: arXiv cs.IT 2007
Year: 2007

We construct a class of linear space-time block codes for any number of transmit antennas that have controllable ML decoding complexity with a maximum rate of 1 symbol per channel use. The decoding complexity for $M$ transmit antennas can be varied from ML decoding of $2^{\lceil \log_2M \rceil -1}$ symbols together to single symbol ML decoding. For ML decoding of $2^{\lceil \log_2M \rceil - n}$ ($n=1,2,...$) symbols together, a diversity of $\min(M,2^{\lceil \log_2M \rceil-n+1})$ can be achieved. Numerical results show that the performance of the constructed code when $2^{\lceil \log_2M \rceil-1}$ symbols are decoded together is quite close to the performance of ideal rate-1 orthogonal codes (that are non-existent for more than 2 transmit antennas).
Complex networks and human language
Venue: arXiv cs.CL 2007
Year: 2007

This paper introduces how human languages can be studied in light of recent development of network theories. There are two directions of exploration. One is to study networks existing in the language system. Various lexical networks can be built based on different relationships between words, being semantic or syntactic. Recent studies have shown that these lexical networks exhibit small-world and scale-free features. The other direction of exploration is to study networks of language users (i.e. social networks of people in the linguistic community), and their role in language evolution. Social networks also show small-world and scale-free features, which cannot be captured by random or regular network models. In the past, computational models of language change and language emergence often assume a population to have a random or regular structure, and there has been little discussion how network structures may affect the dynamics. In the second part of the paper, a series of simulation models of diffusion of linguistic innovation are used to illustrate the importance of choosing realistic conditions of population structure for modeling language change. Four types of social networks are compared, which exhibit two categories of diffusion dynamics. While the questions about which type of networks are more appropriate for modeling still remains, we give some preliminary suggestions for choosing the type of social networks for modeling.
Non-Repudiation in Internet Telephony
Venue: arXiv cs.CR 2007
Year: 2007

We present a concept to achieve non-repudiation for natural language conversations over the Internet. The method rests on chained electronic signatures applied to pieces of packet-based, digital, voice communication. It establishes the integrity and authenticity of the bidirectional data stream and its temporal sequence and thus the security context of a conversation. The concept is close to the protocols for Voice over the Internet (VoIP), provides a high level of inherent security, and extends naturally to multilateral non-repudiation, e.g., for conferences. Signatures over conversations can become true declarations of will in analogy to electronically signed, digital documents. This enables binding verbal contracts, in principle between unacquainted speakers, and in particular without witnesses. A reference implementation of a secure VoIP archive is exhibited.
Logic Meets Algebra: the Case of Regular Languages
Venue: arXiv cs.LO 2007
Year: 2007

The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism required to define them. The algebraic point of view on automata is an essential complement of this classification: by providing alternative, algebraic characterizations for the classes, it often yields the only opportunity for the design of algorithms that decide expressibility in some logical fragment. We survey the existing results relating the expressibility of regular languages in logical fragments of MSO[S] with algebraic properties of their minimal automata. In particular, we show that many of the best known results in this area share the same underlying mechanics and rely on a very strong relation between logical substitutions and block-products of pseudovarieties of monoid. We also explain the impact of these connections on circuit complexity theory.
Thousands of DebitCredit Transactions-Per-Second: Easy and Inexpensive
Venue: arXiv cs.DB 2007
Year: 2007

A $2k computer can execute about 8k transactions per second. This is 80x more than one of the largest US bank's 1970's traffic - it approximates the total US 1970's financial transaction volume. Very modest modern computers can easily solve yesterday's problems.
Cross-Matching Multiple Spatial Observations and Dealing with Missing Data
Venue: arXiv cs.DB 2007
Year: 2007

Cross-match spatially clusters and organizes several astronomical point-source measurements from one or more surveys. Ideally, each object would be found in each survey. Unfortunately, the observation conditions and the objects themselves change continually. Even some stationary objects are missing in some observations; sometimes objects have a variable light flux and sometimes the seeing is worse. In most cases we are faced with a substantial number of differences in object detections between surveys and between observations taken at different times within the same survey or instrument. Dealing with such missing observations is a difficult problem. The first step is to classify misses as ephemeral - when the object moved or simply disappeared, masked - when noise hid or corrupted the object observation, or edge - when the object was near the edge of the observational field. This classification and a spatial library to represent and manipulate observational footprints help construct a Match table recording both hits and misses. Transitive closure clusters friends-of-friends into object bundles. The bundle summary statistics are recorded in a Bundle table. This design is an evolution of the Sloan Digital Sky Survey cross-match design that compared overlapping observations taken at different times. Cross-Matching Multiple Spatial Observations and Dealing with Missing Data.
On the Software and Knowledge Engineering Aspects of the Educational Process
Venue: arXiv cs.SE 2007
Year: 2007

The Hellenic Open University has embarked on a large-scale effort to enhance its textbook-based material with content that demonstrably supports the basic tenets of distance learning. The challenge is to set up a framework that allows for the production-level creation, distribution and consumption of content, and at the same time, evaluate the effort in terms of technological, educational and organizational knowledge gained. This paper presents a model of the educational process that is used as a development backbone and argues about its conceptual and technical practicality at large.
Towards Practical Typechecking for Macro Tree Transducers
Venue: arXiv cs.PL 2007
Year: 2007

Macro tree transducers (mtt) are an important model that both covers many useful XML transformations and allows decidable exact typechecking. This paper reports our first step toward an implementation of mtt typechecker that has a practical efficiency. Our approach is to represent an input type obtained from a backward inference as an alternating tree automaton, in a style similar to Tozawa's XSLT0 typechecking. In this approach, typechecking reduces to checking emptiness of an alternating tree automaton. We propose several optimizations (Cartesian factorization, state partitioning) on the backward inference process in order to produce much smaller alternating tree automata than the naive algorithm, and we present our efficient algorithm for checking emptiness of alternating tree automata, where we exploit the explicit representation of alternation for local optimizations. Our preliminary experiments confirm that our algorithm has a practical performance that can typecheck simple transformations with respect to the full XHTML in a reasonable time.
Certification of bounds on expressions involving rounded operators
Venue: arXiv cs.MS 2007
Year: 2007

Gappa uses interval arithmetic to certify bounds on mathematical expressions that involve rounded as well as exact operators. Gappa generates a theorem with its proof for each bound treated. The proof can be checked with a higher order logic automatic proof checker, either Coq or HOL Light, and we have developed a large companion library of verified facts for Coq dealing with the addition, multiplication, division, and square root, in fixed- and floating-point arithmetics. Gappa uses multiple-precision dyadic fractions for the endpoints of intervals and performs forward error analysis on rounded operators when necessary. When asked, Gappa reports the best bounds it is able to reach for a given expression in a given context. This feature is used to quickly obtain coarse bounds. It can also be used to identify where the set of facts and automatic techniques implemented in Gappa becomes insufficient. Gappa handles seamlessly additional properties expressed as interval properties or rewriting rules in order to establish more intricate bounds. Recent work showed that Gappa is perfectly suited to the proof of correctness of small pieces of software. Proof obligations can be written by designers, produced by third-party tools or obtained by overloading arithmetic operators.
A New Self-Stabilizing Maximal Matching Algorithm
Venue: arXiv cs.DS 2007
Year: 2007

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given different self-stabilizing algorithms that solves the problem for both the adversarial and fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it stabilizes in the same number of moves as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best moves complexities for the distributed adversarial daemon from O(n^2) and O(delta m) to O(m) where n is the number of processes, m is thenumber of edges, and delta is the maximum degree in the graph.
An empirical study of software reuse by experts in object-oriented design
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents an empirical study of the software reuse activity by expert designers in the context of object-oriented design. Our study focuses on the three following aspects of reuse : (1) the interaction between some design processes, e.g. constructing a problem representation, searching for and evaluating solutions, and reuse processes, i.e. retrieving and using previous solutions, (2) the mental processes involved in reuse, e.g. example-based retrieval or bottom-up versus top-down expanding of the solution, and (3) the mental representations constructed throughout the reuse activity, e.g. dynamic versus static representations. Some implications of these results for the specification of software reuse support environments are discussed.
Dealing With Logical Omniscience: Expressiveness and Pragmatics
Venue: arXiv cs.LO 2007
Year: 2007

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience-- how to choose an approach and construct an appropriate model.
Gnutella: Topology Dynamics On Phase Space
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, the topology dynamic of Gnutella is studied through phase space. The dynamic changes in peer degree are studied as a time series in two dimensional phase space which is defined as the number of connected leaves and the number of connected ultras. The reported degrees are concentrated in three special Software related regions that we named as Ultra Stable Region, Leaf Stable Region and Transition Belt. A method is proposed to classify degree traces in phase space into different classes. Connection churn then is studied along with the churn in degree. It shows that the topological structure of Gnutella is rather stable in its connection degree but not the topology itself. The connection drop rate is estimated and the live time of connections is inferred afterwards. M/M/m/m loss queue system is introduced to model the degree keeping process in Gnutella. This model revealed that the degree stable is ensured by large new connection efforts. In other words the stable in topological structure of Gnutella is a results of essential unstable in its topology. That opens a challenge to the basic design philosophy of this network.
Optimizing the SINR operating point of spatial networks
Venue: arXiv cs.IT 2007
Year: 2007

This paper addresses the following question, which is of interest in the design and deployment of a multiuser decentralized network. Given a total system bandwidth of W Hz and a fixed data rate constraint of R bps for each transmission, how many frequency slots N of size W/N should the band be partitioned into to maximize the number of simultaneous transmissions in the network? In an interference-limited ad-hoc network, dividing the available spectrum results in two competing effects: on the positive side, it reduces the number of users on each band and therefore decreases the interference level which leads to an increased SINR, while on the negative side the SINR requirement for each transmission is increased because the same information rate must be achieved over a smaller bandwidth. Exploring this tradeoff between bandwidth and SINR and determining the optimum value of N in terms of the system parameters is the focus of the paper. Using stochastic geometry, we analytically derive the optimal SINR threshold (which directly corresponds to the optimal spectral efficiency) on this tradeoff curve and show that it is a function of only the path loss exponent. Furthermore, the optimal SINR point lies between the low-SINR (power-limited) and high-SINR (bandwidth-limited) regimes. In order to operate at this optimal point, the number of frequency bands (i.e., the reuse factor) should be increased until the threshold SINR, which is an increasing function of the reuse factor, is equal to the optimal value.
Parameterized Algorithms for Directed Maximum Leaf Problems
Venue: arXiv cs.DS 2007
Year: 2007

We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family $\cal L$ that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in $\cal L$. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a `spanning tree with many leaves' in the undirected case, and which is interesting on its own: If a digraph $D\in \cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves.
Permutation Decoding and the Stopping Redundancy Hierarchy of Linear Block Codes
Venue: arXiv cs.IT 2007
Year: 2007

We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.
Towards a New ODE Solver Based on Cartan's Equivalence Method
Venue: arXiv cs.SC 2007
Year: 2007

The aim of the present paper is to propose an algorithm for a new ODE--solver which should improve the abilities of current solvers to handle second order differential equations. The paper provides also a theoretical result revealing the relationship between the change of coordinates, that maps the generic equation to a given target equation, and the symmetry $\D$-groupoid of this target.
Comments on "Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks''
Venue: arXiv cs.DC 2007
Year: 2007

Min, Veeravalli, and Barlas proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that the proposed approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Finally, we formally prove that under a linear cost model, as in the original paper, an optimal schedule has an infinite number of installments. Such a cost model can therefore not be sed to design practical multi-installment strategies.
Invariant template matching in systems with spatiotemporal coding: a vote for instability
Venue: arXiv cs.CV 2007
Year: 2007

We consider the design of a pattern recognition that matches templates to images, both of which are spatially sampled and encoded as temporal sequences. The image is subject to a combination of various perturbations. These include ones that can be modeled as parameterized uncertainties such as image blur, luminance, translation, and rotation as well as unmodeled ones. Biological and neural systems require that these perturbations be processed through a minimal number of channels by simple adaptation mechanisms. We found that the most suitable mathematical framework to meet this requirement is that of weakly attracting sets. This framework provides us with a normative and unifying solution to the pattern recognition problem. We analyze the consequences of its explicit implementation in neural systems. Several properties inherent to the systems designed in accordance with our normative mathematical argument coincide with known empirical facts. This is illustrated in mental rotation, visual search and blur/intensity adaptation. We demonstrate how our results can be applied to a range of practical problems in template matching and pattern recognition.
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
Venue: arXiv cs.GT 2007
Year: 2007

In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).
Aperture-Angle and Hausdorff-Approximation of Convex Figures
Venue: arXiv cs.CG 2007
Year: 2007

The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).
Secure Broadcasting
Venue: arXiv cs.IT 2007
Year: 2007

Wyner's wiretap channel is extended to parallel broadcast channels and fading channels with multiple receivers. In the first part of the paper, we consider the setup of parallel broadcast channels with one sender, multiple intended receivers, and one eavesdropper. We study the situations where the sender broadcasts either a common message or independent messages to the intended receivers. We derive upper and lower bounds on the common-message-secrecy capacity, which coincide when the users are reversely degraded. For the case of independent messages we establish the secrecy sum-capacity when the users are reversely degraded. In the second part of the paper we apply our results to fading channels: perfect channel state information of all intended receivers is known globally, whereas the eavesdropper channel is known only to her. For the common message case, a somewhat surprising result is proven: a positive rate can be achieved independently of the number of intended receivers. For independent messages, an opportunistic transmission scheme is presented that achieves the secrecy sum-capacity in the limit of large number of receivers. Our results are stated for a fast fading channel model. Extensions to the block fading model are also discussed.