OpenRaiser/Intern-Atlas huggingface dataset:
On the Design of Generic Static Analyzers for Modern Imperative Languages
Venue: arXiv cs.PL 2007
Year: 2007

The design and implementation of precise static analyzers for significant fragments of modern imperative languages like C, C++, Java and Python is a challenging problem. In this paper, we consider a core imperative language that has several features found in mainstream languages such as those including recursive functions, run-time system and user-defined exceptions, and a realistic data and memory model. For this language we provide a concrete semantics --characterizing both finite and infinite computations-- and a generic abstract semantics that we prove sound with respect to the concrete one. We say the abstract semantics is generic since it is designed to be completely parametric on the analysis domains: in particular, it provides support for \emph{relational} domains (i.e., abstract domains that can capture the relationships between different data objects). We also sketch how the proposed methodology can be extended to accommodate a larger language that includes pointers, compound data objects and non-structured control flow mechanisms. The approach, which is based on structured, big-step $\mathrm{G}^\infty\mathrm{SOS}$ operational semantics and on abstract interpretation, is modular in that the overall static analyzer is naturally partitioned into components with clearly identified responsibilities and interfaces, something that greatly simplifies both the proof of correctness and the implementation.
Adaptive Methods for Linear Programming Decoding
Venue: arXiv cs.IT 2007
Year: 2007

Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.
Modelling Complexity in Musical Rhythm
Venue: arXiv cs.AI 2007
Year: 2007

This paper constructs a tree structure for the music rhythm using the L-system. It models the structure as an automata and derives its complexity. It also solves the complexity for the L-system. This complexity can resolve the similarity between trees. This complexity serves as a measure of psychological complexity for rhythms. It resolves the music complexity of various compositions including the Mozart effect K488. Keyword: music perception, psychological complexity, rhythm, L-system, automata, temporal associative memory, inverse problem, rewriting rule, bracketed string, tree similarity
ReSHAPE: A Framework for Dynamic Resizing and Scheduling of Homogeneous Applications in a Parallel Environment
Venue: arXiv cs.DC 2007
Year: 2007

Applications in science and engineering often require huge computational resources for solving problems within a reasonable time frame. Parallel supercomputers provide the computational infrastructure for solving such problems. A traditional application scheduler running on a parallel cluster only supports static scheduling where the number of processors allocated to an application remains fixed throughout the lifetime of execution of the job. Due to the unpredictability in job arrival times and varying resource requirements, static scheduling can result in idle system resources thereby decreasing the overall system throughput. In this paper we present a prototype framework called ReSHAPE, which supports dynamic resizing of parallel MPI applications executed on distributed memory platforms. The framework includes a scheduler that supports resizing of applications, an API to enable applications to interact with the scheduler, and a library that makes resizing viable. Applications executed using the ReSHAPE scheduler framework can expand to take advantage of additional free processors or can shrink to accommodate a high priority application, without getting suspended. In our research, we have mainly focused on structured applications that have two-dimensional data arrays distributed across a two-dimensional processor grid. The resize library includes algorithms for processor selection and processor mapping. Experimental results show that the ReSHAPE framework can improve individual job turn-around time and overall system throughput.
Reinforcement Learning for Adaptive Routing
Venue: arXiv cs.LG 2007
Year: 2007

Reinforcement learning means learning a policy--a mapping of observations into actions--based on feedback from the environment. The learning can be viewed as browsing a set of policies while evaluating them by trial through interaction with the environment. We present an application of gradient ascent algorithm for reinforcement learning to a complex domain of packet routing in network communication and compare the performance of this algorithm to other routing methods on a benchmark problem.
Computer Science and Game Theory: A Brief Survey
Venue: arXiv cs.GT 2007
Year: 2007

There has been a remarkable increase in work at the interface of computer science and game theory in the past decade. In this article I survey some of the main themes of work in the area, with a focus on the work in computer science. Given the length constraints, I make no attempt at being comprehensive, especially since other surveys are also available, and a comprehensive survey book will appear shortly.
Asymptotic Analysis of Amplify and Forward Relaying in a Parallel MIMO Relay Network
Venue: arXiv cs.IT 2007
Year: 2007

This paper considers the setup of a parallel MIMO relay network in which $K$ relays, each equipped with $N$ antennas, assist the transmitter and the receiver, each equipped with $M$ antennas, in the half-duplex mode, under the assumption that $N\geq{M}$. This setup has been studied in the literature like in \cite{nabar}, \cite{nabar2}, and \cite{qr}. In this paper, a simple scheme, the so-called Incremental Cooperative Beamforming, is introduced and shown to achieve the capacity of the network in the asymptotic case of $K\to{\infty}$ with a gap no more than $O(\frac{1}{\log(K)})$. This result is shown to hold, as long as the power of the relays scales as $ω(\frac{\log^9(K)}{K})$. Finally, the asymptotic SNR behavior is studied and it is proved that the proposed scheme achieves the full multiplexing gain, regardless of the number of relays.
Liveness of Heap Data for Functional Programs
Venue: arXiv cs.PL 2007
Year: 2007

