OpenRaiser/Intern-Atlas huggingface dataset:
Finding and Classifying Critical Points of 2D Vector Fields: A Cell-Oriented Approach Using Group Theory
Venue: arXiv cs.GR 2010
Year: 2010

We present a novel approach to finding critical points in cell-wise barycentrically or bilinearly interpolated vector fields on surfaces. The Poincar\e index of the critical points is determined by investigating the qualitative behavior of 0-level sets of the interpolants of the vector field components in parameter space using precomputed combinatorial results, thus avoiding the computation of the Jacobian of the vector field at the critical points in order to determine its index. The locations of the critical points within a cell are determined analytically to achieve accurate results. This approach leads to a correct treatment of cases with two first-order critical points or one second-order critical point of bilinearly interpolated vector fields within one cell, which would be missed by examining the linearized field only. We show that for the considered interpolation schemes determining the index of a critical point can be seen as a coloring problem of cell edges. A complete classification of all possible colorings in terms of the types and number of critical points yielded by each coloring is given using computational group theory. We present an efficient algorithm that makes use of these precomputed classifications in order to find and classify critical points in a cell-by-cell fashion. Issues of numerical stability, construction of the topological skeleton, topological simplification, and the statistics of the different types of critical points are also discussed.
The Accuracy of Tree-based Counting in Dynamic Networks
Venue: arXiv cs.DC 2010
Year: 2010

Tree-based protocols are ubiquitous in distributed systems. They are flexible, they perform generally well, and, in static conditions, their analysis is mostly simple. Under churn, however, node joins and failures can have complex global effects on the tree overlays, making analysis surprisingly subtle. To our knowledge, few prior analytic results for performance estimation of tree based protocols under churn are currently known. We study a simple Bellman-Ford-like protocol which performs network size estimation over a tree-shaped overlay. A continuous time Markov model is constructed which allows key protocol characteristics to be estimated, including the expected number of nodes at a given (perceived) distance to the root and, for each such node, the expected (perceived) size of the subnetwork rooted at that node. We validate the model by simulation, using a range of network sizes, node degrees, and churn-to-protocol rates, with convincing results.
Optimal Crosstalk Detection and Localization Method for Optical Time Division Multiplexed Transmission Systems
Venue: arXiv cs.NI 2010
Year: 2010

All-Optical Network (AON) is a network where the user-network interface is optical and the data does undergo optical to electrical conversion within the network. AONs are attractive because they promise very high rates, flexible switching and broad application support. There are two technologies for AON: Wavelength Division Multiplexed (WDM) and Optical Time Division Multiplexed (OTDM). OTDM transmission systems are becoming increasingly important as one of the key technologies satisfying the growing demand for large capacity optical networks. Although OTDM has several advantages in terms of operation system, such as natural accommodation of higher bit rate payloads, it introduces many security vulnerabilities, which do not exist in traditional networks. One of the serious problems with OTDM is the fact that optical crosstalk is additive, and thus the aggregate effect of crosstalk over a whole all-optical network (AON) may be more nefarious than a single point of crosstalk. This is because crosstalk can spread rapidly through the network, causing additional awkward failures and triggering multiple undesirable alarms. This results in the continuous monitoring and identification of the impairments becoming challenging in the event of transmission failures. In this paper we propose a novel approach for detecting and localizing crosstalk in OTDM transmission systems that can participate in some tasks for fault management in optical network.
Data Stream Algorithms for Codeword Testing
Venue: arXiv cs.IT 2010
Year: 2010

Motivated by applications in storage systems and property testing, we study data stream algorithms for local testing and tolerant testing of codes. Ideally, we would like to know whether there exist asymptotically good codes that can be local/tolerant tested with one-pass, poly-log space data stream algorithms. We show that for the error detection problem (and hence, the local testing problem), there exists a one-pass, log-space data stream algorithm for a broad class of asymptotically good codes, including the Reed-Solomon (RS) code and expander codes. In our technically more involved result, we give a one-pass, $O(e\log^2{n})$-space algorithm for RS (and related) codes with dimension $k$ and block length $n$ that can distinguish between the cases when the Hamming distance between the received word and the code is at most $e$ and at least $a\cdot e$ for some absolute constant $a>1$. For RS codes with random errors, we can obtain $e\le O(n/k)$. For folded RS codes, we obtain similar results for worst-case errors as long as $e\le (n/k)^{1-\eps}$ for any constant $\eps>0$. These results follow by reducing the tolerant testing problem to the error detection problem using results from group testing and the list decodability of the code. We also show that using our techniques, the space requirement and the upper bound of $e\le O(n/k)$ cannot be improved by more than logarithmic factors.
Performance Evaluation of Wavelength Routed Optical Network with Wavelength Conversion
Venue: arXiv cs.NI 2010
Year: 2010

