OpenRaiser/Intern-Atlas huggingface dataset:
Towards the Capacity Region of Multiplicative Linear Operator Broadcast Channels
Venue: arXiv cs.IT 2011
Year: 2011

Recent research indicates that packet transmission employing random linear network coding can be regarded as transmitting subspaces over a linear operator channel (LOC). In this paper we propose the framework of linear operator broadcast channels (LOBCs) to model packet broadcasting over LOCs, and we do initial work on the capacity region of constant-dimension multiplicative LOBCs(CMLOBCs), a generalization of broadcast erasure channels. Two fundamental problems regarding CMLOBCs are addressed-finding necessary and sufficient conditions for degradation and deciding whether time sharing suffices to achieve the boundary of the capacity region in the degraded case.
Small (2,s)-colorable graphs without 1-obstacle representations
Venue: arXiv cs.DM 2011
Year: 2011

An obstacle representation of a graph G is a set of points on the plane together with a set of polygonal obstacles that determine a visibility graph isomorphic to G. The obstacle number of G is the minimum number of obstacles over all obstacle representations of G. Alpert, Koch, and Laison gave a 12-vertex bipartite graph and proved that its obstacle number is two. We show that a 10-vertex induced subgraph of this graph has obstacle number two. Alpert et al. also constructed very large graphs with vertex set consisting of a clique and an independent set in order to show that obstacle number is an unbounded parameter. We specify a 70-vertex graph with vertex set consisting of a clique and an independent set, and prove that it has obstacle number greater than one. This is an ancillary document to our article in press. We conclude by showing that a 10-vertex graph with vertex set consisting of two cliques has obstacle number greater than one, improving on a result therein.
Enabling Node Repair in Any Erasure Code for Distributed Storage
Venue: arXiv cs.IT 2011
Year: 2011

Erasure codes are an efficient means of storing data across a network in comparison to data replication, as they tend to reduce the amount of data stored in the network and offer increased resilience in the presence of node failures. The codes perform poorly though, when repair of a failed node is called for, as they typically require the entire file to be downloaded to repair a failed node. A new class of erasure codes, termed as regenerating codes were recently introduced, that do much better in this respect. However, given the variety of efficient erasure codes available in the literature, there is considerable interest in the construction of coding schemes that would enable traditional erasure codes to be used, while retaining the feature that only a fraction of the data need be downloaded for node repair. In this paper, we present a simple, yet powerful, framework that does precisely this. Under this framework, the nodes are partitioned into two 'types' and encoded using two codes in a manner that reduces the problem of node-repair to that of erasure-decoding of the constituent codes. Depending upon the choice of the two codes, the framework can be used to avail one or more of the following advantages: simultaneous minimization of storage space and repair-bandwidth, low complexity of operation, fewer disk reads at helper nodes during repair, and error detection and correction.
Data Intensive High Energy Physics Analysis in a Distributed Cloud
Venue: arXiv cs.DC 2011
Year: 2011

We show that distributed Infrastructure-as-a-Service (IaaS) compute clouds can be effectively used for the analysis of high energy physics data. We have designed a distributed cloud system that works with any application using large input data sets requiring a high throughput computing environment. The system uses IaaS-enabled science and commercial clusters in Canada and the United States. We describe the process in which a user prepares an analysis virtual machine (VM) and submits batch jobs to a central scheduler. The system boots the user-specific VM on one of the IaaS clouds, runs the jobs and returns the output to the user. The user application accesses a central database for calibration data during the execution of the application. Similarly, the data is located in a central location and streamed by the running application. The system can easily run one hundred simultaneous jobs in an efficient manner and should scale to many hundreds and possibly thousands of user jobs.
Improved Achievable Rates for Regularized Tomlinson-Harashima Precoding in Multiuser MIMO Downlink
Venue: arXiv cs.IT 2011
Year: 2011

Tomlinson-Harashima precoding (THP) is considered as a prominent precoding scheme due to its capability to efficiently cancel out the known interference at the transmitter side. Therefore, the information rates achieved by THP are superior to those achieved by conventional linear precoding schemes. In this paper, a new lower bound on the achievable information rate for the regularized THP scheme under additive white Gaussian noise (AWGN) channel with multiuser interference is derived. Analytical results show that the lower bound derived in this paper is tighter than the original lower bound particularly for a low SNR range, while all lower bounds converge to 0.5xlog2(6SNR/πe) as SNR approaches infinity.
Lattice Reduction Aided Precoding for Multiuser MIMO using Seysen's Algorithm
Venue: arXiv cs.IT 2011
Year: 2011

