OpenRaiser/Intern-Atlas huggingface dataset:
Soft-Decision-Driven Channel Estimation for Pipelined Turbo Receivers
Venue: arXiv cs.IT 2011
Year: 2011

We consider channel estimation specific to turbo equalization for multiple-input multiple-output (MIMO) wireless communication. We develop a soft-decision-driven sequential algorithm geared to the pipelined turbo equalizer architecture operating on orthogonal frequency division multiplexing (OFDM) symbols. One interesting feature of the pipelined turbo equalizer is that multiple soft-decisions become available at various processing stages. A tricky issue is that these multiple decisions from different pipeline stages have varying levels of reliability. This paper establishes an effective strategy for the channel estimator to track the target channel, while dealing with observation sets with different qualities. The resulting algorithm is basically a linear sequential estimation algorithm and, as such, is Kalman-based in nature. The main difference here, however, is that the proposed algorithm employs puncturing on observation samples to effectively deal with the inherent correlation among the multiple demapper/decoder module outputs that cannot easily be removed by the traditional innovations approach. The proposed algorithm continuously monitors the quality of the feedback decisions and incorporates it in the channel estimation process. The proposed channel estimation scheme shows clear performance advantages relative to existing channel estimation techniques.
Enabling Multi-level Trust in Privacy Preserving Data Mining
Venue: arXiv cs.DB 2011
Year: 2011

Privacy Preserving Data Mining (PPDM) addresses the problem of developing accurate models about aggregated data without access to precise information in individual data record. A widely studied \emph{perturbation-based PPDM} approach introduces random perturbation to individual values to preserve privacy before data is published. Previous solutions of this approach are limited in their tacit assumption of single-level trust on data miners. In this work, we relax this assumption and expand the scope of perturbation-based PPDM to Multi-Level Trust (MLT-PPDM). In our setting, the more trusted a data miner is, the less perturbed copy of the data it can access. Under this setting, a malicious data miner may have access to differently perturbed copies of the same data through various means, and may combine these diverse copies to jointly infer additional information about the original data that the data owner does not intend to release. Preventing such \emph{diversity attacks} is the key challenge of providing MLT-PPDM services. We address this challenge by properly correlating perturbation across copies at different trust levels. We prove that our solution is robust against diversity attacks with respect to our privacy goal. That is, for data miners who have access to an arbitrary collection of the perturbed copies, our solution prevent them from jointly reconstructing the original data more accurately than the best effort using any individual copy in the collection. Our solution allows a data owner to generate perturbed copies of its data for arbitrary trust levels on-demand. This feature offers data owners maximum flexibility.
Kinetic Stable Delaunay Graphs
Venue: arXiv cs.CG 2011
Year: 2011

We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set $P$ of $n$ moving points in the plane, along algebraic trajectories of constant description complexity. Since the best known upper bound on the number of topological changes in the full $\DT$ is nearly cubic, we seek to maintain a suitable portion of it that is less volatile yet retains many useful properties. We introduce the notion of a stable Delaunay graph, which is a dynamic subgraph of the Delaunay triangulation. The stable Delaunay graph (a) is easy to define, (b) experiences only a nearly quadratic number of discrete changes, (c) is robust under small changes of the norm, and (d) possesses certain useful properties. The stable Delaunay graph ($\SDG$ in short) is defined in terms of a parameter $α>0$, and consists of Delaunay edges $pq$ for which the angles at which $p$ and $q$ see their Voronoi edge $e_{pq}$ are at least $α$. We show that (i) $\SDG$ always contains at least roughly one third of the Delaunay edges; (ii) it contains the $β$-skeleton of $P$, for $β=1+Ω(α^2)$; (iii) it is stable, in the sense that its edges survive for long periods of time, as long as the orientations of the segments connecting (nearby) points of $P$ do not change by much; and (iv) stable Delaunay edges remain stable (with an appropriate redefinition of stability) if we replace the Euclidean norm by any sufficiently close norm. In particular, we can approximate the Euclidean norm by a polygonal norm (namely, a regular $k$-gon, with $k=Θ(1/α)$), and keep track of a Euclidean $\SDG$ by maintaining the full Delaunay triangulation of $P$ under the polygonal norm. We describe two kinetic data structures for maintaining $\SDG$. Both structures use $O^*(n)$ storage and process $O^*(n^2)$ events during the motion, each in $O^*(1)$ time.
Automated code generation for discontinuous Galerkin methods
Venue: arXiv cs.MS 2011
Year: 2011

