OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Dynamic Resource Allocation for Multi-Antenna Broadcasting with Heterogeneous Delay-Constrained Traffic
Venue: arXiv cs.IT 2008
Year: 2008

This paper is concerned with dynamic resource allocation in a cellular wireless network with slow fading for support of data traffic having heterogeneous transmission delay requirements. The multiple-input single-output (MISO) fading broadcast channel (BC) is of interest where the base station (BS) employs multiple transmit antennas to realize simultaneous downlink transmission at the same frequency to multiple mobile users each having a single receive antenna. An information-theoretic approach is taken for characterizing capacity limits of the fading MISO-BC under various transmission delay considerations. First, this paper studies transmit optimization at the BS when some users have delay-tolerant ``packet'' data and the others have delay-sensitive ``circuit'' data for transmission at the same time. Based on the convex optimization framework, an online resource allocation algorithm is derived that is amenable to efficient cross-layer implementation of both physical (PHY) -layer multi-antenna transmission and media-access-control (MAC) -layer multiuser rate scheduling. Secondly, this paper investigates the fundamental throughput-delay tradeoff for transmission over the fading MISO-BC. By comparing the network throughput under completely relaxed versus strictly zero transmission delay constraint, this paper characterizes the limiting loss in sum capacity due to the vanishing delay tolerance, termed the delay penalty, under some prescribed user fairness for transmit rate allocation.
Combining Beamforming and Space-Time Coding Using Noisy Quantized Feedback
Venue: arXiv cs.IT 2008
Year: 2008

The goal of combining beamforming and space-time coding in this work is to obtain full-diversity order and to provide additional received power (array gain) compared to conventional space-time codes. In our system, we consider a quasi-static fading environment and we incorporate both high-rate and low-rate feedback channels with possible feedback errors. To utilize feedback information, a class of code constellations is proposed, inspired from orthogonal designs and precoded space-time block codes, which is called generalized partly orthogonal designs or generalized PODs. Furthermore, to model feedback errors, we assume that the feedback bits go through binary symmetric channels (BSCs). Two cases are studied: first, when the BSC bit error probability is known a priori to the transmission ends and second, when it is not known exactly. In the first case, we derive a minimum pairwise error probability (PEP) design criterion for generalized PODs. Then we design the quantizer for the erroneous feedback channel and the precoder codebook of PODs based on this criterion. The quantization scheme in our system is a channel optimized vector quantizer (COVQ). In the second case, the design of the quantizer and the precoder codebook is based on similar approaches, however with a worst-case design strategy. The attractive property of our combining scheme is that it converges to conventional space-time coding with low-rate and erroneous feedback and to directional beamforming with high-rate and error-free feedback. This scheme shows desirable robustness against feedback channel modeling mismatch.
Constructions for Clumps Statistics
Venue: arXiv cs.DM 2008
Year: 2008

We consider a component of the word statistics known as clump; starting from a finite set of words, clumps are maximal overlapping sets of these occurrences. This parameter has first been studied by Schbath with the aim of counting the number of occurrences of words in random texts. Later work with similar probabilistic approach used the Chen-Stein approximation for a compound Poisson distribution, where the number of clumps follows a law close to Poisson. Presently there is no combinatorial counterpart to this approach, and we fill the gap here. We emphasize the fact that, in contrast with the probabilistic approach which only provides asymptotic results, the combinatorial approach provides exact results that are useful when considering short sequences.
Word-Based Text Compression
Venue: arXiv cs.IT 2008
Year: 2008

Today there are many universal compression algorithms, but in most cases is for specific data better using specific algorithm - JPEG for images, MPEG for movies, etc. For textual documents there are special methods based on PPM algorithm or methods with non-character access, e.g. word-based compression. In the past, several papers describing variants of word-based compression using Huffman encoding or LZW method were published. The subject of this paper is the description of a word-based compression variant based on the LZ77 algorithm. The LZ77 algorithm and its modifications are described in this paper. Moreover, various ways of sliding window implementation and various possibilities of output encoding are described, as well. This paper also includes the implementation of an experimental application, testing of its efficiency and finding the best combination of all parts of the LZ77 coder. This is done to achieve the best compression ratio. In conclusion there is comparison of this implemented application with other word-based compression programs and with other commonly used compression programs.
On the metric distortion of nearest-neighbour graphs on random point sets
Venue: arXiv cs.NI 2008
Year: 2008