Functional programming languages use garbage collection for heap memory management. Ideally, garbage collectors should reclaim all objects that are dead at the time of garbage collection. An object is dead at an execution instant if it is not used in future. Garbage collectors collect only those dead objects that are not reachable from any program variable. This is because they are not able to distinguish between reachable objects that are dead and reachable objects that are live. In this paper, we describe a static analysis to discover reachable dead objects in programs written in first-order, eager functional programming languages. The results of this technique can be used to make reachable dead objects unreachable, thereby allowing garbage collectors to reclaim more dead objects.
On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
Venue: arXiv cs.IT 2008
Year: 2008

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes based on stopping and trapping set enumeration cannot provide accurate worst-case performance predictions.
Higher-order theories
Venue: arXiv cs.LO 2008
Year: 2008

We extend our approach to abstract syntax (with binding constructions) through modules and linearity. First we give a new general definition of arity, yielding the companion notion of signature. Then we obtain a modularity result as requested by Ghani and Uustalu (2003): in our setting, merging two extensions of syntax corresponds to building an amalgamated sum. Finally we define a natural notion of equation concerning a signature and prove the existence of an initial semantics for a so-called representable signature equipped with a set of equations.
Rate Bounds for MIMO Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the multi-input multi-output (MIMO) relay channel where multiple antennas are employed by each terminal. Compared to single-input single-output (SISO) relay channels, MIMO relay channels introduce additional degrees of freedom, making the design and analysis of optimal cooperative strategies more complex. In this paper, a partial cooperation strategy that combines transmit-side message splitting and block-Markov encoding is presented. Lower bounds on capacity that improve on a previously proposed non-cooperative lower bound are derived for Gaussian MIMO relay channels.
A Proof of a Recursion for Bessel Moments
Venue: arXiv cs.SC 2008
Year: 2008

We provide a proof of a conjecture in (Bailey, Borwein, Borwein, Crandall 2007) on the existence and form of linear recursions for moments of powers of the Bessel function $K_0$.
High-resolution distributed sampling of bandlimited fields with low-precision sensors
Venue: arXiv cs.IT 2008
Year: 2008

The problem of sampling a discrete-time sequence of spatially bandlimited fields with a bounded dynamic range, in a distributed, communication-constrained, processing environment is addressed. A central unit, having access to the data gathered by a dense network of fixed-precision sensors, operating under stringent inter-node communication constraints, is required to reconstruct the field snapshots to maximum accuracy. Both deterministic and stochastic field models are considered. For stochastic fields, results are established in the almost-sure sense. The feasibility of having a flexible tradeoff between the oversampling rate (sensor density) and the analog-to-digital converter (ADC) precision, while achieving an exponential accuracy in the number of bits per Nyquist-interval per snapshot is demonstrated. This exposes an underlying ``conservation of bits'' principle: the bit-budget per Nyquist-interval per snapshot (the rate) can be distributed along the amplitude axis (sensor-precision) and space (sensor density) in an almost arbitrary discrete-valued manner, while retaining the same (exponential) distortion-rate characteristics. Achievable information scaling laws for field reconstruction over a bounded region are also derived: With N one-bit sensors per Nyquist-interval, $Θ(\log N)$ Nyquist-intervals, and total network bitrate $R_{net} = Θ((\log N)^2)$ (per-sensor bitrate $Θ((\log N)/N)$), the maximum pointwise distortion goes to zero as $D = O((\log N)^2/N)$ or $D = O(R_{net} 2^{-β\sqrt{R_{net}}})$. This is shown to be possible with only nearest-neighbor communication, distributed coding, and appropriate interpolation algorithms. For a fixed, nonzero target distortion, the number of fixed-precision sensors and the network rate needed is always finite.
Distributing the Kalman Filter for Large-Scale Systems
Venue: arXiv cs.IT 2008
Year: 2008