A compiler approach for generating low-level computer code from high-level input for discontinuous Galerkin finite element forms is presented. The input language mirrors conventional mathematical notation, and the compiler generates efficient code in a standard programming language. This facilitates the rapid generation of efficient code for general equations in varying spatial dimensions. Key concepts underlying the compiler approach and the automated generation of computer code are elaborated. The approach is demonstrated for a range of common problems, including the Poisson, biharmonic, advection--diffusion and Stokes equations.
Potent Tree Codes and their applications: Coding for Interactive Communication, revisited
Venue: arXiv cs.DS 2011
Year: 2011

We study the fundamental problem of reliable interactive communication over a noisy channel. In a breakthrough sequence of papers published in 1992 and 1993, Schulman gave non-constructive proofs of the existence of general methods to emulate any two-party interactive protocol such that: (1) the emulation protocol takes a constant-factor longer than the original protocol, and (2) if the emulation protocol is executed over a noisy channel, then the probability that the emulation protocol fails is exponentially small in the total length of the protocol. Unfortunately, Schulman's emulation procedures either only work in a model with a large amount of shared randomness, or are non-constructive in that they rely on the existence of good tree codes. The only known proofs of the existence of good tree codes are non-constructive, and finding an explicit construction remains an important open problem. Indeed, randomly generated tree codes are not good tree codes with overwhelming probability. In this work, we revisit the problem of reliable interactive communication, and obtain the following results: We introduce a new notion of goodness for a tree code, and define the notion of a potent tree code. We believe that this notion is of independent interest. We prove the correctness of an explicit emulation procedure based on any potent tree code. We show that a randomly generated tree code (with suitable constant alphabet size) is a potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result using only O(n) random bits, where $n$ is the depth of the tree. These results allow us to obtain the first fully explicit emulation procedure for reliable interactive communication over noisy channels with a constant communication overhead, and exponentially small failure probability.
Evolving Pacing Strategies for Team Pursuit Track Cycling
Venue: arXiv cs.NE 2011
Year: 2011

Team pursuit track cycling is a bicycle racing sport held on velodromes and is part of the Summer Olympics. It involves the use of strategies to minimize the overall time that a team of cyclists needs to complete a race. We present an optimisation framework for team pursuit track cycling and show how to evolve strategies using metaheuristics for this interesting real-world problem. Our experimental results show that these heuristics lead to significantly better strategies than state-of-art strategies that are currently used by teams of cyclists.
Performance evaluation of FD-SOI Mosfets for different metal gate work function
Venue: arXiv cs.OH 2011
Year: 2011

Fully depleted (FD) Silicon on Insulator (SOI) metal oxide Field Effect Transistor (MOSFET) Is the Leading Contender for Sun 65nm Regime. This paper presents a study of effects of work functions of metal gate on the performance of FD-SOI MOSFET. Sentaurus TCAD simulation tool is used to investigate the effect of work function of gates ont he performance FDSOI MOSFET. Specific channel length of the device that had been concentrated is 25nm. From simulation we observed that by changing the work function of the metal gates of FD-SOI MOSFET we can change the threshold voltage. Hence by using this technique we can set the appropriate threshold voltage of FD-SOI MOSFET at same voltage and we can decrease the leakage current, gate tunneling current and short channel effects and increase drive current.
Phase Transitions in Knowledge Compilation: an Experimental Study
Venue: arXiv cs.AI 2011
Year: 2011