Lenstra-Lenstra-Lovasz (LLL) algorithm, which is one of the lattice reduction (LR) techniques, has been extensively used to obtain better basis of the channel matrix. In this paper, we jointly apply Seysen's lattice reduction algorithm (SA), instead of LLL, with the conventional linear precoding algorithms. Since SA obtains more orthogonal lattice basis compared to that obtained by LLL, lattice reduction aided (LRA) precoding based on SA algorithm outperforms the LRA precoding with LLL. Simulation results demonstrate that a gain of 0.5dB at target BER of 10^-5 is achieved when SA is used instead of LLL for the LR stage.
Bandwidth and pathwidth of three-dimensional grids
Venue: arXiv cs.DM 2011
Year: 2011

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors.
Asymmetric Quantizers Are Better at Low SNR
Venue: arXiv cs.IT 2011
Year: 2011

We study the behavior of channel capacity when a one-bit quantizer is employed at the output of the discrete-time average-power-limited Gaussian channel. We focus on the low signal-to-noise ratio regime, where communication at very low spectral efficiencies takes place, as in Spread-Spectrum and Ultra-Wideband communications. It is well know that, in this regime, a symmetric one-bit quantizer reduces capacity by 2/pi, which translates to a power loss of approximately two decibels. Here we show that if an asymmetric one-bit quantizer is employed, and if asymmetric signal constellations are used, then these two decibels can be recovered in full.
On the Non-Termination of Ruppert's Algorithm
Venue: arXiv cs.CG 2011
Year: 2011

A planar straight-line graph which causes the non-termination Ruppert's algorithm for a minimum angle threshold larger than about 29.5 degrees is given. The minimum input angle of this example is about 74.5 degrees meaning that failure is not due to small input angles. Additionally, a similar non-acute input is given for which Chew's second algorithm does not terminate for a minimum angle threshold larger than about 30.7 degrees.
Almost Settling the Hardness of Noncommutative Determinant
Venue: arXiv cs.CC 2011
Year: 2011

In this paper, we study the complexity of computing the determinant of a matrix over a non-commutative algebra. In particular, we ask the question, "over which algebras, is the determinant easier to compute than the permanent?" Towards resolving this question, we show the following hardness and easiness of noncommutative determinant computation. * [Hardness] Computing the determinant of an n \times n matrix whose entries are themselves 2 \times 2 matrices over a field is as hard as computing the permanent over the field. This extends the recent result of Arvind and Srinivasan, who proved a similar result which however required the entries to be of linear dimension. * [Easiness] Determinant of an n \times n matrix whose entries are themselves d \times d upper triangular matrices can be computed in poly(n^d) time. Combining the above with the decomposition theorem of finite dimensional algebras (in particular exploiting the simple structure of 2 \times 2 matrix algebras), we can extend the above hardness and easiness statements to more general algebras as follows. Let A be a finite dimensional algebra over a finite field with radical R(A). * [Hardness] If the quotient A/R(A) is non-commutative, then computing the determinant over the algebra A is as hard as computing the permanent. * [Easiness] If the quotient A/R(A) is commutative and furthermore, R(A) has nilpotency index d (i.e., the smallest d such that R(A)d = 0), then there exists a poly(n^d)-time algorithm that computes determinants over the algebra A. In particular, for any constant dimensional algebra A over a finite field, since the nilpotency index of R(A) is at most a constant, we have the following dichotomy theorem: if A/R(A) is commutative, then efficient determinant computation is feasible and otherwise determinant is as hard as permanent.
Levenshtein Distance Technique in Dictionary Lookup Methods: An Improved Approach
Venue: arXiv cs.IT 2011
Year: 2011

Dictionary lookup methods are popular in dealing with ambiguous letters which were not recognized by Optical Character Readers. However, a robust dictionary lookup method can be complex as apriori probability calculation or a large dictionary size increases the overhead and the cost of searching. In this context, Levenshtein distance is a simple metric which can be an effective string approximation tool. After observing the effectiveness of this method, an improvement has been made to this method by grouping some similar looking alphabets and reducing the weighted difference among members of the same group. The results showed marked improvement over the traditional Levenshtein distance technique.
Non-clairvoyant Scheduling Games
Venue: arXiv cs.DS 2011
Year: 2011