This paper derives a \emph{distributed} Kalman filter to estimate a sparsely connected, large-scale, $n-$dimensional, dynamical system monitored by a network of $N$ sensors. Local Kalman filters are implemented on the ($n_l-$dimensional, where $n_l\ll n$) sub-systems that are obtained after spatially decomposing the large-scale system. The resulting sub-systems overlap, which along with an assimilation procedure on the local Kalman filters, preserve an $L$th order Gauss-Markovian structure of the centralized error processes. The information loss due to the $L$th order Gauss-Markovian approximation is controllable as it can be characterized by a divergence that decreases as $L\uparrow$. The order of the approximation, $L$, leads to a lower bound on the dimension of the sub-systems, hence, providing a criterion for sub-system selection. The assimilation procedure is carried out on the local error covariances with a distributed iterate collapse inversion (DICI) algorithm that we introduce. The DICI algorithm computes the (approximated) centralized Riccati and Lyapunov equations iteratively with only local communication and low-order computation. We fuse the observations that are common among the local Kalman filters using bipartite fusion graphs and consensus averaging algorithms. The proposed algorithm achieves full distribution of the Kalman filter that is coherent with the centralized Kalman filter with an $L$th order Gaussian-Markovian structure on the centralized error processes. Nowhere storage, communication, or computation of $n-$dimensional vectors and matrices is needed; only $n_l \ll n$ dimensional vectors and matrices are communicated or used in the computation at the sensors.
On Fast-Decodable Space-Time Block Codes
Venue: arXiv cs.IT 2008
Year: 2008

We focus on full-rate, fast-decodable space-time block codes (STBCs) for 2x2 and 4x2 multiple-input multiple-output (MIMO) transmission. We first derive conditions for reduced-complexity maximum-likelihood decoding, and apply them to a unified analysis of two families of 2x2 STBCs that were recently proposed. In particular, we describe a reduced-complexity sphere decoding algorithm suitable for QAM signal constellations. Next, we derive a novel reduced-complexity 4x2 STBC, and show that it outperforms all previously known codes with certain constellations.
Effective Generation of Subjectively Random Binary Sequences
Venue: arXiv cs.HC 2008
Year: 2008

We present an algorithm for effectively generating binary sequences which would be rated by people as highly likely to have been generated by a random process, such as flipping a fair coin.
Geometric Complexity Theory VII: Nonstandard quantum group for the plethysm problem
Venue: arXiv cs.CC 2008
Year: 2008

This article describes a {\em nonstandard} quantum group that may be used to derive a positive formula for the plethysm problem, just as the standard (Drinfeld-Jimbo) quantum group can be used to derive the positive Littlewood-Richardson rule for arbitrary complex semisimple Lie groups. The sequel \cite{GCT8} gives conjecturally correct algorithms to construct canonical bases of the coordinate rings of these nonstandard quantum groups and canonical bases of the dually paired nonstandard deformations of the symmetric group algebra. A positive $#P$-formula for the plethysm constant follows from the conjectural properties of these canonical bases and the duality and reciprocity conjectures herein.
Evaluation experiments on related terms search in Wikipedia: Information Content and Adapted HITS (In Russian)
Venue: arXiv cs.IR 2008
Year: 2008

The classification of metrics and algorithms search for related terms via WordNet, Roget's Thesaurus, and Wikipedia was extended to include adapted HITS algorithm. Evaluation experiments on Information Content and adapted HITS algorithm are described. The test collection of Russian word pairs with human-assigned similarity judgments is proposed. ----- Klassifikacija metrik i algoritmov poiska semanticheski blizkih slov v tezaurusah WordNet, Rozhe i jenciklopedii Vikipedija rasshirena adaptirovannym HITS algoritmom. S pomow'ju jeksperimentov v Vikipedii oceneny metrika Information Content i adaptirovannyj algoritm HITS. Predlozhen resurs dlja ocenki semanticheskoj blizosti russkih slov.
New Counting Codes for Distributed Video Coding
Venue: arXiv cs.IT 2008
Year: 2008

This paper introduces a new counting code. Its design was motivated by distributed video coding where, for decoding, error correction methods are applied to improve predictions. Those error corrections sometimes fail which results in decoded values worse than the initial prediction. Our code exploits the fact that bit errors are relatively unlikely events: more than a few bit errors in a decoded pixel value are rare. With a carefully designed counting code combined with a prediction those bit errors can be corrected and sometimes the original pixel value recovered. The error correction improves significantly. Our new code not only maximizes the Hamming distance between adjacent (or "near 1") codewords but also between nearby (for example "near 2") codewords. This is why our code is significantly different from the well-known maximal counting sequences which have maximal average Hamming distance. Fortunately, the new counting code can be derived from Gray Codes for every code word length (i.e. bit depth).
Bandwidth Partitioning in Decentralized Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper addresses the following question, which is of interest in the design of a multiuser decentralized network. Given a total system bandwidth of W Hz and a fixed data rate constraint of R bps for each transmission, how many frequency slots N of size W/N should the band be partitioned into in order to maximize the number of simultaneous links in the network? Dividing the available spectrum results in two competing effects. On the positive side, a larger N allows for more parallel, noninterfering communications to take place in the same area. On the negative side, a larger N increases the SINR requirement for each link because the same information rate must be achieved over less bandwidth. Exploring this tradeoff and determining the optimum value of N in terms of the system parameters is the focus of the paper. Using stochastic geometry, the optimal SINR threshold - which directly corresponds to the optimal spectral efficiency - is derived for both the low SNR (power-limited) and high SNR (interference-limited) regimes. This leads to the optimum choice of the number of frequency bands N in terms of the path loss exponent, power and noise spectral density, desired rate, and total bandwidth.
Noise threshold for universality of 2-input gates
Venue: arXiv cs.IT 2008
Year: 2008