The rapid development of telecommunication networks is driven by user demands for new applications and advances in technologies. The explosive growth of the internet traffic is due to its use for collecting the information, communication, multimedia application, entertainment, etc. These applications are imposing a tremendous demand for bandwidth capacity on telecommunication network. The introduction of fiber optics had proved to meet the huge demand of bandwidth. These requirement can be meet by all optical network which is capable of transmitting enormous data at very high speed, around 50 Tera bits per seconds (Tbps) A wavelength conversion technique is addressed in this paper to reduced the blocking probability in wavelength routed networks. It is seen that the blocking probability of traffic requests decreases as the wavelength conversion factor increases. We explode the possibility for network with different size with variation in wavelength per link. In this work the evaluation of wavelength routed optical network with varying number of wavelength converters, different traffic types are carried out and results are shown that the blocking probability is minimum with 50% to 60% wavelength convertible nodes. Wavelength convertible nodes more than 60% are not showing much effect on reduction in blocking probability rather it results in increase in overall cost of network.
Explicit Maximum Likelihood Loss Estimator in Multicast Tomography
Venue: arXiv cs.NI 2010
Year: 2010

For the tree topology, previous studies show the maximum likelihood estimate (MLE) of a link/path takes a polynomial form with a degree that is one less than the number of descendants connected to the link/path. Since then, the main concern is focused on searching for methods to solve the high degree polynomial without using iterative approximation. An explicit estimator based on the Law of Large Numbers has been proposed to speed up the estimation. However, the estimate obtained from the estimator is not a MLE. When $n<\infty$, the estimate may be noticeable different from the MLE. To overcome this, an explicit MLE estimator is presented in this paper and a comparison between the MLE estimator and the explicit estimator proposed previously is presented to unveil the insight of the MLE estimator and point out the pitfall of the previous one.
On the comparison of plans: Proposition of an instability measure for dynamic machine scheduling
Venue: arXiv cs.AI 2010
Year: 2010

On the basis of an analysis of previous research, we present a generalized approach for measuring the difference of plans with an exemplary application to machine scheduling. Our work is motivated by the need for such measures, which are used in dynamic scheduling and planning situations. In this context, quantitative approaches are needed for the assessment of the robustness and stability of schedules. Obviously, any `robustness' or `stability' of plans has to be defined w. r. t. the particular situation and the requirements of the human decision maker. Besides the proposition of an instability measure, we therefore discuss possibilities of obtaining meaningful information from the decision maker for the implementation of the introduced approach.
Indoor Positioning with Radio Location Fingerprinting
Venue: arXiv cs.NI 2010
Year: 2010

An increasingly important requirement for many novel applications is sensing the positions of people, equipment, etc. GPS technology has proven itself as a successfull technology for positioning in outdoor environments but indoor no technology has yet gained a similar wide-scale adoption. A promising indoor positioning technique is radio-based location fingerprinting, having the major advantage of exploiting already existing radio infrastructures, like IEEE 802.11, which avoids extra deployment costs and effort. The research goal of this thesis is to address the limitations of current indoor location fingerprinting systems. In particular the aim is to advance location fingerprinting techniques for the challenges of handling heterogeneous clients, scalability to many clients, and interference between communication and positioning. The wireless clients used for location fingerprinting are heterogeneous even when only considering clients for the same technology. Heterogeneity is a challenge for location fingerprinting because it severely decreases the precision of location fingerprinting. To support many clients location fingerprinting has to address how to scale estimate calculation, measurement distribution, and distribution of position estimates. This is a challenge because of the number of calculations involved and the frequency of measurements and position updates. Positioning using location fingerprinting requires the measurement of, for instance, signal strength for nearby base stations. However, many wireless communication technologies block communication while collecting such measurements. This interference is a challenge because it is not desirable that positioning disables communication. An additional goal is to improve the conceptual foundation of location fingerprinting. A better foundation will aid researchers to better survey and design location fingerprinting systems.
Efficient multicast data transfer with congestion control using dynamic source channels
Venue: arXiv cs.NI 2010
Year: 2010

The most efficient receiver-driven multicast congestion control protocols use dynamic channels. This means that each group has a cyclic rate variation with a continuously decreasing phase. Despite promising results in terms of fairness, using efficiently these dynamic groups could be a challenging task for application programmers. This paper presents a sequencer which maps out application data to dynamic groups in an optimal way. Multiple applications such as file transfer or video streaming, can use this sequencer, thanks to a simple API usable with any buffer containing the most important data first. To evaluate this solution, we designed a file transfer software using a FEC encoding. Results show the sequencer optimal behavior and the file transfer efficiency, as a single download generates only little more overhead than TCP . Moreover, download time is almost independent of the number of receivers, and is already faster than TCP with 2 competing downloads.
Universal A Posteriori Metrics Game
Venue: arXiv cs.IT 2010
Year: 2010

