OpenRaiser/Intern-Atlas huggingface dataset:
Assessing scientific research performance and impact with single indices
Venue: arXiv cs.IR 2009
Year: 2009

We provide a comprehensive and critical review of the h-index and its most important modifications proposed in the literature, as well as of other similar indicators measuring research output and impact. Extensions of some of these indices are presented and illustrated.
Maximum Entropy on Compact Groups
Venue: arXiv cs.IT 2009
Year: 2009

On a compact group the Haar probability measure plays the role of uniform distribution. The entropy and rate distortion theory for this uniform distribution is studied. New results and simplified proofs on convergence of convolutions on compact groups are presented and they can be formulated as entropy increases to its maximum. Information theoretic techniques and Markov chains play a crucial role. The convergence results are also formulated via rate distortion functions. The rate of convergence is shown to be exponential.
Techniques for Distributed Reachability Analysis with Partial Order and Symmetry based Reductions
Venue: arXiv cs.DC 2009
Year: 2009

In this work we propose techniques for efficient reachability analysis of the state space (e.g., detection of bad states) using a combination of partial order and symmetry based reductions in a distributed setting. The proposed techniques are focused towards explicit state space enumeration based model-checkers like SPIN. We consider variants for both depth-first as well as breadth-first based generation of the reduced state graphs on-the-fly.
On Allocating Goods to Maximize Fairness
Venue: arXiv cs.DS 2009
Year: 2009

Given a set of $m$ agents and a set of $n$ items, where agent $A$ has utility $u_{A,i}$ for item $i$, our goal is to allocate items to agents to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an $\tilde{O}(\sqrt{m})$-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an approximation algorithm that achieves an $\tilde{O}(n^{\eps})$ approximation for any $\eps=Ω(\log\log n/\log n)$ in time $n^{O(1/\eps)}$. In particular, we obtain poly-logarithmic approximation in quasi-polynomial time, and for any constant $\eps > 0$, we obtain $O(n^{\eps})$ approximation in polynomial time. An interesting aspect of our algorithm is that we use as a building block a linear program whose integrality gap is $Ω(\sqrt m)$. We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. We also investigate the special case of the problem, where every item has a non-zero utility for at most two agents. We show that even in this restricted setting the problem is hard to approximate upto any factor better tha 2, and show a factor $(2+\eps)$-approximation algorithm running in time $poly(n,1/\eps)$ for any $\eps>0$. This special case can be cast as a graph edge orientation problem, and our algorithm can be viewed as a generalization of Eulerian orientations to weighted graphs.
Comments on "Broadcast Channels with Arbitrarily Correlated Sources"
Venue: arXiv cs.IT 2009
Year: 2009

The Marton-Gelfand-Pinsker inner bound on the capacity region of broadcast channels was extended by Han-Costa to include arbitrarily correlated sources where the capacity region is replaced by an admissible source region. The main arguments of Han-Costa are correct but unfortunately the authors overlooked an inequality in their derivation. The corrected region is presented and the absence of the omitted inequality is shown to sometimes admit sources that are not admissible.
Weighted Naive Bayes Model for Semi-Structured Document Categorization
Venue: arXiv cs.IR 2009
Year: 2009

The aim of this paper is the supervised classification of semi-structured data. A formal model based on bayesian classification is developed while addressing the integration of the document structure into classification tasks. We define what we call the structural context of occurrence for unstructured data, and we derive a recursive formulation in which parameters are used to weight the contribution of structural element relatively to the others. A simplified version of this formal model is implemented to carry out textual documents classification experiments. First results show, for a adhoc weighting strategy, that the structural context of word occurrences has a significant impact on classification results comparing to the performance of a simple multinomial naive Bayes classifier. The proposed implementation competes on the Reuters-21578 data with the SVM classifier associated or not with the splitting of structural components. These results encourage exploring the learning of acceptable weighting strategies for this model, in particular boosting strategies.
Highly Undecidable Problems For Infinite Computations
Venue: arXiv cs.LO 2009
Year: 2009

We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are $Π_2^1$-complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all $Π_2^1$-complete for context-free omega-languages or for infinitary rational relations. Topological and arithmetical properties of 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are also highly undecidable. These very surprising results provide the first examples of highly undecidable problems about the behaviour of very simple finite machines like 1-counter automata or 2-tape automata.
A new muscle fatigue and recovery model and its ergonomics application in human simulation
Venue: arXiv cs.RO 2009
Year: 2009