Phase transitions in many complex combinational problems have been widely studied in the past decade. In this paper, we investigate phase transitions in the knowledge compilation empirically, where DFA, OBDD and d-DNNF are chosen as the target languages to compile random k-SAT instances. We perform intensive experiments to analyze the sizes of compilation results and draw the following conclusions: there exists an easy-hard-easy pattern in compilations; the peak point of sizes in the pattern is only related to the ratio of the number of clauses to that of variables when k is fixed, regardless of target languages; most sizes of compilation results increase exponentially with the number of variables growing, but there also exists a phase transition that separates a polynomial-increment region from the exponential-increment region; Moreover, we explain why the phase transition in compilations occurs by analyzing microstructures of DFAs, and conclude that a kind of solution interchangeability with more than 2 variables has a sharp transition near the peak point of the easy-hard-easy pattern, and thus it has a great impact on sizes of DFAs.
Applications of Tauberian Theorem for High-SNR Analysis of Performance over Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper derives high-SNR asymptotic average error rates over fading channels by relating them to the outage probability, under mild assumptions. The analysis is based on the Tauberian theorem for Laplace-Stieltjes transforms which is grounded on the notion of regular variation, and applies to a wider range of channel distributions than existing approaches. The theory of regular variation is argued to be the proper mathematical framework for finding sufficient and necessary conditions for outage events to dominate high-SNR error rate performance. It is proved that the diversity order being $d$ and the cumulative distribution function (CDF) of the channel power gain having variation exponent $d$ at 0 imply each other, provided that the instantaneous error rate is upper-bounded by an exponential function of the instantaneous SNR. High-SNR asymptotic average error rates are derived for specific instantaneous error rates. Compared to existing approaches in the literature, the asymptotic expressions are related to the channel distribution in a much simpler manner herein, and related with outage more intuitively. The high-SNR asymptotic error rate is also characterized under diversity combining schemes with the channel power gain of each branch having a regularly varying CDF. Numerical results are shown to corroborate our theoretical analysis.
ReveR: Software Simulator of Reversible Processor with Stack
Venue: arXiv cs.ET 2011
Year: 2011

A software model of a reversible processor ReveR with the stack is discussed in this paper. An architecture, the minimal set of elementary reversible operations together with an implementation of the basic control flow structures and procedures calls using simple assembler language are described.
QEMPAR: QoS and Energy Aware Multi-Path Routing Algorithm for Real-Time Applications in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Enabling real time applications in wireless sensor networks requires certain delay and bandwidth which pose more challenges in the design of routing protocols. The algorithm that is used for packet routing in such applications should be able to establish a tradeoff between end to end delay parameter and energy consumption. In this paper, we propose a new multi path routing algorithm for real time applications in wireless sensor networks namely QEMPAR which is QoS aware and can increase the network lifetime. Simulation results show that the proposed algorithm is more efficient than previous algorithms in providing quality of service requirements of real-time applications.
Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average
Venue: arXiv cs.DS 2011
Year: 2011

