OpenRaiser/Intern-Atlas huggingface dataset:
Uncertainty Updating in the Description of Coupled Heat and Moisture Transport in Heterogeneous Materials
Venue: arXiv cs.NA 2011
Year: 2011

To assess the durability of structures, heat and moisture transport need to be analyzed. To provide a reliable estimation of heat and moisture distribution in a certain structure, one needs to include all available information about the loading conditions and material parameters. Moreover, the information should be accompanied by a corresponding evaluation of its credibility. Here, the Bayesian inference is applied to combine different sources of information, so as to provide a more accurate estimation of heat and moisture fields [1]. The procedure is demonstrated on the probabilistic description of heterogeneous material where the uncertainties consist of a particular value of individual material characteristic and spatial fluctuations. As for the heat and moisture transfer, it is modelled in coupled setting [2].
Physical-Layer MIMO Relaying
Venue: arXiv cs.IT 2011
Year: 2011

The physical-layer network coding (PNC) approach provides improved performance in many scenarios over "traditional" relaying techniques or network coding. This work addresses the generalization of PNC to wireless scenarios where network nodes have multiple antennas. We use a recent matrix decomposition, which allows, by linear pre- and post-processing, to simultaneously transform both channel matrices to triangular forms, where the diagonal entries, corresponding to both channels, are equal. This decomposition, in conjunction with precoding, allows to convert any two-input multiple-access channel (MAC) into parallel MACs, over which single-antenna PNC may be used. The technique is demonstrated using the two-way relay channel with multiple antennas. For this case it is shown that, in the high signal-to-noise regime, the scheme approaches the cut-set bound, thus establishing the asymptotic network capacity.
On Outage Probability and Diversity-Multiplexing Tradeoff in MIMO Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

Fading MIMO relay channels are studied analytically, when the source and destination are equipped with multiple antennas and the relays have a single one. Compact closed-form expressions are obtained for the outage probability under i.i.d. and correlated Rayleigh-fading links. Low-outage approximations are derived, which reveal a number of insights, including the impact of correlation, of the number of antennas, of relay noise and of relaying protocol. The effect of correlation is shown to be negligible, unless the channel becomes almost fully correlated. The SNR loss of relay fading channels compared to the AWGN channel is quantified. The SNR-asymptotic diversity-multiplexing tradeoff (DMT) is obtained for a broad class of fading distributions, including, as special cases, Rayleigh, Rice, Nakagami, Weibull, which may be non-identical, spatially correlated and/or non-zero mean. The DMT is shown to depend not on a particular fading distribution, but rather on its polynomial behavior near zero, and is the same for the simple "amplify-and-forward" protocol and more complicated "decode-and-forward" one with capacity achieving codes, i.e. the full processing capability at the relay does not help to improve the DMT. There is however a significant difference between the SNR-asymptotic DMT and the finite-SNR outage performance: while the former is not improved by using an extra antenna on either side, the latter can be significantly improved and, in particular, an extra antenna can be traded-off for a full processing capability at the relay. The results are extended to the multi-relay channels with selection relaying and typical outage events are identified.
Blind Adaptive Subcarrier Combining Technique for MC-CDMA Receiver in Mobile Rayleigh Channel
Venue: arXiv cs.IT 2011
Year: 2011

A new subcarrier combining technique is proposed for MC -CDMA receiver in mobile Rayleigh fading channel. It exploits the structure formed by repeating spreading sequences of users on different subcarriers to simultaneously suppress multiple access interference (MAI) and provide implicit channel tracking without any knowledge of the channel amplitudes or training sequences. This is achieved by adaptively weighting each subcarrier in each symbol period by employing a simple gradient descent algorithm to meet the constant modulus (CM) criterion with judicious selection of step-size. Improved BER and user capacity performance are shown with similar complexity in order of O(N) compared with conventional maximum ratio combining and equal gain combining techniques even under high channel Doppler rates.
Back and Forth Between Rules and SE-Models (Extended Version)
Venue: arXiv cs.AI 2011
Year: 2011

Rules in logic programming encode information about mutual interdependencies between literals that is not captured by any of the commonly used semantics. This information becomes essential as soon as a program needs to be modified or further manipulated. We argue that, in these cases, a program should not be viewed solely as the set of its models. Instead, it should be viewed and manipulated as the set of sets of models of each rule inside it. With this in mind, we investigate and highlight relations between the SE-model semantics and individual rules. We identify a set of representatives of rule equivalence classes induced by SE-models, and so pinpoint the exact expressivity of this semantics with respect to a single rule. We also characterise the class of sets of SE-interpretations representable by a single rule. Finally, we discuss the introduction of two notions of equivalence, both stronger than strong equivalence [1] and weaker than strong update equivalence [2], which seem more suitable whenever the dependency information found in rules is of interest.
Linear Programming based Detectors for Two-Dimensional Intersymbol Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