We study the graph constructed on a Poisson point process in $d$ dimensions by connecting each point to the $k$ points nearest to it. This graph a.s. has an infinite cluster if $k > k_c(d)$ where $k_c(d)$, known as the critical value, depends only on the dimension $d$. This paper presents an improved upper bound of 188 on the value of $k_c(2)$. We also show that if $k \geq 188$ the infinite cluster of $\NN(2,k)$ has an infinite subset of points with the property that the distance along the edges of the graphs between these points is at most a constant multiplicative factor larger than their Euclidean distance. Finally we discuss in detail the relevance of our results to the study of multi-hop wireless sensor networks.
Multiple Random Oracles Are Better Than One
Venue: arXiv cs.LG 2008
Year: 2008

We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f : {-1,1}^n -> {-1,1} that depends on k (unknown) coordinates. While the best known algorithms for the general problem of learning a k-junta require running time of n^k * poly(n,2^k), we show that given access to k different product distributions with biases separated by γ>0, the functions may be learned in time poly(n,2^k,γ^{-k}). More generally, given access to t <= k different product distributions, the functions may be learned in time n^{k/t} * poly(n,2^k,γ^{-k}). Our techniques involve novel results in Fourier analysis relating Fourier expansions with respect to different biases and a generalization of Russo's formula.
Reasoning in Abella about Structural Operational Semantics Specifications
Venue: arXiv cs.LO 2008
Year: 2008

The approach to reasoning about structural operational semantics style specifications supported by the Abella system is discussed. This approach uses lambda tree syntax to treat object language binding and encodes binding related properties in generic judgments. Further, object language specifications are embedded directly into the reasoning framework through recursive definitions. The treatment of binding via generic judgments implicitly enforces distinctness and atomicity in the names used for bound variables. These properties must, however, be made explicit in reasoning tasks. This objective can be achieved by allowing recursive definitions to also specify generic properties of atomic predicates. The utility of these various logical features in the Abella system is demonstrated through actual reasoning tasks. Brief comparisons with a few other logic based approaches are also made.
Logic Mining Using Neural Networks
Venue: arXiv cs.LO 2008
Year: 2008

Knowledge could be gained from experts, specialists in the area of interest, or it can be gained by induction from sets of data. Automatic induction of knowledge from data sets, usually stored in large databases, is called data mining. Data mining methods are important in the management of complex systems. There are many technologies available to data mining practitioners, including Artificial Neural Networks, Regression, and Decision Trees. Neural networks have been successfully applied in wide range of supervised and unsupervised learning applications. Neural network methods are not commonly used for data mining tasks, because they often produce incomprehensible models, and require long training times. One way in which the collective properties of a neural network may be used to implement a computational task is by way of the concept of energy minimization. The Hopfield network is well-known example of such an approach. The Hopfield network is useful as content addressable memory or an analog computer for solving combinatorial-type optimization problems. Wan Abdullah [1] proposed a method of doing logic programming on a Hopfield neural network. Optimization of logical inconsistency is carried out by the network after the connection strengths are defined from the logic program; the network relaxes to neural states corresponding to a valid interpretation. In this article, we describe how Hopfield network is able to induce logical rules from large database by using reverse analysis method: given the values of the connections of a network, we can hope to know what logical rules are entrenched in the database.
Expected Message Delivery Time for Small-world Networks in the Continuum Limit
Venue: arXiv cs.IT 2008
Year: 2008