In the parameterized problem \textsc{MaxLin2-AA}[$k$], we are given a system with variables $x_1,...,x_n$ consisting of equations of the form $\prod_{i \in I}x_i = b$, where $x_i,b \in \{-1, 1\}$ and $I\subseteq [n],$ each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least $W/2+k$, where $W$ is the total weight of all equations and $k$ is the parameter (if $k=0$, the possibility is assured). We show that \textsc{MaxLin2-AA}[$k$] has a kernel with at most $O(k^2\log k)$ variables and can be solved in time $2^{O(k\log k)}(nm)^{O(1)}$. This solves an open problem of Mahajan et al. (2006). The problem \textsc{Max-$r$-Lin2-AA}[$k,r$] is the same as \textsc{MaxLin2-AA}[$k$] with two differences: each equation has at most $r$ variables and $r$ is the second parameter. We prove a theorem on \textsc{Max-$r$-Lin2-AA}[$k,r$] which implies that \textsc{Max-$r$-Lin2-AA}[$k,r$] has a kernel with at most $(2k-1)r$ variables improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function $f:\ \{-1,1\}^n \rightarrow \mathbb{R}$ of degree $r$. We show applicability of the lower bound by giving a new proof of the Edwards-Erd{\H o}s bound (each connected graph on $n$ vertices and $m$ edges has a bipartite subgraph with at least $m/2 + (n-1)/4$ edges) and obtaining a generalization.
Modulation Diversity in Fading Channels with Quantized Receiver
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we address the design of codes which achieve modulation diversity in block fading single-input single-output (SISO) channels with signal quantization at receiver and low-complexity decoding. With an unquantized receiver, coding based on algebraic rotations is known to achieve modulation coding diversity. On the other hand, with a quantized receiver, algebraic rotations may not guarantee diversity. Through analysis, we propose specific rotations which result in the codewords having equidistant component-wise projections. We show that the proposed coding scheme achieves maximum modulation diversity with a low-complexity minimum distance decoder and perfect channel knowledge. Relaxing the perfect channel knowledge assumption we propose a novel training/estimation and receiver control technique to estimate the channel. We show that our coding/training/estimation scheme and minimum distance decoding achieve an error probability performance similar to that achieved with perfect channel knowledge.
M-AODV : AODV variant to improve quality of service in MANETs
Venue: arXiv cs.NI 2011
Year: 2011

Nowadays, multimedia and real-time applications consume much network resources and so, need high flow rates and very small transfer delay. The current ad hoc networks (MANETs), in their original state, are not able to satisfy the requirements of quality of service (QoS). Researches for improving QoS in these networks are main topics and a subject of intensive researches. In Adhoc networks, the routing phase plays an important role for improving QoS. Numerous routing protocols (proactive, reactive and hybrid) were proposed. AODV (Adhoc On demand Distance Vector) is probably the more treated in literature In this article, we propose a new variant based on the AODV which gives better results than the original AODV protocol with respect of a set of QoS parameters and under different constraints, taking into account the limited resources of mobile environments (bandwidth, energy, etc...). The proposed variant (M-AODV) suggests that the discovering operation for paths reconstruction should be done from the source. It also defines a new mechanism for determining multiple disjoint (separated) routes. To validate our solution, simulations were made under Network Simulator (NS2). We measure traffic control and packet loss rate under diverse constraints (mobility, energy and scale).
A novel approach for determining fatigue resistances of different muscle groups in static cases
Venue: arXiv cs.RO 2011
Year: 2011

In ergonomics and biomechanics, muscle fatigue models based on maximum endurance time (MET) models are often used to integrate fatigue effect into ergonomic and biomechanical application. However, due to the empirical principle of those MET models, the disadvantages of this method are: 1) the MET models cannot reveal the muscle physiology background very well; 2) there is no general formation for those MET models to predict MET. In this paper, a theoretical MET model is extended from a simple muscle fatigue model with consideration of the external load and maximum voluntary contraction in passive static exertion cases. The universal availability of the extended MET model is analyzed in comparison to 24 existing empirical MET models. Using mathematical regression method, 21 of the 24 MET models have intraclass correlations over 0.9, which means the extended MET model could replace the existing MET models in a general and computationally efficient way. In addition, an important parameter, fatigability (or fatigue resistance) of different muscle groups, could be calculated via the mathematical regression approach. Its mean value and its standard deviation are useful for predicting MET values of a given population during static operations. The possible reasons influencing the fatigue resistance were classified and discussed, and it is still a very challenging work to find out the quantitative relationship between the fatigue resistance and the influencing factors.
A Small PRG for Polynomial Threshold Functions of Gaussians
Venue: arXiv cs.CC 2011
Year: 2011