Although automatic techniques have been employed in manufacturing industries to increase productivity and efficiency, there are still lots of manual handling jobs, especially for assembly and maintenance jobs. In these jobs, musculoskeletal disorders (MSDs) are one of the major health problems due to overload and cumulative physical fatigue. With combination of conventional posture analysis techniques, digital human modelling and simulation (DHM) techniques have been developed and commercialized to evaluate the potential physical exposures. However, those ergonomics analysis tools are mainly based on posture analysis techniques, and until now there is still no fatigue index available in the commercial software to evaluate the physical fatigue easily and quickly. In this paper, a new muscle fatigue and recovery model is proposed and extended to evaluate joint fatigue level in manual handling jobs. A special application case is described and analyzed by digital human simulation technique.
An Ω(n log n) lower bound for computing the sum of even-ranked elements
Venue: arXiv cs.DS 2009
Year: 2009

Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove that, in the algebraic computation-tree model, this problem has time complexity Θ(n log n). This solves an open problem posed by Michael Shamos at the Canadian Conference on Computational Geometry in 2008.
FAIR: Fuzzy-based Aggregation providing In-network Resilience for real-time Wireless Sensor Networks
Venue: arXiv cs.CR 2009
Year: 2009

This work introduces FAIR, a novel framework for Fuzzy-based Aggregation providing In-network Resilience for Wireless Sensor Networks. FAIR addresses the possibility of malicious aggregator nodes manipulating data. It provides data-integrity based on a trust level of the WSN response and it tolerates link or node failures. Compared to available solutions, it offers a general aggregation model and makes the trust level visible to the querier. We classify the proposed approach as complementary to protocols ensuring resilience against sensor leaf nodes providing faulty data. Thanks to our flexible resilient framework and due to the use of Fuzzy Inference Schemes, we achieve promising results within a short design cycle.
Constructions of Quasi-Twisted Two-Weight Codes
Venue: arXiv cs.IT 2009
Year: 2009

A code is said to be two-weight if the non-zero codewords have only two different a weight w1 and w2. Two-weight codes are closely related to strongly regular graphs. In this paper. It is shown that a consta-cyclic code of composite length can be put in the quasi-twisted form. Based on this transformation, a new construction method of quasi-twisted (QT) two-weight codes is presented. A large amount of QT two-weight codes are found, and some new codes are also constructed.
Adaptive threshold-based decision for efficient hybrid deflection and retransmission scheme in OBS networks
Venue: arXiv cs.NI 2009
Year: 2009

Burst contention is a well-known challenging problem in Optical Burst Switching (OBS) networks. Deflection routing is used to resolve contention. Burst retransmission is used to reduce the Burst Loss Ratio (BLR) by retransmitting dropped bursts. Previous works show that combining deflection and retransmission outperforms both pure deflection and pure retransmission approaches. This paper proposes a new Adaptive Hybrid Deflection and Retransmission (AHDR) approach that dynamically combines deflection and retransmission approaches based on network conditions such as BLR and link utilization. Network Simulator 2 (ns-2) is used to simulate the proposed approach on different network topologies. Simulation results show that the proposed approach outperforms static approaches in terms of BLR by using an adaptive decision threshold.
Feedback Communication over Individual Channels
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of communicating over a channel for which no mathematical model is specified. We present achievable rates as a function of the channel input and output sequences known a-posteriori for discrete and continuous channels. Furthermore we present a rate-adaptive scheme employing feedback which achieves these rates asymptotically without prior knowledge of the channel behavior.
A Holistic Approach to Information Distribution in Ad Hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

