OpenRaiser/Intern-Atlas huggingface dataset:
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Venue: arXiv cs.CC 2010
Year: 2010

We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the logspace complexity class \SPL. Since \SPL\ is contained in the logspace counting classes $\oplusŁ$ (in fact in \modk\ for all $k\geq 2$), \CeqL, and \PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs is in $\FL^{\SPL}$. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a logspace computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function.
Analysis of Feedback Overhead for MIMO Beamforming over Time-Varying Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, the required amount of feedback overhead for multiple-input multiple-output (MIMO) beamforming over time-varying channels is presented in terms of the entropy of the feedback messages. In the case that each transmit antenna has its own power amplifier which has individual power limit, it has been known that only phase steering information is necessary to form the optimal transmit beamforming vector. Since temporal correlation exists for wireless fading channels, one can utilize the previous reported feedback messages as prior information to efficiently encode the current feedback message. Thus, phase tracking information, difference between two phase steering information in adjacent feedback slots, is sufficient as a feedback message. We show that while the entropy of the phase steering information is a constant, the entropy of the phase tracking information is a function of the temporal correlation parameter. For the phase tracking information, upperbounds on the entropy are presented in the Gaussian entropy and the von-Mises entropy by using the theory on the maximum entropy distributions. Derived results can quantify the amount of reduction in feedback overhead of the phase tracking information over the phase steering information. For application perspective, the signal-to-noise ratio (SNR) gain of phase tracking beamforming over phase steering beamforming is evaluated by using Monte-Carlo simulation. Also we show that the derived entropies can determine the appropriate duration of the feedback reports with respect to the degree of the channel variation rates.
Circuits with arbitrary gates for random operators
Venue: arXiv cs.CC 2010
Year: 2010

We consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As gates we allow arbitrary boolean functions; neither fanin nor fanout of gates is restricted. An operator is linear if it computes n linear forms, that is, computes a matrix-vector product y=Ax over GF(2). We prove the existence of n-operators requiring about n^2 wires in any circuit, and linear n-operators requiring about n^2/\log n wires in depth-2 circuits, if either all output gates or all gates on the middle layer are linear.
A characterization of b-perfect graphs
Venue: arXiv cs.DM 2010
Year: 2010

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number of a graph $G$ is the largest integer $k$ such that $G$ admits a b-coloring with $k$ colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph of $G$. We prove that a graph is b-perfect if and only if it does not contain as an induced subgraph a member of a certain list of twenty-two graphs. This entails the existence of a polynomial-time recognition algorithm and of a polynomial-time algorithm for coloring exactly the vertices of every b-perfect graph.
Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
Venue: arXiv cs.CG 2010
Year: 2010

Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the distance between two points p,q in R^2 in the normed plane whose unit ball is B. For a set T of n points (terminals) in R^2, a B-Manhattan network on T is a network N(T) = (V,E) with the property that its edges are parallel to the directions of B and for every pair of terminals t_i and t_j, the network N(T) contains a shortest B-path between them, i.e., a path of length || t_i - t_j ||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum possible length. The problem of finding minimum B-Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case when the unit ball B is a square (and hence the distance || p - q || is the l_1 or the l_infty-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for minimum B-Manhattan network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (APPROX'05) and subsequently used in other factor 2 approximation algorithms for minimum Manhattan problem.
Fully Countering Trusting Trust through Diverse Double-Compiling
Venue: arXiv cs.CR 2010
Year: 2010

An Air Force evaluation of Multics, and Ken Thompson's Turing award lecture ("Reflections on Trusting Trust"), showed that compilers can be subverted to insert malicious Trojan horses into critical software, including themselves. If this "trusting trust" attack goes undetected, even complete analysis of a system's source code will not find the malicious code that is running. Previously-known countermeasures have been grossly inadequate. If this attack cannot be countered, attackers can quietly subvert entire classes of computer systems, gaining complete control over financial, infrastructure, military, and/or business systems worldwide. This dissertation's thesis is that the trusting trust attack can be detected and effectively countered using the "Diverse Double-Compiling" (DDC) technique, as demonstrated by (1) a formal proof that DDC can determine if source code and generated executable code correspond, (2) a demonstration of DDC with four compilers (a small C compiler, a small Lisp compiler, a small maliciously corrupted Lisp compiler, and a large industrial-strength C compiler, GCC), and (3) a description of approaches for applying DDC in various real-world scenarios. In the DDC technique, source code is compiled twice: the source code of the compiler's parent is compiled using a trusted compiler, and then the putative compiler source code is compiled using the result of the first compilation. If the DDC result is bit-for-bit identical with the original compiler-under-test's executable, and certain other assumptions hold, then the compiler-under-test's executable corresponds with its putative source code.
Countering Trusting Trust through Diverse Double-Compiling
Venue: arXiv cs.CR 2010
Year: 2010

An Air Force evaluation of Multics, and Ken Thompson's famous Turing award lecture "Reflections on Trusting Trust," showed that compilers can be subverted to insert malicious Trojan horses into critical software, including themselves. If this attack goes undetected, even complete analysis of a system's source code will not find the malicious code that is running, and methods for detecting this particular attack are not widely known. This paper describes a practical technique, termed diverse double-compiling (DDC), that detects this attack and some compiler defects as well. Simply recompile the source code twice: once with a second (trusted) compiler, and again using the result of the first compilation. If the result is bit-for-bit identical with the untrusted binary, then the source code accurately represents the binary. This technique has been mentioned informally, but its issues and ramifications have not been identified or discussed in a peer-reviewed work, nor has a public demonstration been made. This paper describes the technique, justifies it, describes how to overcome practical challenges, and demonstrates it.
Near MDS poset codes and distributions
Venue: arXiv cs.IT 2010
Year: 2010

We study $q$-ary codes with distance defined by a partial order of the coordinates of the codewords. Maximum Distance Separable (MDS) codes in the poset metric have been studied in a number of earlier works. We consider codes that are close to MDS codes by the value of their minimum distance. For such codes, we determine their weight distribution, and in the particular case of the "ordered metric" characterize distributions of points in the unit cube defined by the codes. We also give some constructions of codes in the ordered Hamming space.
On the Joint Decoding of LDPC Codes and Finite-State Channels via Linear Programming
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, the linear programming (LP) decoder for binary linear codes, introduced by Feldman, et al. is extended to joint-decoding of binary-input finite-state channels. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the LP joint decoder also has the maximum-likelihood (ML) certificate property and all integer valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional valued JD-PCWs.
Adaptive Bases for Reinforcement Learning
Venue: arXiv cs.LG 2010
Year: 2010

We consider the problem of reinforcement learning using function approximation, where the approximating basis can change dynamically while interacting with the environment. A motivation for such an approach is maximizing the value function fitness to the problem faced. Three errors are considered: approximation square error, Bellman residual, and projected Bellman residual. Algorithms under the actor-critic framework are presented, and shown to converge. The advantage of such an adaptive basis is demonstrated in simulations.
Software Requirements Specification of the IUfA's UUIS -- a Team 4 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

This document presents the business requirement of Unified University Inventory System (UUIS) in Technology-independent manner. All attempts have been made in using mostly business terminology and business language while describing the requirements in this document. Very minimal and commonly understood Technical terminology is used. Use case approach is used in modeling the business requirements in this document.
Analysis of Non-Persistent CSMA Protocols with Exponential Backoff Scheduling
Venue: arXiv cs.NI 2010
Year: 2010

This paper studies the performance of Non-persistent CSMA/CA protocols with K-Exponential Backoff scheduling algorithms. A multi-queue single-server system is proposed to model multiple access networks. The input buffer of each access node is modeled as a Geo/G/1 queue, and the service time distribution of head-of-line packets is derived from the Markov chain of underlying scheduling algorithm. The main results include the complete analysis of the throughput and delay distribution, from which we obtained stable regions with respect to the throughput and bounded mean delay of the Geometric Retransmission and Exponential Backoff schemes. We show that the throughput stable region of Geometric Retransmission will vanish as the number of nodes n \rightarrow \infty; thus, it is inherently unstable for large n. In contrast to Geometric Retransmission, the throughput stable region of Exponential Backoff can be obtained for an infinite population. We found that the bounded mean delay region of Geometric Retransmission remains the same as its throughput stable region. Besides, the variance of service time of Exponential Backoff can be unbounded due to the capture effect; thus, its bounded delay region is only a sub-set of its throughput stable region. Analytical results presented in this paper are all verified by simulation.
Smart matching
Venue: arXiv cs.LO 2010
Year: 2010

One of the most annoying aspects in the formalization of mathematics is the need of transforming notions to match a given, existing result. This kind of transformations, often based on a conspicuous background knowledge in the given scientific domain (mostly expressed in the form of equalities or isomorphisms), are usually implicit in the mathematical discourse, and it would be highly desirable to obtain a similar behavior in interactive provers. The paper describes the superposition-based implementation of this feature inside the Matita interactive theorem prover, focusing in particular on the so called smart application tactic, supporting smart matching between a goal and a given result.
The Deletable Bloom filter: A new member of the Bloom family
Venue: arXiv cs.DS 2010
Year: 2010

We introduce the Deletable Bloom filter (DlBF) as a new spin on the popular data structure based on compactly encoding the information of where collisions happen when inserting elements. The DlBF design enables false-negative-free deletions at a fraction of the cost in memory consumption, which turns to be appealing for certain probabilistic filter applications.
Capacity-Equivocation Region of the Gaussian MIMO Wiretap Channel
Venue: arXiv cs.IT 2010
Year: 2010

We study the Gaussian multiple-input multiple-output (MIMO) wiretap channel, which consists of a transmitter, a legitimate user, and an eavesdropper. In this channel, the transmitter sends a common message to both the legitimate user and the eavesdropper. In addition to this common message, the legitimate user receives a private message, which is desired to be kept hidden as much as possible from the eavesdropper. We obtain the entire capacity-equivocation region of the Gaussian MIMO wiretap channel. This region contains all achievable common message, private message, and private message's equivocation (secrecy) rates. In particular, we show the sufficiency of jointly Gaussian auxiliary random variables and channel input to evaluate the existing single-letter description of the capacity-equivocation region due to Csiszar-Korner.
General Ramified Recurrence is Sound for Polynomial Time
Venue: arXiv cs.LO 2010
Year: 2010

Leivant's ramified recurrence is one of the earliest examples of an implicit characterization of the polytime functions as a subalgebra of the primitive recursive functions. Leivant's result, however, is originally stated and proved only for word algebras, i.e. free algebras whose constructors take at most one argument. This paper presents an extension of these results to ramified functions on any free algebras, provided the underlying terms are represented as graphs rather than trees, so that sharing of identical subterms can be exploited.
Adaptive MAC Protocols Using Memory for Networks with Critical Traffic
Venue: arXiv cs.NI 2010
Year: 2010

We consider wireless communication networks where network users are subject to critical events such as emergencies and crises. If a critical event occurs to a user, the user needs to send critical traffic as early as possible. However, most existing medium access control (MAC) protocols are not adequate to meet the urgent need for data transmission by users with critical traffic. In this paper, we devise a class of distributed MAC protocols that achieve coordination using the finite-length memory of users containing their own observations and traffic types. We formulate a protocol design problem and find optimal protocols that solve the problem. We show that the proposed protocols enable a user with critical traffic to transmit its critical traffic without interruption from other users after a short delay while allowing users to share the channel efficiently when there is no critical traffic. Moreover, the proposed protocols require short memory and can be implemented without explicit message passing.
The Production of Probabilistic Entropy in Structure/Action Contingency Relations
Venue: arXiv cs.AI 2010
Year: 2010

Luhmann (1984) defined society as a communication system which is structurally coupled to, but not an aggregate of, human action systems. The communication system is then considered as self-organizing ("autopoietic"), as are human actors. Communication systems can be studied by using Shannon's (1948) mathematical theory of communication. The update of a network by action at one of the local nodes is then a well-known problem in artificial intelligence (Pearl 1988). By combining these various theories, a general algorithm for probabilistic structure/action contingency can be derived. The consequences of this contingency for each system, its consequences for their further histories, and the stabilization on each side by counterbalancing mechanisms are discussed, in both mathematical and theoretical terms. An empirical example is elaborated.
Comparing Repository Types - Challenges and barriers for subject-based repositories, research repositories, national repository systems and institutional repositories in serving scholarly communication
Venue: arXiv cs.DL 2010
Year: 2010

After two decades of repository development, some conclusions may be drawn as to which type of repository and what kind of service best supports digital scholarly communication, and thus the production of new knowledge. Four types of publication repository may be distinguished, namely the subject-based repository, research repository, national repository system and institutional repository. Two important shifts in the role of repositories may be noted. With regard to content, a well-defined and high quality corpus is essential. This implies that repository services are likely to be most successful when constructed with the user and reader uppermost in mind. With regard to service, high value to specific scholarly communities is essential. This implies that repositories are likely to be most useful to scholars when they offer dedicated services supporting the production of new knowledge. Along these lines, challenges and barriers to repository development may be identified in three key dimensions: a) identification and deposit of content; b) access and use of services; and c) preservation of content and sustainability of service. An indicative comparison of challenges and barriers in some major world regions such as Europe, North America and East Asia plus Australia is offered in conclusion.
The Complex Gaussian Kernel LMS algorithm
Venue: arXiv cs.LG 2010
Year: 2010