We develop a pseudo-random generator to fool degree-$d$ polynomial threshold functions with respect to the Gaussian distribution. For $c>0$ any constant, we construct a pseudo-random generator that fools such functions to within $ε$ and has seed length $\log(n) 2^{O(d)} ε^{-4-c}$.
Explosive Percolation in Erdös-Rényi-Like Random Graph Processes
Venue: arXiv cs.DM 2011
Year: 2011

The evolution of the largest component has been studied intensely in a variety of random graph processes, starting in 1960 with the Erdös-Rényi process. It is well known that this process undergoes a phase transition at n/2 edges when, asymptotically almost surely, a linear-sized component appears. Moreover, this phase transition is continuous, i.e., in the limit the function f(c) denoting the fraction of vertices in the largest component in the process after cn edge insertions is continuous. A variation of the Erdös-Rényi process are the so-called Achlioptas processes in which in every step a random pair of edges is drawn, and a fixed edge-selection rule selects one of them to be included in the graph while the other is put back. Recently, Achlioptas, D'Souza and Spencer (2009) gave strong numerical evidence that a variety of edge-selection rules exhibit a discontinuous phase transition. However, Riordan and Warnke (2011) very recently showed that all Achlioptas processes have a continuous phase transition. In this work we prove discontinuous phase transitions for a class of Erdös-Rényi-like processes in which in every step we connect two vertices, one chosen randomly from all vertices, and one chosen randomly from a restricted set of vertices.
Optimal Polygonal Representation of Planar Graphs
Venue: arXiv cs.CG 2011
Year: 2011

In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)xO(n) grid.
Coded Modulation for Power Line Communications
Venue: arXiv cs.IT 2011
Year: 2011

We discuss the application of coded modulation for power-line communications. We combine M-ary FSK with diversity and coding to make the transmission robust against permanent frequency disturbances and impulse noise. We give a particular example of the coding/modulation scheme that is in agreement with the existing CENELEC norms. The scheme can be considered as a form of coded Frequency Hopping and is thus extendable to any frequency range.
A bio-inspired image coder with temporal scalability
Venue: arXiv cs.CV 2011
Year: 2011

We present a novel bio-inspired and dynamic coding scheme for static images. Our coder aims at reproducing the main steps of the visual stimulus processing in the mammalian retina taking into account its time behavior. The main novelty of this work is to show how to exploit the time behavior of the retina cells to ensure, in a simple way, scalability and bit allocation. To do so, our main source of inspiration will be the biologically plausible retina model called Virtual Retina. Following a similar structure, our model has two stages. The first stage is an image transform which is performed by the outer layers in the retina. Here it is modelled by filtering the image with a bank of difference of Gaussians with time-delays. The second stage is a time-dependent analog-to-digital conversion which is performed by the inner layers in the retina. Thanks to its conception, our coder enables scalability and bit allocation across time. Also, our decoded images do not show annoying artefacts such as ringing and block effects. As a whole, this article shows how to capture the main properties of a biological system, here the retina, in order to design a new efficient coder.
Computing generalized inverses using LU factorization of matrix product
Venue: arXiv cs.SC 2011
Year: 2011

An algorithm for computing {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4} -inverses and the Moore-Penrose inverse of a given rational matrix A is established. Classes A(2, 3)s and A(2, 4)s are characterized in terms of matrix products (R*A)+R* and T*(AT*)+, where R and T are rational matrices with appropriate dimensions and corresponding rank. The proposed algorithm is based on these general representations and the Cholesky factorization of symmetric positive matrices. The algorithm is implemented in programming languages MATHEMATICA and DELPHI, and illustrated via examples. Numerical results of the algorithm, corresponding to the Moore-Penrose inverse, are compared with corresponding results obtained by several known methods for computing the Moore-Penrose inverse.