We investigate the problem of spreading information contents in a wireless ad hoc network with mechanisms embracing the peer-to-peer paradigm. In our vision, information dissemination should satisfy the following requirements: (i) it conforms to a predefined distribution and (ii) it is evenly and fairly carried by all nodes in their turn. In this paper, we observe the dissemination effects when the information moves across nodes according to two well-known mobility models, namely random walk and random direction. Our approach is fully distributed and comes at a very low cost in terms of protocol overhead; in addition, simulation results show that the proposed solution can achieve the aforementioned goals under different network scenarios, provided that a sufficient number of information replicas are injected into the network. This observation calls for a further step: in the realistic case where the user content demand varies over time, we need a content replication/drop strategy to adapt the number of information replicas to the changes in the information query rate. We therefore devise a distributed, lightweight scheme that performs efficiently in a variety of scenarios.
Low-Complexity Near-ML Decoding of Large Non-Orthogonal STBCs using Reactive Tabu Search
Venue: arXiv cs.IT 2009
Year: 2009

Non-orthogonal space-time block codes (STBC) with {\em large dimensions} are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) {\em as well as} full transmit diversity. Decoding of non-orthogonal STBCs with large dimensions has been a challenge. In this paper, we present a reactive tabu search (RTS) based algorithm for decoding non-orthogonal STBCs from cyclic division algebras (CDA) having large dimensions. Under i.i.d fading and perfect channel state information at the receiver (CSIR), our simulation results show that RTS based decoding of $12\times 12$ STBC from CDA and 4-QAM with 288 real dimensions achieves $i)$ $10^{-3}$ uncoded BER at an SNR of just 0.5 dB away from SISO AWGN performance, and $ii)$ a coded BER performance close to within about 5 dB of the theoretical MIMO capacity, using rate-3/4 turbo code at a spectral efficiency of 18 bps/Hz. RTS is shown to achieve near SISO AWGN performance with less number of dimensions than with LAS algorithm (which we reported recently) at some extra complexity than LAS. We also report good BER performance of RTS when i.i.d fading and perfect CSIR assumptions are relaxed by considering a spatially correlated MIMO channel model, and by using a training based iterative RTS decoding/channel estimation scheme.
Joint universal lossy coding and identification of stationary mixing sources with general alphabets
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of joint universal variable-rate lossy coding and identification for parametric classes of stationary $β$-mixing sources with general (Polish) alphabets. Compression performance is measured in terms of Lagrangians, while identification performance is measured by the variational distance between the true source and the estimated source. Provided that the sources are mixing at a sufficiently fast rate and satisfy certain smoothness and Vapnik-Chervonenkis learnability conditions, it is shown that, for bounded metric distortions, there exist universal schemes for joint lossy compression and identification whose Lagrangian redundancies converge to zero as $\sqrt{V_n \log n /n}$ as the block length $n$ tends to infinity, where $V_n$ is the Vapnik-Chervonenkis dimension of a certain class of decision regions defined by the $n$-dimensional marginal distributions of the sources; furthermore, for each $n$, the decoder can identify $n$-dimensional marginal of the active source up to a ball of radius $O(\sqrt{V_n\log n/n})$ in variational distance, eventually with probability one. The results are supplemented by several examples of parametric sources satisfying the regularity conditions.
Achievability results for statistical learning under communication constraints
Venue: arXiv cs.IT 2009
Year: 2009

The problem of statistical learning is to construct an accurate predictor of a random variable as a function of a correlated random variable on the basis of an i.i.d. training sample from their joint distribution. Allowable predictors are constrained to lie in some specified class, and the goal is to approach asymptotically the performance of the best predictor in the class. We consider two settings in which the learning agent only has access to rate-limited descriptions of the training data, and present information-theoretic bounds on the predictor performance achievable in the presence of these communication constraints. Our proofs do not assume any separation structure between compression and learning and rely on a new class of operational criteria specifically tailored to joint design of encoders and learning algorithms in rate-constrained settings.
The Sensing Capacity of Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