Although the real reproducing kernels are used in an increasing number of machine learning problems, complex kernels have not, yet, been used, in spite of their potential interest in applications such as communications. In this work, we focus our attention on the complex gaussian kernel and its possible application in the complex Kernel LMS algorithm. In order to derive the gradients needed to develop the complex kernel LMS (CKLMS), we employ the powerful tool of Wirtinger's Calculus, which has recently attracted much attention in the signal processing community. Writinger's calculus simplifies computations and offers an elegant tool for treating complex signals. To this end, the notion of Writinger's calculus is extended to include complex RKHSs. Experiments verify that the CKLMS offers significant performance improvements over the traditional complex LMS or Widely Linear complex LMS (WL-LMS) algorithms, when dealing with nonlinearities.
Multistage Hybrid Arabic/Indian Numeral OCR System
Venue: arXiv cs.CV 2010
Year: 2010

The use of OCR in postal services is not yet universal and there are still many countries that process mail sorting manually. Automated Arabic/Indian numeral Optical Character Recognition (OCR) systems for Postal services are being used in some countries, but still there are errors during the mail sorting process, thus causing a reduction in efficiency. The need to investigate fast and efficient recognition algorithms/systems is important so as to correctly read the postal codes from mail addresses and to eliminate any errors during the mail sorting stage. The objective of this study is to recognize printed numerical postal codes from mail addresses. The proposed system is a multistage hybrid system which consists of three different feature extraction methods, i.e., binary, zoning, and fuzzy features, and three different classifiers, i.e., Hamming Nets, Euclidean Distance, and Fuzzy Neural Network Classifiers. The proposed system, systematically compares the performance of each of these methods, and ensures that the numerals are recognized correctly. Comprehensive results provide a very high recognition rate, outperforming the other known developed methods in literature.
Semi-Trusted Mixer Based Privacy Preserving Distributed Data Mining for Resource Constrained Devices
Venue: arXiv cs.CR 2010
Year: 2010

