OpenRaiser/Intern-Atlas huggingface dataset:
A Limit Theorem in Singular Regression Problem
Venue: arXiv cs.LG 2009
Year: 2009

In statistical problems, a set of parameterized probability distributions is used to estimate the true probability distribution. If Fisher information matrix at the true distribution is singular, then it has been left unknown what we can estimate about the true distribution from random samples. In this paper, we study a singular regression problem and prove a limit theorem which shows the relation between the singular regression problem and two birational invariants, a real log canonical threshold and a singular fluctuation. The obtained theorem has an important application to statistics, because it enables us to estimate the generalization error from the training error without any knowledge of the true probability distribution.
The compositional construction of Markov processes
Venue: arXiv cs.LO 2009
Year: 2009

We describe an algebra for composing automata in which the actions have probabilities. We illustrate by showing how to calculate the probability of reaching deadlock in k steps in a model of the classical Dining Philosopher problem, and show, using the Perron-Frobenius Theorem, that this probability tends to 1 as k tends to infinity.
Capacity Bounds of Half-Duplex Gaussian Cooperative Interference Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we investigate the half-duplex cooperative communication scheme of a two user Gaussian interference channel. We develop achievable region and outer bound for the case when the system allow either transmitter or receiver cooperation. We show that by using our transmitter cooperation scheme, there is significant capacity improvement compare to the previous results, especially when the cooperation link is strong. Further, if the cooperation channel gain is infinity, both our transmitter and receiver cooperation rates achieve their respective outer bound. It is also shown that transmitter cooperation provides larger achievable region than receiver cooperation under the same channel and power conditions.
A Statistical Approach to Performance Monitoring in Soft Real-Time Distributed Systems
Venue: arXiv cs.NI 2009
Year: 2009

Soft real-time applications require timely delivery of messages conforming to the soft real-time constraints. Satisfying such requirements is a complex task both due to the volatile nature of distributed environments, as well as due to numerous domain-specific factors that affect message latency. Prompt detection of the root-cause of excessive message delay allows a distributed system to react accordingly. This may significantly improve compliance with the required timeliness constraints. In this work, we present a novel approach for distributed performance monitoring of soft-real time distributed systems. We propose to employ recent distributed algorithms from the statistical signal processing and learning domains, and to utilize them in a different context of online performance monitoring and root-cause analysis, for pinpointing the reasons for violation of performance requirements. Our approach is general and can be used for monitoring of any distributed system, and is not limited to the soft real-time domain. We have implemented the proposed framework in TransFab, an IBM prototype of soft real-time messaging fabric. In addition to root-cause analysis, the framework includes facilities to resolve resource allocation problems, such as memory and bandwidth deficiency. The experiments demonstrate that the system can identify and resolve latency problems in a timely fashion.
Automatic Analog Beamforming Transceiver for 60 GHz Radios
Venue: arXiv cs.NI 2009
Year: 2009

We propose a transceiver architecture for automatic beamforming and instantaneous setup of a multigigabit-per-second wireless link between two millimeter wave radios. The retro-directive architecture eliminates necessity of slow and complex digital algorithms required for searching and tracking the directions of opposite end radios. Simulations predict <5 micro-seconds setup time for a 2-Gbps bidirectional 60-GHz communication link between two 10-meters apart radios. The radios have 4-element arrayed antennas, and use QPSK modulation with 1.5 GHz analog bandwidth.
An Algebraic Watchdog for Wireless Network Coding
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we propose a scheme, called the "algebraic watchdog" for wireless network coding, in which nodes can detect malicious behaviors probabilistically, police their downstream neighbors locally using overheard messages, and, thus, provide a secure global "self-checking network". Unlike traditional Byzantine detection protocols which are receiver-based, this protocol gives the senders an active role in checking the node downstream. This work is inspired by Marti et. al.'s watchdog-pathrater, which attempts to detect and mitigate the effects of routing misbehavior. As the first building block of a such system, we focus on a two-hop network. We present a graphical model to understand the inference process nodes execute to police their downstream neighbors; as well as to compute, analyze, and approximate the probabilities of misdetection and false detection. In addition, we present an algebraic analysis of the performance using an hypothesis testing framework, that provides exact formulae for probabilities of false detection and misdetection.
On Leveraging Partial Paths in Partially-Connected Networks
Venue: arXiv cs.NI 2009
Year: 2009