Over binary input channels, uniform distribution is a universal prior, in the sense that it allows to maximize the worst case mutual information over all binary input channels, ensuring at least 94.2% of the capacity. In this paper, we address a similar question, but with respect to a universal generalized linear decoder. We look for the best collection of finitely many a posteriori metrics, to maximize the worst case mismatched mutual information achieved by decoding with these metrics (instead of an optimal decoder such as the Maximum Likelihood (ML) tuned to the true channel). It is shown that for binary input and output channels, two metrics suffice to actually achieve the same performance as an optimal decoder. In particular, this implies that there exist a decoder which is generalized linear and achieves at least 94.2% of the compound capacity on any compound set, without the knowledge of the underlying set.
Polynomial Learning of Distribution Families
Venue: arXiv cs.LG 2010
Year: 2010

The question of polynomial learnability of probability distributions, particularly Gaussian mixture distributions, has recently received significant attention in theoretical computer science and machine learning. However, despite major progress, the general question of polynomial learnability of Gaussian mixture distributions still remained open. The current work resolves the question of polynomial learnability for Gaussian mixtures in high dimension with an arbitrary fixed number of components. The result on learning Gaussian mixtures relies on an analysis of distributions belonging to what we call "polynomial families" in low dimension. These families are characterized by their moments being polynomial in parameters and include almost all common probability distributions as well as their mixtures and products. Using tools from real algebraic geometry, we show that parameters of any distribution belonging to such a family can be learned in polynomial time and using a polynomial number of sample points. The result on learning polynomial families is quite general and is of independent interest. To estimate parameters of a Gaussian mixture distribution in high dimensions, we provide a deterministic algorithm for dimensionality reduction. This allows us to reduce learning a high-dimensional mixture to a polynomial number of parameter estimations in low dimension. Combining this reduction with the results on polynomial families yields our result on learning arbitrary Gaussian mixtures in high dimensions.
Fréchet Distance Problems in Weighted Regions
Venue: arXiv cs.CG 2010
Year: 2010

We discuss two versions of the Fréchet distance problem in weighted planar subdivisions. In the first one, the distance between two points is the weighted length of the line segment joining the points. In the second one, the distance between two points is the length of the shortest path between the points. In both cases, we give algorithms for finding a (1+epsilon)-factor approximation of the Fréchet distance between two polygonal curves. We also consider the Fréchet distance between two polygonal curves among polyhedral obstacles in R^3 and present a (1+epsilon)-factor approximation algorithm.
Outer Bounds for the Interference Channel with a Cognitive Relay
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we first present an outer bound for a general interference channel with a cognitive relay, i.e., a relay that has non-causal knowledge of both independent messages transmitted in the interference channel. This outer bound reduces to the capacity region of the deterministic broadcast channel and of the deterministic cognitive interference channel through nulling of certain channel inputs. It does not, however, reduce to that of certain deterministic interference channels for which capacity is known. As such, we subsequently tighten the bound for channels whose outputs satisfy an "invertibility" condition. This second outer bound now reduces to the capacity of this special class of deterministic interference channels. The second outer bound is further tightened for the high SNR deterministic approximation of the Gaussian interference channel with a cognitive relay by exploiting the special structure of the interference. We provide an example that suggests that this third bound is tight in at least some parameter regimes for the high SNR deterministic approximation of the Gaussian channel. Another example shows that the third bound is capacity in the special case where there are no direct links between the non-cognitive transmitters.
Tailored RF pulse optimization for magnetization inversion at ultra high field
Venue: arXiv cs.CE 2010
Year: 2010

The radiofrequency (RF) transmit field is severely inhomogeneous at ultrahigh field due to both RF penetration and RF coil design issues. This particularly impairs image quality for sequences that use inversion pulses such as magnetization prepared rapid acquisition gradient echo and limits the use of quantitative arterial spin labeling sequences such as flow-attenuated inversion recovery. Here we have used a search algorithm to produce inversion pulses tailored to take into account the heterogeneity of the RF transmit field at 7 T. This created a slice selective inversion pulse that worked well (good slice profile and uniform inversion) over the range of RF amplitudes typically obtained in the head at 7 T while still maintaining an experimentally achievable pulse length and pulse amplitude in the brain at 7 T. The pulses used were based on the frequency offset correction inversion technique, as well as time dilation of functions, but the RF amplitude, frequency sweep, and gradient functions were all generated using a genetic algorithm with an evaluation function that took into account both the desired inversion profile and the transmit field inhomogeneity.
Notations Around the World: Census and Exploitation
Venue: arXiv cs.DL 2010
Year: 2010