In a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy -- the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time.
Linear Precoding for Relay Networks with Finite-Alphabet Constraints
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the optimal precoding scheme for relay networks with finite-alphabet constraints. We show that the previous work utilizing various design criteria to maximize either the diversity order or the transmission rate with the Gaussian-input assumption may lead to significant loss for a practical system with finite constellation set constraint. A linear precoding scheme is proposed to maximize the mutual information for relay networks. We exploit the structure of the optimal precoding matrix and develop a unified two-step iterative algorithm utilizing the theory of convex optimization and optimization on the complex Stiefel manifold. Numerical examples show that this novel iterative algorithm achieves significant gains compared to its conventional counterpart.
Application of Freeman Chain Codes: An Alternative Recognition Technique for Malaysian Car Plates
Venue: arXiv cs.CV 2011
Year: 2011

Various applications of car plate recognition systems have been developed using various kinds of methods and techniques by researchers all over the world. The applications developed were only suitable for specific country due to its standard specification endorsed by the transport department of particular countries. The Road Transport Department of Malaysia also has endorsed a specification for car plates that includes the font and size of characters that must be followed by car owners. However, there are cases where this specification is not followed. Several applications have been developed in Malaysia to overcome this problem. However, there is still problem in achieving 100% recognition accuracy. This paper is mainly focused on conducting an experiment using chain codes technique to perform recognition for different types of fonts used in Malaysian car plates.
Restarting Automata with Auxiliary Symbols and Small Lookahead
Venue: arXiv cs.FL 2011
Year: 2011

We present a study on lookahead hierarchies for restarting automata with auxiliary symbols and small lookahead. In particular, we show that there are just two different classes of languages recognised RRWW automata, through the restriction of lookahead size. We also show that the respective (left-) monotone restarting automaton models characterise the context-free languages and that the respective right-left-monotone restarting automata characterise the linear languages both with just lookahead length 2.
On Quadratic Programming with a Ratio Objective
Venue: arXiv cs.CC 2011
Year: 2011

Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. QP captures many known combinatorial optimization problems, and assuming the unique games conjecture, semidefinite programming techniques give optimal approximation algorithms. We extend this body of work by initiating the study of Quadratic Programming problems where the variables take values in the domain {-1,0,1}. The specific problems we study are QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum x_i^2}, and Normalized QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum d_i x_i^2}, where d_i = \sum_j |a_{ij}| We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an $\tilde{O}(n^{1/3})$ algorithm for QP-ratio. We also obtain an $\tilde{O}(n^{1/4})$ approximation for bipartite graphs, and better algorithms for special cases. As with other problems with ratio objectives (e.g. uniform sparsest cut), it seems difficult to obtain inapproximability results based on P!=NP. We give two results that indicate that QP-Ratio is hard to approximate to within any constant factor. We also give a natural distribution on instances of QP-Ratio for which an n^εapproximation (for εroughly 1/10) seems out of reach of current techniques.
Precise Schedulability Analysis for unfeasible to notify separately for comprehensive - EDF Scheduling of interrupted Hard Real-Time Tasks on the similar Multiprocessors
Venue: arXiv cs.SE 2011
Year: 2011

In Real-time system, utilization based schedulability test is a common approach to determine whether or not tasks can be admitted without violating deadline requirements. The exact problem has previously been proven intractable even upon single processors; sufficient conditions are presented here for determining whether a given periodic task system will meet all deadlines if scheduled non-preemptively upon a multiprocessor platform using the earliest-deadline first scheduling algorithm. Many real-time scheduling algorithms have been developed recently to reduce affinity in the portable devices that use processors. Extensive power aware scheduling techniques have been published for energy reduction, but most of them have been focused solely on reducing the processor affinity. The non-preemptive scheduling of periodic task systems upon processing platforms comprised of several same processors is considered.
A Novel Approach to the Statistical Modeling of Wireline Channels
Venue: arXiv cs.IT 2011
Year: 2011

We report here that channel power gain and Root-Mean-Square Delay Spread (RMS-DS) in Low/Medium Voltage power line channels are negatively correlated lognormal random variables. Further analysis of other wireline channels allows us to report a strong similarity between some properties observed in power line channels and the ones observed in other wireline channels, e.g. coaxial cables and phone lines. For example, it is here reported that channel power gain and logarithm of the RMS-DS in DSL links are \textit{linearly} correlated random variables. Exploiting these results, we here propose a statistical wireline channel model where tap amplitudes and delays are generated in order to reflect these physical properties. Although wireline channels are considered deterministic as their impulse response can be readily calculated once the link topology is known, a statistical wireline channel model is useful because the variability of link topologies and wiring practices give rise to a stochastic aspect of wireline communications that has not been well characterized in the literature. Finally, we also point out that alternative channel models that normalize impulse responses to a common (often unitary) power gain may be misleading when assessing the performance of equalization schemes since this normalization artificially removes the correlation between channel power gain and RMS-DS and, thus, Inter-Symbol Interference (ISI).
Distributed Consensus on Set-valued Information
Venue: arXiv cs.RO 2011
Year: 2011