Mobile wireless network research focuses on scenarios at the extremes of the network connectivity continuum where the probability of all nodes being connected is either close to unity, assuming connected paths between all nodes (mobile ad hoc networks), or it is close to zero, assuming no multi-hop paths exist at all (delay-tolerant networks). In this paper, we argue that a sizable fraction of networks lies between these extremes and is characterized by the existence of partial paths, i.e. multi-hop path segments that allow forwarding data closer to the destination even when no end-to-end path is available. A fundamental issue in such networks is dealing with disruptions of end-to-end paths. Under a stochastic model, we compare the performance of the established end-to-end retransmission (ignoring partial paths), against a forwarding mechanism that leverages partial paths to forward data closer to the destination even during disruption periods. Perhaps surprisingly, the alternative mechanism is not necessarily superior. However, under a stochastic monotonicity condition between current v.s. future path length, which we demonstrate to hold in typical network models, we manage to prove superiority of the alternative mechanism in stochastic dominance terms. We believe that this study could serve as a foundation to design more efficient data transfer protocols for partially-connected networks, which could potentially help reducing the gap between applications that can be supported over disconnected networks and those requiring full connectivity.
Nuclear norm minimization for the planted clique and biclique problems
Venue: arXiv cs.DS 2009
Year: 2009

We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special cases that the input graph has a planted clique or biclique (i.e., a single large clique or biclique plus diversionary edges), our algorithm successfully provides an exact solution to the original instance. For each problem, we provide two analyses of when our algorithm succeeds. In the first analysis, the diversionary edges are placed by an adversary. In the second, they are placed at random. In the case of random edges for the planted clique problem, we obtain the same bound as Alon, Krivelevich and Sudakov as well as Feige and Krauthgamer, but we use different techniques.
Erasure Codes with a Banded Structure for Hybrid Iterative-ML Decoding
Venue: arXiv cs.IT 2009
Year: 2009

This paper presents new FEC codes for the erasure channel, LDPC-Band, that have been designed so as to optimize a hybrid iterative-Maximum Likelihood (ML) decoding. Indeed, these codes feature simultaneously a sparse parity check matrix, which allows an efficient use of iterative LDPC decoding, and a generator matrix with a band structure, which allows fast ML decoding on the erasure channel. The combination of these two decoding algorithms leads to erasure codes achieving a very good trade-off between complexity and erasure correction capability.
Efficient decoding algorithm using triangularity of $\mbf{R}$ matrix of QR-decomposition
Venue: arXiv cs.IT 2009
Year: 2009