Small-world networks are networks in which the graphical diameter of the network is as small as the diameter of random graphs but whose nodes are highly clustered when compared with the ones in a random graph. Examples of small-world networks abound in sociology, biology, neuroscience and physics as well as in human-made networks. This paper analyzes the average delivery time of messages in dense small-world networks constructed on a plane. Iterative equations for the average message delivery time in these networks are provided for the situation in which nodes employ a simple greedy geographic routing algorithm. It is shown that two network nodes communicate with each other only through their short-range contacts, and that the average message delivery time rises linearly if the separation between them is small. On the other hand, if their separation increases, the average message delivery time rapidly saturates to a constant value and stays almost the same for all large values of their separation.
Counterflow Extension for the F.A.S.T.-Model
Venue: arXiv cs.MA 2008
Year: 2008

The F.A.S.T. (Floor field and Agent based Simulation Tool) model is a microscopic model of pedestrian dynamics, which is discrete in space and time. It was developed in a number of more or less consecutive steps from a simple CA model. This contribution is a summary of a study on an extension of the F.A.S.T-model for counterflow situations. The extensions will be explained and it will be shown that the extended F.A.S.T.-model is capable of handling various counterflow situations and to reproduce the well known lane formation effect.
Development of a peristaltic micropump for bio-medical applications based on mini LIPCA
Venue: arXiv cs.RO 2008
Year: 2008

This paper presents the design, fabrication, and experimental characterization of a peristaltic micropump. The micropump is composed of two layers fabricated from polydimethylsiloxane (PDMS) material. The first layer has a rectangular channel and two valve seals. Three rectangular mini lightweight piezo-composite actuators are integrated in the second layer, and used as actuation parts. Two layers are bonded, and covered by two polymethyl methacrylate (PMMA) plates, which help increase the stiffness of the micropump. A maximum flow rate of 900 mokroliter per min and a maximum backpressure of 1.8 kPa are recorded when water is used as pump liquid. We measured the power consumption of the micropump. The micropump is found to be a promising candidate for bio-medical application due to its bio-compatibility, portability, bidirectionality, and simple effective design.
A multivariate generalization of Costa's entropy power inequality
Venue: arXiv cs.IT 2008
Year: 2008

A simple multivariate version of Costa's entropy power inequality is proved. In particular, it is shown that if independent white Gaussian noise is added to an arbitrary multivariate signal, the entropy power of the resulting random variable is a multidimensional concave function of the individual variances of the components of the signal. As a side result, we also give an expression for the Hessian matrix of the entropy and entropy power functions with respect to the variances of the signal components, which is an interesting result in its own right.
Characterizing Video Responses in Social Networks
Venue: arXiv cs.MM 2008
Year: 2008

Video sharing sites, such as YouTube, use video responses to enhance the social interactions among their users. The video response feature allows users to interact and converse through video, by creating a video sequence that begins with an opening video and followed by video responses from other users. Our characterization is over 3.4 million videos and 400,000 video responses collected from YouTube during a 7-day period. We first analyze the characteristics of the video responses, such as popularity, duration, and geography. We then examine the social networks that emerge from the video response interactions.
Universe Detectors for Sybil Defense in Ad Hoc Wireless Networks
Venue: arXiv cs.DC 2008
Year: 2008

The Sybil attack in unknown port networks such as wireless is not considered tractable. A wireless node is not capable of independently differentiating the universe of real nodes from the universe of arbitrary non-existent fictitious nodes created by the attacker. Similar to failure detectors, we propose to use universe detectors to help nodes determine which universe is real. In this paper, we (i) define several variants of the neighborhood discovery problem under Sybil attack (ii) propose a set of matching universe detectors (iii) demonstrate the necessity of additional topological constraints for the problems to be solvable: node density and communication range; (iv) present SAND -- an algorithm that solves these problems with the help of appropriate universe detectors, this solution demonstrates that the proposed universe detectors are the weakest detectors possible for each problem.
Cellular Systems with Full-Duplex Compress-and-Forward Relaying and Cooperative Base Stations
Venue: arXiv cs.IT 2008
Year: 2008