This paper focuses on the convergence of infor- mation in distributed systems of agents communicating over a network. The information on which the convergence is sought is not represented by real numbers, rather by sets of real numbers, whose possible dynamics are given by the class of so-called Boolean maps, involving only unions, intersections, and complements of sets. Based on a notion of contractivity, a necessary and sufficient condition ensuring the global and local convergence toward an equilibrium point is presented. In particular the analysis of global convergence recovers results already obtained by the authors, but the more general approach used in this paper allows analogue results to be found to characterize the local convergence.
Planning with Partial Preference Models
Venue: arXiv cs.AI 2011
Year: 2011

Current work in planning with preferences assume that the user's preference models are completely specified and aim to search for a single solution plan. In many real-world planning scenarios, however, the user probably cannot provide any information about her desired plans, or in some cases can only express partial preferences. In such situations, the planner has to present not only one but a set of plans to the user, with the hope that some of them are similar to the plan she prefers. We first propose the usage of different measures to capture quality of plan sets that are suitable for such scenarios: domain-independent distance measures defined based on plan elements (actions, states, causal links) if no knowledge of the user's preferences is given, and the Integrated Convex Preference measure in case the user's partial preference is provided. We then investigate various heuristic approaches to find set of plans according to these measures, and present empirical results demonstrating the promise of our approach.
Domain decomposition schemes for evolutionary equations of first order with not self-adjoint operators
Venue: arXiv cs.NA 2011
Year: 2011

Domain decomposition methods are essential in solving applied problems on parallel computer systems. For boundary value problems for evolutionary equations the implicit schemes are in common use to solve problems at a new time level employing iterative methods of domain decomposition. An alternative approach is based on constructing iteration-free methods based on special schemes of splitting into subdomains. Such regionally-additive schemes are constructed using the general theory of additive operator-difference schemes. There are employed the analogues of classical schemes of alternating direction method, locally one-dimensional schemes, factorization methods, vector and regularized additive schemes. The main results were obtained here for time-dependent problems with self-adjoint elliptic operators of second order. The paper discusses the Cauchy problem for the first order evolutionary equations with a nonnegative not self-adjoint operator in a finite-dimensional Hilbert space. Based on the partition of unit, we have constructed the operators of decomposition which preserve nonnegativity for the individual operator terms of splitting. Unconditionally stable additive schemes of domain decomposition were constructed using the regularization principle for operator-difference schemes. Vector additive schemes were considered, too. The results of our work are illustrated by a model problem for the two-dimensional parabolic equation.
A Review of Research on Devnagari Character Recognition
Venue: arXiv cs.CV 2011
Year: 2011

English Character Recognition (CR) has been extensively studied in the last half century and progressed to a level, sufficient to produce technology driven applications. But same is not the case for Indian languages which are complicated in terms of structure and computations. Rapidly growing computational power may enable the implementation of Indic CR methodologies. Digital document processing is gaining popularity for application to office and library automation, bank and postal services, publishing houses and communication technology. Devnagari being the national language of India, spoken by more than 500 million people, should be given special attention so that document retrieval and analysis of rich ancient and modern Indian literature can be effectively done. This article is intended to serve as a guide and update for the readers, working in the Devnagari Optical Character Recognition (DOCR) area. An overview of DOCR systems is presented and the available DOCR techniques are reviewed. The current status of DOCR is discussed and directions for future research are suggested.
On Logical Extension of Algebraic Division
Venue: arXiv cs.LO 2011
Year: 2011

Basic arithmetic is the cornerstone of mathematics and computer sciences. In arithmetic, 'division by zero' is an undefined operation and any attempt at extending logic for algebraic division to incorporate division by zero has resulted in paradoxes and fallacies. However, there is no proven theorem or mathematical logic that suggests that, defining logic for division by zero would result in break-down of theory. Basing on this motivation, in this paper, we attempt at logically defining a solution for 'division by zero' problem.