In this paper a homomorphic privacy preserving association rule mining algorithm is proposed which can be deployed in resource constrained devices (RCD). Privacy preserved exchange of counts of itemsets among distributed mining sites is a vital part in association rule mining process. Existing cryptography based privacy preserving solutions consume lot of computation due to complex mathematical equations involved. Therefore less computation involved privacy solutions are extremely necessary to deploy mining applications in RCD. In this algorithm, a semi-trusted mixer is used to unify the counts of itemsets encrypted by all mining sites without revealing individual values. The proposed algorithm is built on with a well known communication efficient association rule mining algorithm named count distribution (CD). Security proofs along with performance analysis and comparison show the well acceptability and effectiveness of the proposed algorithm. Efficient and straightforward privacy model and satisfactory performance of the protocol promote itself among one of the initiatives in deploying data mining application in RCD.
Adaptive Slot Allocation And Bandwidth Sharing For Prioritized Handoff Calls In Mobile Netwoks
Venue: arXiv cs.NI 2010
Year: 2010

Mobility management and bandwidth management are two major research issues in a cellular mobile network. Mobility management consists of two basic components: location management and handoff management. To Provide QoS to the users Handoff is a key element in wireless cellular networks. It is often initiated either by crossing a cell boundary or by deterioration in the quality of signal in the current channel. In this paper, a new admission control policy for cellular mobile network is being proposed. Two important QoS parameter in cellular networks are Call Dropping Probability (CDP) and Handoff Dropping Probability (HDP). CDP represents the probability that a call is dropped due to a handoff failure. HDP represents the probability of a handoff failure due to insufficient available resources in the target cell. Most of the algorithms try to limit the HDP to some target maximum but not CDP. In this paper, we show that when HDP is controlled, the CDP is also controlled to a minimum extent while maintaining lower blocking rates for new calls in the system.