In this paper the advantages provided by multicell processing of signals transmitted by mobile terminals (MTs) which are received via dedicated relay terminals (RTs) are studied. It is assumed that each RT is capable of full-duplex operation and receives the transmission of adjacent relay terminals. Focusing on intra-cell TDMA and non-fading channels, a simplified relay-aided uplink cellular model based on a model introduced by Wyner is considered. Assuming a nomadic application in which the RTs are oblivious to the MTs' codebooks, a form of distributed compress-and-forward (CF) scheme with decoder side information is employed. The per-cell sum-rate of the CF scheme is derived and is given as a solution of a simple fixed point equation. This achievable rate reveals that the CF scheme is able to completely eliminate the inter-relay interference, and it approaches a ``cut-set-like'' upper bound for strong RTs transmission power. The CF rate is also shown to surpass the rate of an amplify-and-forward scheme via numerical calculations for a wide range of the system parameters.
On Recovery of Sparse Signals via $\ell_1$ Minimization
Venue: arXiv cs.LG 2008
Year: 2008

This article considers constrained $\ell_1$ minimization methods for the recovery of high dimensional sparse signals in three settings: noiseless, bounded error and Gaussian noise. A unified and elementary treatment is given in these noise settings for two $\ell_1$ minimization methods: the Dantzig selector and $\ell_1$ minimization with an $\ell_2$ constraint. The results of this paper improve the existing results in the literature by weakening the conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. This paper also establishes connections between restricted isometry property and the mutual incoherence property. Some results of Candes, Romberg and Tao (2006) and Donoho, Elad, and Temlyakov (2006) are extended.
Information, Energy and Density for Ad Hoc Sensor Networks over Correlated Random Fields: Large Deviations Analysis
Venue: arXiv cs.IT 2008
Year: 2008

Using large deviations results that characterize the amount of information per node on a two-dimensional (2-D) lattice, asymptotic behavior of a sensor network deployed over a correlated random field for statistical inference is investigated. Under a 2-D hidden Gauss-Markov random field model with symmetric first order conditional autoregression, the behavior of the total information [nats] and energy efficiency [nats/J] defined as the ratio of total gathered information to the required energy is obtained as the coverage area, node density and energy vary.
Specification of an extensible and portable file format for electronic structure and crystallographic data
Venue: arXiv cs.DL 2008
Year: 2008

In order to allow different software applications, in constant evolution, to interact and exchange data, flexible file formats are needed. A file format specification for different types of content has been elaborated to allow communication of data for the software developed within the European Network of Excellence "NANOQUANTA", focusing on first-principles calculations of materials and nanosystems. It might be used by other software as well, and is described here in detail. The format relies on the NetCDF binary input/output library, already used in many different scientific communities, that provides flexibility as well as portability accross languages and platforms. Thanks to NetCDF, the content can be accessed by keywords, ensuring the file format is extensible and backward compatible.
Towards Exploring Fundamental Limits of System-Specific Cryptanalysis Within Limited Attack Classes: Application to ABSG
Venue: arXiv cs.CR 2008
Year: 2008

A new approach on cryptanalysis is proposed where the goal is to explore the fundamental limits of a specific class of attacks against a particular cryptosystem. As a first step, the approach is applied on ABSG, which is an LFSR-based stream cipher where irregular decimation techniques are utilized. Consequently, under some mild assumptions, which are common in cryptanalysis, the tight lower bounds on the algorithmic complexity of successful Query-Based Key-Recovery attacks are derived for two different setups of practical interest. The proofs rely on the concept of ``typicality'' of information theory.
On Expanded Cyclic Codes
Venue: arXiv cs.IT 2008
Year: 2008