An efficient decoding algorithm named `divided decoder' is proposed in this paper. Divided decoding can be combined with any decoder using QR-decomposition and offers different pairs of performance and complexity. Divided decoding provides various combinations of two or more different searching algorithms. Hence it makes flexibility in error rate and complexity for the algorithms using it. We calculate diversity orders and upper bounds of error rates for typical models when these models are solved by divided decodings with sphere decoder, and discuss about the effects of divided decoding on complexity. Simulation results of divided decodings combined with a sphere decoder according to different splitting indices correspond to the theoretical analysis.
Resource Adaptive Agents in Interactive Theorem Proving
Venue: arXiv cs.LO 2009
Year: 2009

We introduce a resource adaptive agent mechanism which supports the user in interactive theorem proving. The mechanism uses a two layered architecture of agent societies to suggest appropriate commands together with possible command argument instantiations. Experiments with this approach show that its effectiveness can be further improved by introducing a resource concept. In this paper we provide an abstract view on the overall mechanism, motivate the necessity of an appropriate resource concept and discuss its realization within the agent architecture.
On Recognizable Languages of Infinite Pictures
Venue: arXiv cs.LO 2009
Year: 2009

In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. The authors asked for comparing the tiling system acceptance with an acceptance of pictures row by row using an automaton model over ordinal words of length $ω^2$. We give in this paper a solution to this problem, showing that all languages of infinite pictures which are accepted row by row by Büchi or Choueka automata reading words of length $ω^2$ are Büchi recognized by a finite tiling system, but the converse is not true. We give also the answer to two other questions which were raised by Altenbernd, Thomas and Wöhrle, showing that it is undecidable whether a Büchi recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable).
Effectively Searching Maps in Web Documents
Venue: arXiv cs.DL 2009
Year: 2009

Maps are an important source of information in archaeology and other sciences. Users want to search for historical maps to determine recorded history of the political geography of regions at different eras, to find out where exactly archaeological artifacts were discovered, etc. Currently, they have to use a generic search engine and add the term map along with other keywords to search for maps. This crude method will generate a significant number of false positives that the user will need to cull through to get the desired results. To reduce their manual effort, we propose an automatic map identification, indexing, and retrieval system that enables users to search and retrieve maps appearing in a large corpus of digital documents using simple keyword queries. We identify features that can help in distinguishing maps from other figures in digital documents and show how a Support-Vector-Machine-based classifier can be used to identify maps. We propose map-level-metadata e.g., captions, references to the maps in text, etc. and document-level metadata, e.g., title, abstract, citations, how recent the publication is, etc. and show how they can be automatically extracted and indexed. Our novel ranking algorithm weights different metadata fields differently and also uses the document-level metadata to help rank retrieved maps. Empirical evaluations show which features should be selected and which metadata fields should be weighted more. We also demonstrate improved retrieval results in comparison to adaptations of existing methods for map retrieval. Our map search engine has been deployed in an online map-search system that is part of the Blind-Review digital library system.
Max Edge Coloring of Trees
Venue: arXiv cs.DS 2009
Year: 2009

We study the weighted generalization of the edge coloring problem where the weight of each color class (matching) equals to the weight of its heaviest edge and the goal is to minimize the sum of the colors' weights. We present a 3/2-approximation algorithm for trees.
A Framework to Handle Linear Temporal Properties in (ω-)Regular Model Checking
Venue: arXiv cs.LO 2009
Year: 2009

Since the topic emerged several years ago, work on regular model checking has mostly been devoted to the verification of state reachability and safety properties. Though it was known that linear temporal properties could also be checked within this framework, little has been done about working out the corresponding details. This paper addresses this issue in the context of regular model checking based on the encoding of states by finite or infinite words. It works out the exact constructions to be used in both cases, and proposes a partial solution to the problem resulting from the fact that infinite computations of unbounded configurations might never contain the same configuration twice, thus making cycle detection problematic.
Peer to Peer Optimistic Collaborative Editing on XML-like trees
Venue: arXiv cs.DS 2009
Year: 2009

Collaborative editing consists in editing a common document shared by several independent sites. This may give rise to conficts when two different users perform simultaneous uncompatible operations. Centralized systems solve this problem by using locks that prevent some modifications to occur and leave the resolution of confict to users. On the contrary, peer to peer (P2P) editing doesn't allow locks and the optimistic approach uses a Integration Transformation IT that reconciliates the conficting operations and ensures convergence (all copies are identical on each site). Two properties TP1 and TP2, relating the set of allowed operations Op and the transformation IT, have been shown to ensure the correctness of the process. The choice of the set Op is crucial to define an integration operation that satisfies TP1 and TP2. Many existing algorithms don't satisfy these properties and are indeed incorrect i.e. convergence is not guaranteed. No algorithm enjoying both properties is known for strings and little work has been done for XML trees in a pure P2P framework (that doesn't use time-stamps for instance). We focus on editing unranked unordered labeled trees, so-called XML-like trees that are considered for instance in the Harmony pro ject. We show that no transformation satisfying TP1 and TP2 can exist for a first set of operations but we show that TP1 and TP2 hold for a richer set of operations. We show how to combine our approach with any convergent editing process on strings (not necessarily based on integration transformation) to get a convergent process.
On the bit-complexity of sparse polynomial multiplication
Venue: arXiv cs.DS 2009
Year: 2009

In this paper, we present fast algorithms for the product of two multivariate polynomials in sparse representation. The bit complexity of our algorithms are studied in detail for various types of coefficients, and we derive new complexity results for the power series multiplication in many variables. Our algorithms are implemented and freely available within the Mathemagix software. We show that their theoretical costs are well-reflected in practice.
Neighbourhood Structures: Bisimilarity and Basic Model Theory
Venue: arXiv cs.LO 2009
Year: 2009

Neighbourhood structures are the standard semantic tool used to reason about non-normal modal logics. The logic of all neighbourhood models is called classical modal logic. In coalgebraic terms, a neighbourhood frame is a coalgebra for the contravariant powerset functor composed with itself, denoted by 2^2. We use this coalgebraic modelling to derive notions of equivalence between neighbourhood structures. 2^2-bisimilarity and behavioural equivalence are well known coalgebraic concepts, and they are distinct, since 2^2 does not preserve weak pullbacks. We introduce a third, intermediate notion whose witnessing relations we call precocongruences (based on pushouts). We give back-and-forth style characterisations for 2^2-bisimulations and precocongruences, we show that on a single coalgebra, precocongruences capture behavioural equivalence, and that between neighbourhood structures, precocongruences are a better approximation of behavioural equivalence than 2^2-bisimulations. We also introduce a notion of modal saturation for neighbourhood models, and investigate its relationship with definability and image-finiteness. We prove a Hennessy-Milner theorem for modally saturated and for image-finite neighbourhood models. Our main results are an analogue of Van Benthem's characterisation theorem and a model-theoretic proof of Craig interpolation for classical modal logic.
Network Coding Capacity: A Functional Dependence Bound
Venue: arXiv cs.IT 2009
Year: 2009

Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set of all entropic vectors $Γ^{*}$, which is known to be an extremely hard problem. On the other hand, calculating the explicitly known linear programming bound is very hard in practice due to an exponential growth in complexity as a function of network size. We give a new, easily computable outer bound, based on characterization of all functional dependencies in networks. We also show that the proposed bound is tighter than some known bounds.
Fast Dual-Radio Cross-Layer Handoffs in Multi-Hop Infrastructure-mode 802.11 Wireless Networks for In-Vehicle Multimedia Infotainment
Venue: arXiv cs.NI 2009
Year: 2009

Minimizing handoff latency and achieving near-zero packet loss is critical for delivering multimedia infotainment applications to fast-moving vehicles that are likely to encounter frequent handoffs. In this paper, we propose a dual-radio cross-layer handoff scheme for infrastructure-mode 802.11 Wireless Networks that achieve this goal. We present performance results of an implementation of our algorithm in a Linux-based On-Board-Unit prototype.
Arrow's Impossibility Theorem Without Unanimity
Venue: arXiv cs.GT 2009
Year: 2009

Arrow's Impossibility Theorem states that any constitution which satisfies Transitivity, Independence of Irrelevant Alternatives (IIA) and Unanimity is a dictatorship. Wilson derived properties of constitutions satisfying Transitivity and IIA for unrestricted domains where ties are allowed. In this paper we consider the case where only strict preferences are allowed. In this case we derive a new short proof of Arrow theorem and further obtain a new and complete characterization of all functions satisfying Transitivity and IIA.
An algebra of automata which includes both classical and quantum entities
Venue: arXiv cs.LO 2009
Year: 2009

We describe an algebra for composing automata which includes both classical and quantum entities and their communications. We illustrate by describing in detail a quantum protocol.
Optimizing Service Orchestrations
Venue: arXiv cs.DC 2009
Year: 2009

As the number of services and the size of data involved in workflows increases, centralised orchestration techniques are reaching the limits of scalability. In the classic orchestration model, all data passes through a centralised engine, which results in unnecessary data transfer, wasted bandwidth and the engine to become a bottleneck to the execution of a workflow. This paper presents and evaluates the Circulate architecture which maintains the robustness and simplicity of centralised orchestration, but facilitates choreography by allowing services to exchange data directly with one another. Circulate could be realised within any existing workflow framework, in this paper, we focus on WS-Circulate, a Web services based implementation. Taking inspiration from the Montage workflow, a number of common workflow patterns (sequence, fan-in and fan-out), input to output data size relationships and network configurations are identified and evaluated. The performance analysis concludes that a substantial reduction in communication overhead results in a 2-4 fold performance benefit across all patterns. An end-to-end pattern through the Montage workflow results in an 8 fold performance benefit and demonstrates how the advantage of using the Circulate architecture increases as the complexity of a workflow grows.
On the Entropy of Written Spanish
Venue: arXiv cs.CL 2009
Year: 2009

This paper reports on results on the entropy of the Spanish language. They are based on an analysis of natural language for n-word symbols (n = 1 to 18), trigrams, digrams, and characters. The results obtained in this work are based on the analysis of twelve different literary works in Spanish, as well as a 279917 word news file provided by the Spanish press agency EFE. Entropy values are calculated by a direct method using computer processing and the probability law of large numbers. Three samples of artificial Spanish language produced by a first-order model software source are also analyzed and compared with natural Spanish language.
On the Relationship Between the Multi-antenna Secrecy Communications and Cognitive Radio Communications
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the capacity of the multi-antenna or multiple-input multiple-output (MIMO) secrecy channels with multiple eavesdroppers having single/multiple antennas. It is known that the MIMO secrecy capacity is achievable with the optimal transmit covariance matrix that maximizes the minimum difference between the channel mutual information of the secrecy user and those of the eavesdroppers. The MIMO secrecy capacity computation can thus be formulated as a non-convex max-min problem, which cannot be solved efficiently by standard convex optimization techniques. To handle this difficulty, we explore a relationship between the MIMO secrecy channel and the recently developed MIMO cognitive radio (CR) channel, in which the multi-antenna secondary user transmits over the same spectrum simultaneously with multiple primary users, subject to the received interference power constraints at the primary users, or the so-called ``interference temperature (IT)'' constraints. By constructing an auxiliary CR MIMO channel that has the same channel responses as the MIMO secrecy channel, we prove that the optimal transmit covariance matrix to achieve the secrecy capacity is the same as that to achieve the CR spectrum sharing capacity with properly selected IT constraints. Based on this relationship, several algorithms are proposed to solve the non-convex secrecy capacity computation problem by transforming it into a sequence of CR spectrum sharing capacity computation problems that are convex. For the case with single-antenna eavesdroppers, the proposed algorithms obtain the exact capacity of the MIMO secrecy channel, while for the case with multi-antenna eavesdroppers, the proposed algorithms obtain both upper and lower bounds on the MIMO secrecy capacity.