We present and study linear programming based detectors for two-dimensional intersymbol interference channels. Interesting instances of two-dimensional intersymbol interference channels are magnetic storage, optical storage and Wyner's cellular network model. We show that the optimal maximum a posteriori detection in such channels lends itself to a natural linear programming based sub-optimal detector. We call this the Pairwise linear program detector. Our experiments show that the Pairwise linear program detector performs poorly. We then propose two methods to strengthen our detector. These detectors are based on systematically enhancing the Pairwise linear program. The first one, the Block linear program detector adds higher order potential functions in an {\em exhaustive} manner, as constraints, to the Pairwise linear program detector. We show by experiments that the Block linear program detector has performance close to the optimal detector. We then develop another detector by {\em adaptively} adding frustrated cycles to the Pairwise linear program detector. Empirically, this detector also has performance close to the optimal one and turns out to be less complex then the Block linear program detector.
Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines
Venue: arXiv cs.CC 2011
Year: 2011

The aim of this paper is to undertake an experimental investigation of the trade-offs between program-size and time computational complexity. The investigation includes an exhaustive exploration and systematic study of the functions computed by the set of all 2-color Turing machines with 2, 3 and 4 states--denoted by (n,2) with n the number of states--with particular attention to the runtimes and space usages when the machines have access to larger resources (more states). We report that the average runtime of Turing machines computing a function almost surely increases as a function of the number of states, indicating that machines not terminating (almost) immediately tend to occupy all the resources at hand. We calculated all time complexity classes to which the algorithms computing the functions found in both (2,2) and (3,2) belong to, and made a comparison among these classes. For a selection of functions the comparison was extended to (4,2). Our study revealed various structures in the micro-cosmos of small Turing machines. Most notably we observed "phase-transitions" in the halting-probability distribution that we explain. Moreover, it is observed that short initial segments fully define a function computed by a Turing machine.
Complete Subdivision Algorithms, II: Isotopic Meshing of Singular Algebraic Curves
Venue: arXiv cs.CG 2011
Year: 2011

Given a real valued function f(X,Y), a box region B_0 in R^2 and a positive epsilon, we want to compute an epsilon-isotopic polygonal approximation to the restriction of the curve S=f^{-1}(0)={p in R^2: f(p)=0} to B_0. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga and Vegter gave a numerical subdivision algorithm that is exact when the curve S is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of S. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.
Pseudo-random graphs and bit probe schemes with one-sided error
Venue: arXiv cs.DS 2011
Year: 2011