The paper has a threefold purpose. The first purpose is to present an explicit description of expanded cyclic codes defined in $\GF(q^m)$. The proposed explicit construction of expanded generator matrix and expanded parity check matrix maintains the symbol-wise algebraic structure and thus keeps many important original characteristics. The second purpose of this paper is to identify a class of constant-weight cyclic codes. Specifically, we show that a well-known class of $q$-ary BCH codes excluding the all-zero codeword are constant-weight cyclic codes. Moreover, we show this class of codes achieve the Plotkin bound. The last purpose of the paper is to characterize expanded cyclic codes utilizing the proposed expanded generator matrix and parity check matrix. We characterize the properties of component codewords of a codeword and particularly identify the precise conditions under which a codeword can be represented by a subbasis. Our developments reveal an alternative while more general view on the subspace subcodes of Reed-Solomon codes. With the new insights, we present an improved lower bound on the minimum distance of an expanded cyclic code by exploiting the generalized concatenated structure. We also show that the fixed-rate binary expanded Reed-Solomon codes are asymptotically "bad", in the sense that the ratio of minimum distance over code length diminishes with code length going to infinity. It overturns the prevalent conjecture that they are "good" codes and deviates from the ensemble of generalized Reed-Solomon codes which asymptotically achieves the Gilbert-Varshamov bound.
Relational Parametricity and Separation Logic
Venue: arXiv cs.LO 2008
Year: 2008

Separation logic is a recent extension of Hoare logic for reasoning about programs with references to shared mutable data structures. In this paper, we provide a new interpretation of the logic for a programming language with higher types. Our interpretation is based on Reynolds's relational parametricity, and it provides a formal connection between separation logic and data abstraction.
Design And Fabrication of Condenser Microphone Using Wafer Transfer And Micro-electroplating Technique
Venue: arXiv cs.OH 2008
Year: 2008

A novel fabrication process, which uses wafer transfer and micro-electroplating technique, has been proposed and tested. In this paper, the effects of the diaphragm thickness and stress, the air-gap thickness, and the area ratio of acoustic holes to backplate on the sensitivity of the condenser microphone have been demonstrated since the performance of the microphone depends on these parameters. The microphone diaphragm has been designed with a diameter and thickness of 1.9 mm and 0.6 $μ$m, respectively, an air-gap thickness of 10 $μ$m, and a 24% area ratio of acoustic holes to backplate. To obtain a lower initial stress, the material used for the diaphragm is polyimide. The measured sensitivities of the microphone at the bias voltages of 24 V and 12 V are -45.3 and -50.2 dB/Pa (at 1 kHz), respectively. The fabricated microphone shows a flat frequency response extending to 20 kHz.
Integrated RF MEMS/CMOS Devices
Venue: arXiv cs.OH 2008
Year: 2008

A maskless post-processing technique for CMOS chips is developed that enables the fabrication of RF MEMS parallel-plate capacitors with a high quality factor and a very compact size. Simulations and measured results are presented for several MEMS/CMOS capacitors. A 2-pole coupled line tunable bandpass filter with a center frequency of 9.5 GHz is designed, fabricated and tested. A tuning range of 17% is achieved using integrated variable MEMS/CMOS capacitors with a quality factor exceeding 20. The tunable filter occupies a chip area of 1.2 x 2.1 mm2.
UV Direct-Writing of Metals on Polyimide
Venue: arXiv cs.OH 2008
Year: 2008

Conductive micro-patterned copper tracks were fabricated by UV direct-writing of a nanoparticle silver seed layer followed by selective electroless copper deposition. Silver ions were first incorporated into a hydrolyzed polyimide surface layer by wet chemical treatment. A photoreactive polymer coating, methoxy poly(ethylene glycol) (MPEG) was coated on top of the substrate prior to UV irradiation. Electrons released through the interaction between the MPEG molecules and UV photons allowed the reduction of the silver ions across the MPEG/doped polyimide interface. The resultant silver seed layer has a cluster morphology which is suitable for the initiation of electroless plating. Initial results showed that the deposited copper tracks were in good agreement with the track width on the photomask and laser direct-writing can also fabricate smaller line width metal tracks with good accuracy. The facile fabrication presented here can be carried out in air, at atmospheric pressure, and on contoured surfaces.