This paper demonstrates fundamental limits of sensor networks for detection problems where the number of hypotheses is exponentially large. Such problems characterize many important applications including detection and classification of targets in a geographical area using a network of sensors, and detecting complex substances with a chemical sensor array. We refer to such applications as largescale detection problems. Using the insight that these problems share fundamental similarities with the problem of communicating over a noisy channel, we define a quantity called the sensing capacity and lower bound it for a number of sensor network models. The sensing capacity expression differs significantly from the channel capacity due to the fact that a fixed sensor configuration encodes all states of the environment. As a result, codewords are dependent and non-identically distributed. The sensing capacity provides a bound on the minimal number of sensors required to detect the state of an environment to within a desired accuracy. The results differ significantly from classical detection theory, and provide an ntriguing connection between sensor networks and communications. In addition, we discuss the insight that sensing capacity provides for the problem of sensor selection.
Bit Precision Analysis for Compressed Sensing
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the stability of some reconstruction algorithms for compressed sensing in terms of the bit precision. Considering the fact that practical digital systems deal with discretized signals, we motivate the importance of the total number of accurate bits needed from the measurement outcomes in addition to the number of measurements. It is shown that if one uses a $2k \times n$ Vandermonde matrix with roots on the unit circle as the measurement matrix, $O(\ell + k \log(n/k))$ bits of precision per measurement are sufficient to reconstruct a $k$-sparse signal $x \in \R^n$ with dynamic range (i.e., the absolute ratio between the largest and the smallest nonzero coefficients) at most $2^\ell$ within $\ell$ bits of precision, hence identifying its correct support. Finally, we obtain an upper bound on the total number of required bits when the measurement matrix satisfies a restricted isometry property, which is in particular the case for random Fourier and Gaussian matrices. For very sparse signals, the upper bound on the number of required bits for Vandermonde matrices is shown to be better than this general upper bound.
Improved community structure detection using a modified fine tuning strategy
Venue: arXiv cs.CY 2009
Year: 2009

The community structure of a complex network can be determined by finding the partitioning of its nodes that maximizes modularity. Many of the proposed algorithms for doing this work by recursively bisecting the network. We show that this unduely constrains their results, leading to a bias in the size of the communities they find and limiting their effectivness. To solve this problem, we propose adding a step to the existing algorithms that does not increase the order of their computational complexity. We show that, if this step is combined with a commonly used method, the identified constraint and resulting bias are removed, and its ability to find the optimal partitioning is improved. The effectiveness of this combined algorithm is also demonstrated by using it on real-world example networks. For a number of these examples, it achieves the best results of any known algorithm.
Discovering Global Patterns in Linguistic Networks through Spectral Analysis: A Case Study of the Consonant Inventories
Venue: arXiv cs.CL 2009
Year: 2009

Recent research has shown that language and the socio-cognitive phenomena associated with it can be aptly modeled and visualized through networks of linguistic entities. However, most of the existing works on linguistic networks focus only on the local properties of the networks. This study is an attempt to analyze the structure of languages via a purely structural technique, namely spectral analysis, which is ideally suited for discovering the global correlations in a network. Application of this technique to PhoNet, the co-occurrence network of consonants, not only reveals several natural linguistic principles governing the structure of the consonant inventories, but is also able to quantify their relative importance. We believe that this powerful technique can be successfully applied, in general, to study the structure of natural languages.
An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources
Venue: arXiv cs.IT 2009
Year: 2009

We present a new lossy compressor for discrete sources. For coding a source sequence $x^n$, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by a linear combination of its empirical probabilities of some order $k+1$ and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large $n$, provided $k$ is increased as $o(\log n)$.
Joint Source-Channel Coding at the Application Layer for Parallel Gaussian Sources
Venue: arXiv cs.IT 2009
Year: 2009

In this paper the multicasting of independent parallel Gaussian sources over a binary erasure broadcasted channel is considered. Multiresolution embedded quantizer and layered joint source-channel coding schemes are used in order to serve simultaneously several users at different channel capacities. The convex nature of the rate-distortion function, computed by means of reverse water-filling, allows us to solve relevant convex optimization problems corresponding to different performance criteria. Then, layered joint source-channel codes are constructed based on the concatenation of embedded scalar quantizers with binary rateless encoders.
Grammatic -- a tool for grammar definition reuse and modularity
Venue: arXiv cs.PL 2009
Year: 2009

Grammatic is a tool for grammar definition and manipulation aimed to improve modularity and reuse of grammars and related development artifacts. It is independent from parsing technology and any other details of target system implementation. Grammatic provides a way for annotating grammars with arbitrary metadata (like associativity attributes, semantic actions or anything else). It might be used as a front-end for external tools like parser generators to make their input grammars modular and reusable. This paper describes main principles behind Grammatic and gives an overview of languages it provides and their ability to separate concerns and define reusable modules. Also it presents sketches of possible use cases for the tool.