Evans and Pippenger showed in 1998 that noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability epsilon and epsilon<theta, where theta is roughly 8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least theta cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is theta. We conjecture that the same threshold also holds for circuits.
Predicting relevant empty spots in social interaction
Venue: arXiv cs.AI 2008
Year: 2008

An empty spot refers to an empty hard-to-fill space which can be found in the records of the social interaction, and is the clue to the persons in the underlying social network who do not appear in the records. This contribution addresses a problem to predict relevant empty spots in social interaction. Homogeneous and inhomogeneous networks are studied as a model underlying the social interaction. A heuristic predictor function approach is presented as a new method to address the problem. Simulation experiment is demonstrated over a homogeneous network. A test data in the form of baskets is generated from the simulated communication. Precision to predict the empty spots is calculated to demonstrate the performance of the presented approach.
A Family of Likelihood Ascent Search Multiuser Detectors: an Upper Bound of Bit Error Rate and a Lower Bound of Asymptotic Multiuser Efficiency
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, the bit error performance of a family of likelihood ascent search (LAS) multiuser detectors is analyzed. An upper bound on the BER of any LAS detector is obtained by bounding the fixed point region with the worst initial detector. The concept of indecomposable errors developed by Verdu is applied to tighten the upper bound. In a special instance, the upper bound is reduced to that for all the local maximum likelihood detectors. The upper bound is comparable with that of the optimum detector obtained by Verdu. A lower bound on the asymptotic multiuser efficiency (AME) is then obtained. It is shown that there are nontrivial CDMA channels such that a LAS detector can achieve unit AME regardless of user number. The AME lower bound provides a means for further seeking a good set of spreading sequences and power distribution for spectral and power efficient CDMA.
Randomness and metastability in CDMA paradigms
Venue: arXiv cs.IT 2008
Year: 2008

Code Division Multiple Access (CDMA) in which the signature code assignment to users contains a random element has recently become a cornerstone of CDMA research. The random element in the construction is particularly attractive in that it provides robustness and flexibility in application, whilst not making significant sacrifices in terms of multiuser efficiency. We present results for sparse random codes of two types, with and without modulation. Simple microscopic consideration on system samples would suggest differences in the phase space of the two models, but we demonstrate that the thermodynamic results and metastable states are equivalent in the minimum bit error rate detector. We analyse marginal properties of interactions and also make analogies to constraint satisfiability problems in order to understand qualitative features of detection and metastable states. This may have consequences for developing algorithmic methods to escape metastable states, thus improving decoding performance.
Cooperative Relaying with State Available at the Relay
Venue: arXiv cs.IT 2008
Year: 2008

We consider a state-dependent full-duplex relay channel with the state of the channel non-causally available at only the relay. In the framework of cooperative wireless networks, some specific terminals can be equipped with cognition capabilities, i.e, the relay in our model. In the discrete memoryless (DM) case, we derive lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme at the relay that consists in a combination of codeword splitting, Gel'fand-Pinsker binning, and a decode-and-forward scheme. The upper bound is better than that obtained by assuming that the channel state is available at the source and the destination as well. For the Gaussian case, we also derive lower and upper bounds on channel capacity. The lower bound is obtained by a coding scheme which is based on a combination of codeword splitting and Generalized dirty paper coding. The upper bound is also better than that obtained by assuming that the channel state is available at the source, the relay, and the destination. The two bounds meet, and so give the capacity, in some special cases for the degraded Gaussian case.
Upper Bounds for the Number of Hamiltonian Cycles
Venue: arXiv cs.DM 2008
Year: 2008

An upper bound for the number of Hamiltonian cycles of symmetric diagraphs is established first in this paper, which is tighter than the famous Minc's bound and the Br$\acute{e}$gman's bound. A transformation on graphs is proposed, so that counting the number of Hamiltonian cycles of an undirected graph can be done by counting the number of Hamiltonian cycles of its corresponding symmetric directed graph. In this way, an upper bound for the number of Hamiltonian cycles of undirected graphs is also obtained.