We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of type "Is x in A?" can be answered very quickly. H.Buhrman, P.B.Miltersen, J.Radhakrishnan, and S.Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of $O(n\log m)$ bits, and requires to read only one randomly chosen bit from the memory to answer a query. The answer is correct with high probability with two-sided errors. In this paper we show that for the same problem there exists a bit-probe scheme with one-sided error that needs space of $O(n\log^2 m+\poly(\log m))$ bits. The difference with the model of Buhrman, Miltersen, Radhakrishnan, and Venkatesh is that we consider a bit-probe scheme with an auxiliary word. This means that in our scheme the memory is split into two parts of different size: the main storage of $O(n\log^2 m)$ bits and a short word of $\log^{O(1)}m$ bits that is pre-computed once for the stored set A and `cached'. To answer a query "Is x in A?" we allow to read the whole cached word and only one bit from the main storage. For some reasonable values of parameters our space bound is better than what can be achieved by any scheme without cached data.
Low Complexity Kolmogorov-Smirnov Modulation Classification
Venue: arXiv cs.IT 2011
Year: 2011

Kolmogorov-Smirnov (K-S) test-a non-parametric method to measure the goodness of fit, is applied for automatic modulation classification (AMC) in this paper. The basic procedure involves computing the empirical cumulative distribution function (ECDF) of some decision statistic derived from the received signal, and comparing it with the CDFs of the signal under each candidate modulation format. The K-S-based modulation classifier is first developed for AWGN channel, then it is applied to OFDM-SDMA systems to cancel multiuser interference. Regarding the complexity issue of K-S modulation classification, we propose a low-complexity method based on the robustness of the K-S classifier. Extensive simulation results demonstrate that compared with the traditional cumulant-based classifiers, the proposed K-S classifier offers superior classification performance and requires less number of signal samples (thus is fast).
On Expressive Powers of Timed Logics: Comparing Boundedness, Non-punctuality and Deterministic Freezing
Venue: arXiv cs.LO 2011
Year: 2011

Timed temporal logics exhibit a bewildering diversity of operators and the resulting decidability and expressiveness properties also vary considerably. We study the expressive power of timed logics TPTL[U,S] and MTL[U,S] as well as of their several fragments. Extending the LTL EF games of Etessami and Wilke, we define MTL Ehrenfeucht-Fraisse games on a pair of timed words. Using the associated EF theorem, we show that, expressively, the timed logics BoundedMTL[U,S], MTL[F,P] and MITL[U,S] (respectively incorporating the restrictions of boundedness, unary modalities and non-punctuality), are all pairwise incomparable. As our first main result, we show that MTL[U,S] is strictly contained within the freeze logic TPTL[U,S] for both weakly and strictly monotonic timed words, thereby extending the result of Bouyer et al and completing the proof of the original conjecture of Alur and Henziger from 1990. We also relate the expressiveness of a recently proposed deterministic freeze logic TTL[X,Y] (with NP-complete satisfiability) to MTL. As our second main result, we show by an explicit reduction that TTL[X,Y] lies strictly within the unary, non-punctual logic MITL[F,P]. This shows that deterministic freezing with punctuality is expressible in the non-punctual MITL[F,P].
Reliable Physical Layer Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

When two or more users in a wireless network transmit simultaneously, their electromagnetic signals are linearly superimposed on the channel. As a result, a receiver that is interested in one of these signals sees the others as unwanted interference. This property of the wireless medium is typically viewed as a hindrance to reliable communication over a network. However, using a recently developed coding strategy, interference can in fact be harnessed for network coding. In a wired network, (linear) network coding refers to each intermediate node taking its received packets, computing a linear combination over a finite field, and forwarding the outcome towards the destinations. Then, given an appropriate set of linear combinations, a destination can solve for its desired packets. For certain topologies, this strategy can attain significantly higher throughputs over routing-based strategies. Reliable physical layer network coding takes this idea one step further: using judiciously chosen linear error-correcting codes, intermediate nodes in a wireless network can directly recover linear combinations of the packets from the observed noisy superpositions of transmitted signals. Starting with some simple examples, this survey explores the core ideas behind this new technique and the possibilities it offers for communication over interference-limited wireless networks.
A Truthful Randomized Mechanism for Combinatorial Public Projects via Convex Optimization
Venue: arXiv cs.GT 2011
Year: 2011

In Combinatorial Public Projects, there is a set of projects that may be undertaken, and a set of self-interested players with a stake in the set of projects chosen. A public planner must choose a subset of these projects, subject to a resource constraint, with the goal of maximizing social welfare. Combinatorial Public Projects has emerged as one of the paradigmatic problems in Algorithmic Mechanism Design, a field concerned with solving fundamental resource allocation problems in the presence of both selfish behavior and the computational constraint of polynomial-time. We design a polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental variant of combinatorial public projects. Our results apply to combinatorial public projects when players have valuations that are matroid rank sums (MRS), which encompass most concrete examples of submodular functions studied in this context, including coverage functions, matroid weighted-rank functions, and convex combinations thereof. Our approximation factor is the best possible, assuming P != NP. Ours is the first mechanism that achieves a constant factor approximation for a natural NP-hard variant of combinatorial public projects.
Interference Alignment and Degrees of Freedom Region of Cellular Sigma Channel
Venue: arXiv cs.IT 2011
Year: 2011

We investigate the Degrees of Freedom (DoF) Region of a cellular network, where the cells can have overlapping areas. Within an overlapping area, the mobile users can access multiple base stations. We consider a case where there are two base stations both equipped with multiple antennas. The mobile stations are all equipped with single antenna and each mobile station can belong to either a single cell or both cells. We completely characterize the DoF region for the uplink channel assuming that global channel state information is available at the transmitters. The achievability scheme is based on interference alignment at the base stations.
Computing an Aggregate Edge-Weight Function for Clustering Graphs with Multiple Edge Types
Venue: arXiv cs.SI 2011
Year: 2011

We investigate the community detection problem on graphs in the existence of multiple edge types. Our main motivation is that similarity between objects can be defined by many different metrics and aggregation of these metrics into a single one poses several important challenges, such as recovering this aggregation function from ground-truth, investigating the space of different clusterings, etc. In this paper, we address how to find an aggregation function to generate a composite metric that best resonates with the ground-truth. We describe two approaches: solving an inverse problem where we try to find parameters that generate a graph whose clustering gives the ground-truth clustering, and choosing parameters to maximize the quality of the ground-truth clustering. We present experimental results on real and synthetic benchmarks.
Paranoid Secondary: Waterfilling in a Cognitive Interference Channel with Partial Information
Venue: arXiv cs.IT 2011
Year: 2011

We study a two-user cognitive channel, where the primary flow is sporadic, cannot be re-designed and operating below its link capacity. To study the impact of primary traffic uncertainty, we propose a block activity model that captures the random on-off periods of primary's transmissions. Each block in the model can be split into parallel Gaussian-mixture channels, such that each channel resembles a multiple user channel (MAC) from the point of view of the secondary user. The secondary senses the current state of the primary at the start of each block. We show that the optimal power transmitted depends on the sensed state and the optimal power profile is paranoid, i.e. either growing or decaying in power as a function of time. We show that such a scheme achieves capacity when there is no noise in the sensing. The optimal transmission for the secondary performs rate splitting and follows a layered water-filling power allocation for each parallel channel to achieve capacity. The secondary rate approaches a genie-aided scheme for large block-lengths. Additionally, if the fraction of time primary uses the channel tends to one, the paranoid scheme and the genie-aided upper bound get arbitrarily close to a no-sensing scheme.
An Algorithm for Repairing Low-Quality Video Enhancement Techniques Based on Trained Filter
Venue: arXiv cs.CV 2011
Year: 2011

Multifarious image enhancement algorithms have been used in different applications. Still, some algorithms or modules are imperfect for practical use. When the image enhancement modules have been fixed or combined by a series of algorithms, we need to repair them as a whole part without changing the inside. This report aims to find an algorithm based on trained filters to repair low-quality image enhancement modules. A brief review on basic image enhancement techniques and pixel classification methods will be presented, and the procedure of trained filters will be described step by step. The experiments and result comparisons for this algorithm will be described in detail.
A Wiki for Business Rules in Open Vocabulary, Executable English
Venue: arXiv cs.AI 2011
Year: 2011

The problem of business-IT alignment is of widespread economic concern. As one way of addressing the problem, this paper describes an online system that functions as a kind of Wiki -- one that supports the collaborative writing and running of business and scientific applications, as rules in open vocabulary, executable English, using a browser. Since the rules are in English, they are indexed by Google and other search engines. This is useful when looking for rules for a task that one has in mind. The design of the system integrates the semantics of data, with a semantics of an inference method, and also with the meanings of English sentences. As such, the system has functionality that may be useful for the Rules, Logic, Proof and Trust requirements of the Semantic Web. The system accepts rules, and small numbers of facts, typed or copy-pasted directly into a browser. One can then run the rules, again using a browser. For larger amounts of data, the system uses information in the rules to automatically generate and run SQL over networked databases. From a few highly declarative rules, the system typically generates SQL that would be too complicated to write reliably by hand. However, the system can explain its results in step-by-step hypertexted English, at the business or scientific level As befits a Wiki, shared use of the system is free.
A Medial Axis Based Thinning Strategy for Character Images
Venue: arXiv cs.CV 2011
Year: 2011

Thinning of character images is a big challenge. Removal of strokes or deformities in thinning is a difficult problem. In this paper, we have proposed a medial axis based thinning strategy used for performing skeletonization of printed and handwritten character images. In this method, we have used shape characteristics of text to get skeleton of nearly same as the true character shape. This approach helps to preserve the local features and true shape of the character images. The proposed algorithm produces one pixel width thin skeleton. As a by-product of our thinning approach, the skeleton also gets segmented into strokes in vector form. Hence further stroke segmentation is not required. Experiment is done on printed English and Bengali characters and we obtain less spurious branches comparing with other thinning methods without any post processing.
Synthesizing Switching Logic to Minimize Long-Run Cost
Venue: arXiv cs.SY 2011
Year: 2011

Given a multi-modal dynamical system, optimal switching logic synthesis involves generating the conditions for switching between the system modes such that the resulting hybrid system satisfies a quantitative specification. We formalize and solve the problem of optimal switching logic synthesis for quantitative specifications over long run behavior. Each trajectory of the system, and each state of the system, is associated with a cost. Our goal is to synthesize a system that minimizes this cost from each initial state. Our paper generalizes earlier work on synthesis for safety as safety specifications can be encoded as quantitative specifications. We present an approach for specifying quantitative measures using reward and penalty functions, and illustrate its effectiveness using several examples. We present an automated technique to synthesize switching logic for such quantitative measures. Our algorithm is based on reducing the synthesis problem to an unconstrained numerical optimization problem which can be solved by any off-the-shelf numerical optimization engines. We demonstrate the effectiveness of this approach with experimental results.