Mathematical notations around the world are diverse. Not as much as requiring computing machines' makers to adapt to each culture, but as much as to disorient a person landing on a web-page with a text in mathematics. In order to understand better this diversity, we are building a census of notations: it should allow any content creator or mathematician to grasp which mathematical notation is used in which language and culture. The census is built collaboratively, collected in pages with a given semantic and presenting observations of the widespread notations being used in existing materials by a graphical extract. We contend that our approach should dissipate the fallacies found here and there about the notations in "other cultures" so that a better understanding of the cultures can be realized. The exploitation of the census in the math-bridge project is also presented: this project aims at taking learners "where they are in their math-knowledge" and bring them to a level ready to start engineering studies. The census serves as definitive reference for the transformation elements that generate the rendering of formulæ in web-browsers.
Analysis of Quasi-Cyclic LDPC codes under ML decoding over the erasure channel
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we show that Quasi-Cyclic LDPC codes can efficiently accommodate the hybrid iterative/ML decoding over the binary erasure channel. We demonstrate that the quasi-cyclic structure of the parity-check matrix can be advantageously used in order to significantly reduce the complexity of the ML decoding. This is achieved by a simple row/column permutation that transforms a QC matrix into a pseudo-band form. Based on this approach, we propose a class of QC-LDPC codes with almost ideal error correction performance under the ML decoding, while the required number of row/symbol operations scales as $k\sqrt{k}$, where $k$ is the number of source symbols.
Optimism in Reinforcement Learning and Kullback-Leibler Divergence
Venue: arXiv cs.LG 2010
Year: 2010

We consider model-based reinforcement learning in finite Markov De- cision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out extended value it- erations under a constraint of consistency with the estimated model tran- sition probabilities. The UCRL2 algorithm by Auer, Jaksch and Ortner (2009), which follows this strategy, has recently been shown to guarantee near-optimal regret bounds. In this paper, we strongly argue in favor of using the Kullback-Leibler (KL) divergence for this purpose. By studying the linear maximization problem under KL constraints, we provide an ef- ficient algorithm, termed KL-UCRL, for solving KL-optimistic extended value iteration. Using recent deviation bounds on the KL divergence, we prove that KL-UCRL provides the same guarantees as UCRL2 in terms of regret. However, numerical experiments on classical benchmarks show a significantly improved behavior, particularly when the MDP has reduced connectivity. To support this observation, we provide elements of com- parison between the two algorithms based on geometric considerations.
Construction auto-stabilisante d'arbre couvrant en dépit d'actions malicieuses
Venue: arXiv cs.DC 2010
Year: 2010

A self-stabilizing protocol provides by definition a tolerance to transient failures. Recently, a new class of self-stabilizing protocols appears. These protocols provides also a tolerance to a given number of permanent failures. In this article, we are interested in self-stabilizing protocols that deal with Byzantines failures. We prove that, for some problems which not allow strict stabilization (see [Nesterenko,Arora,2002]), there exist solutions that tolerates Byzantine faults if we define a new criteria of tolerance.
Multiple oligo nucleotide arrays: Methods to reduce manufacture time and cost
Venue: arXiv cs.DM 2010
Year: 2010

The customized multiple arrays are becoming vastly used in microarray experiments for varies purposes, mainly for its ability to handle a large quantity of data and output high quality results. However, experimenters who use customized multiple arrays still face many problems, such as the cost and time to manufacture the masks, and the cost for production of the multiple arrays by costly machines. Although there is some research on the multiple arrays, there is little concern on the manufacture time and cost, which is actually important to experimenters. In this paper, we have proposed methods to reduce the time and cost for the manufacture of the customized multiple arrays. We have first introduced a heuristic algorithm for the mask decomposition problem for multiple arrays. Then a streamline method is proposed for the integration of different steps of manufacture on a higher level. Experiments show that our methods are very effective in reduction of the time and cost of manufacture of multiple arrays.
Parallel algorithms in linear algebra
Venue: arXiv cs.DS 2010
Year: 2010

This report provides an introduction to algorithms for fundamental linear algebra problems on various parallel computer architectures, with the emphasis on distributed-memory MIMD machines. To illustrate the basic concepts and key issues, we consider the problem of parallel solution of a nonsingular linear system by Gaussian elimination with partial pivoting. This problem has come to be regarded as a benchmark for the performance of parallel machines. We consider its appropriateness as a benchmark, its communication requirements, and schemes for data distribution to facilitate communication and load balancing. In addition, we describe some parallel algorithms for orthogonal (QR) factorization and the singular value decomposition (SVD).