OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic information theory
Venue: arXiv cs.IT 2008
Year: 2008

We introduce algorithmic information theory, also known as the theory of Kolmogorov complexity. We explain the main concepts of this quantitative approach to defining `information'. We discuss the extent to which Kolmogorov's and Shannon's information theory have a common purpose, and where they are fundamentally different. We indicate how recent developments within the theory allow one to formally distinguish between `structural' (meaningful) and `random' information as measured by the Kolmogorov structure function, which leads to a mathematical formalization of Occam's razor in inductive inference. We end by discussing some of the philosophical implications of the theory.
Correlation of Expert and Search Engine Rankings
Venue: arXiv cs.DL 2008
Year: 2008

In previous research it has been shown that link-based web page metrics can be used to predict experts' assessment of quality. We are interested in a related question: do expert rankings of real-world entities correlate with search engine rankings of corresponding web resources? For example, each year US News & World Report publishes a list of (among others) top 50 graduate business schools. Does their expert ranking correlate with the search engine ranking of the URLs of those business schools? To answer this question we conducted 9 experiments using 8 expert rankings on a range of academic, athletic, financial and popular culture topics. We compared the expert rankings with the rankings in Google, Live Search (formerly MSN) and Yahoo (with list lengths of 10, 25, and 50). In 57 search engine vs. expert comparisons, only 1 strong and 4 moderate correlations were statistically significant. In 42 inter-search engine comparisons, only 2 strong and 4 moderate correlations were statistically significant. The correlations appeared to decrease with the size of the lists: the 3 strong correlations were for lists of 10, the 8 moderate correlations were for lists of 25, and no correlations were found for lists of 50.
Automating Spreadsheet Discovery & Risk Assessment
Venue: arXiv cs.SE 2008
Year: 2008

There have been many articles and mishaps published about the risks of uncontrolled spreadsheets in today's business environment, including non-compliance, operational risk, errors, and fraud all leading to significant loss events. Spreadsheets fall into the realm of end user developed applications and are often absent the proper safeguards and controls an IT organization would enforce for enterprise applications. There is also an overall lack of software programming discipline enforced in how spreadsheets are developed. However, before an organization can apply proper controls and discipline to critical spreadsheets, an accurate and living inventory of spreadsheets across the enterprise must be created, and all critical spreadsheets must be identified. As such, this paper proposes an automated approach to the initial stages of the spreadsheet management lifecycle - discovery, inventory and risk assessment. Without the use of technology, these phases are often treated as a one-off project. By leveraging technology, they become a sustainable business process.
Finding links and initiators: a graph reconstruction problem
Venue: arXiv cs.AI 2008
Year: 2008

Consider a 0-1 observation matrix M, where rows correspond to entities and columns correspond to signals; a value of 1 (or 0) in cell (i,j) of M indicates that signal j has been observed (or not observed) in entity i. Given such a matrix we study the problem of inferring the underlying directed links between entities (rows) and finding which entries in the matrix are initiators. We formally define this problem and propose an MCMC framework for estimating the links and the initiators given the matrix of observations M. We also show how this framework can be extended to incorporate a temporal aspect; instead of considering a single observation matrix M we consider a sequence of observation matrices M1,..., Mt over time. We show the connection between our problem and several problems studied in the field of social-network analysis. We apply our method to paleontological and ecological data and show that our algorithms work well in practice and give reasonable results.
Interference Alignment for Line-of-Sight Channels
Venue: arXiv cs.IT 2008
Year: 2008

The fully connected K-user interference channel is studied in a multipath environment with bandwidth W. We show that when each link consists of D physical paths, the total spectral efficiency can grow {\it linearly} with K. This result holds not merely in the limit of large transmit power P, but for any fixed P, and is therefore a stronger characterization than degrees of freedom. It is achieved via a form of interference alignment in the time domain. A caveat of this result is that W must grow with K, a phenomenon we refer to as {\it bandwidth scaling}. Our insight comes from examining channels with single path links (D=1), which we refer to as line-of-sight (LOS) links. For such channels we build a time-indexed interference graph and associate the communication problem with finding its maximal independent set. This graph has a stationarity property that we exploit to solve the problem efficiently via dynamic programming. Additionally, the interference graph enables us to demonstrate the necessity of bandwidth scaling for any scheme operating over LOS interference channels. Bandwidth scaling is then shown to also be a necessary ingredient for interference alignment in the K-user interference channel.
Using descriptive mark-up to formalize translation quality assessment
Venue: arXiv cs.CL 2008
Year: 2008

The paper deals with using descriptive mark-up to emphasize translation mistakes. The author postulates the necessity to develop a standard and formal XML-based way of describing translation mistakes. It is considered to be important for achieving impersonal translation quality assessment. Marked-up translations can be used in corpus translation studies; moreover, automatic translation assessment based on marked-up mistakes is possible. The paper concludes with setting up guidelines for further activity within the described field.
Changing Assembly Modes without Passing Parallel Singularities in Non-Cuspidal 3-R\underline{P}R Planar Parallel Robots
Venue: arXiv cs.RO 2008
Year: 2008

This paper demonstrates that any general 3-DOF three-legged planar parallel robot with extensible legs can change assembly modes without passing through parallel singularities (configurations where the mobile platform loses its stiffness). While the results are purely theoretical, this paper questions the very definition of parallel singularities.
An Exploratory Study of Calendar Use
Venue: arXiv cs.HC 2008
Year: 2008

In this paper, we report on findings from an ethnographic study of how people use their calendars for personal information management (PIM). Our participants were faculty, staff and students who were not required to use or contribute to any specific calendaring solution, but chose to do so anyway. The study was conducted in three parts: first, an initial survey provided broad insights into how calendars were used; second, this was followed up with personal interviews of a few participants which were transcribed and content-analyzed; and third, examples of calendar artifacts were collected to inform our analysis. Findings from our study include the use of multiple reminder alarms, the reliance on paper calendars even among regular users of electronic calendars, and wide use of calendars for reporting and life-archival purposes. We conclude the paper with a discussion of what these imply for designers of interactive calendar systems and future work in PIM research.
A High Performance Memory Database for Web Application Caches
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents the architecture and characteristics of a memory database intended to be used as a cache engine for web applications. Primary goals of this database are speed and efficiency while running on SMP systems with several CPU cores (four and more). A secondary goal is the support for simple metadata structures associated with cached data that can aid in efficient use of the cache. Due to these goals, some data structures and algorithms normally associated with this field of computing needed to be adapted to the new environment.
Approximating acyclicity parameters of sparse hypergraphs
Venue: arXiv cs.DS 2008
Year: 2008

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph H is constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class. This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class.
On Gaussian MIMO BC-MAC Duality With Multiple Transmit Covariance Constraints
Venue: arXiv cs.IT 2008
Year: 2008

Owing to the structure of the Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC), associated optimization problems such as capacity region computation and beamforming optimization are typically non-convex, and cannot be solved directly. One feasible approach to these problems is to transform them into their dual multiple access channel (MAC) problems, which are easier to deal with due to their convexity properties. The conventional BC-MAC duality is established via BC-MAC signal transformation, and has been successfully applied to solve beamforming optimization, signal-to-interference-plus-noise ratio (SINR) balancing, and capacity region computation. However, this conventional duality approach is applicable only to the case, in which the base station (BS) of the BC is subject to a single sum power constraint. An alternative approach is minimax duality, established by Yu in the framework of Lagrange duality, which can be applied to solve the per-antenna power constraint problem. This paper extends the conventional BC-MAC duality to the general linear constraint case, and thereby establishes a general BC-MAC duality. This new duality is applied to solve the capacity computation and beamforming optimization for the MIMO and multiple-input single-output (MISO) BC, respectively, with multiple linear constraints. Moreover, the relationship between this new general BC-MAC duality and minimax duality is also presented. It is shown that the general BC-MAC duality offers more flexibility in solving BC optimization problems relative to minimax duality. Numerical results are provided to illustrate the effectiveness of the proposed algorithms.
Towards a More Accurate Carrier Sensing Model for CSMA Wireless Networks
Venue: arXiv cs.NI 2008
Year: 2008

This work calls into question a substantial body of past work on CSMA wireless networks. In the majority of studies on CSMA wireless networks, a contention graph is used to model the carrier sensing relationships (CS) among links. This is a 0-1 model in which two links can either sense each other completely or not. In real experiments, we observed that this is generally not the case: the CS relationship between the links are often probabilistic and can vary dynamically over time. This is the case even if the distance between the links is fixed and there is no drastic change in the environment. Furthermore, this partial carrier sensing relationship is prevalent and occurs over a wide range of distances between the links. This observation is not consistent with the 0-1 contention graph and implies that many results and conclusions drawn from previous theoretical studies need to be re-examined. This paper establishes a more accurate CS model with the objective of laying down a foundation for future theoretical studies that reflect reality. Towards that end, we set up detailed experiments to investigate the partial carrier sensing phenomenon. We discuss the implications and the use of our partial carrier sensing model in network analysis.
Llull and Copeland Voting Computationally Resist Bribery and Control
Venue: arXiv cs.GT 2008
Year: 2008

The only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. We study a parameterized version of Copeland voting, denoted by Copeland^α, where the parameter αis a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. We prove that Copeland^{0.5}, the system commonly referred to as "Copeland voting," provides full resistance to constructive control, and we prove the same for Copeland^α, for all rational α, 0 < α< 1. Copeland voting is the first natural election system proven to have full resistance to constructive control. We also prove that both Copeland^1 (Llull elections) and Copeland^0 are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational α, 0 \leq α\leq 1, Copeland^αvoting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^α. We also study Copeland^αelections under more flexible models such as microbribery and extended control and we integrate the potential irrationality of voter preferences into many of our results.
Achieving compositionality of the stable model semantics for Smodels programs
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, a Gaifman-Shapiro-style module architecture is tailored to the case of Smodels programs under the stable model semantics. The composition of Smodels program modules is suitably limited by module conditions which ensure the compatibility of the module system with stable models. Hence the semantics of an entire Smodels program depends directly on stable models assigned to its modules. This result is formalized as a module theorem which truly strengthens Lifschitz and Turner's splitting-set theorem for the class of Smodels programs. To streamline generalizations in the future, the module theorem is first proved for normal programs and then extended to cover Smodels programs using a translation from the latter class of programs to the former class. Moreover, the respective notion of module-level equivalence, namely modular equivalence, is shown to be a proper congruence relation: it is preserved under substitutions of modules that are modularly equivalent. Principles for program decomposition are also addressed. The strongly connected components of the respective dependency graph can be exploited in order to extract a module structure when there is no explicit a priori knowledge about the modules of a program. The paper includes a practical demonstration of tools that have been developed for automated (de)composition of Smodels programs. To appear in Theory and Practice of Logic Programming.
Secure Wireless Communications via Cooperation
Venue: arXiv cs.IT 2008
Year: 2008

The feasibility of physical-layer-based security approaches for wireless communications in the presence of one or more eavesdroppers is hampered by channel conditions. In this paper, cooperation is investigated as an approach to overcome this problem and improve the performance of secure communications. In particular, a decode-and-forward (DF) based cooperative protocol is considered, and the objective is to design the system for secrecy capacity maximization or transmit power minimization. System design for the DF-based cooperative protocol is first studied by assuming the availability of global channel state information (CSI). For the case of one eavesdropper, an iterative scheme is proposed to obtain the optimal solution for the problem of transmit power minimization. For the case of multiple eavesdroppers, the problem of secrecy capacity maximization or transmit power minimization is in general intractable. Suboptimal system design is proposed by adding an additional constraint, i.e., the complete nulling of signals at all eavesdroppers, which yields simple closed-form solutions for the aforementioned two problems. Then, the impact of imperfect CSI of eavesdroppers on system design is studied, in which the ergodic secrecy capacity is of interest.
Relevance Feedback in Conceptual Image Retrieval: A User Evaluation
Venue: arXiv cs.IR 2008
Year: 2008

The Visual Object Information Retrieval (VOIR) system described in this paper implements an image retrieval approach that combines two layers, the conceptual and the visual layer. It uses terms from a textual thesaurus to represent the conceptual information and also works with image regions, the visual information. The terms are related with the image regions through a weighted association enabling the execution of concept-level queries. VOIR uses region-based relevance feedback to improve the quality of the results in each query session and to discover new associations between text and image. This paper describes a user-centred and task-oriented comparative evaluation of VOIR which was undertaken considering three distinct versions of VOIR: a full-fledge version; one supporting relevance feedback only at image level; and a third version not supporting relevance feedback at all. The evaluation performed showed the usefulness of region based relevance feedback in the context of VOIR prototype.
16 Propositions to Reconsider the Organization of a Scientific Workshop
Venue: arXiv cs.CY 2008
Year: 2008

Participating a scientific workshop is nowadays often an adventure because the number of participants do seldom exceed the number of talks. A half-day workshop is mostly finished at lunchtime, speakers are sometimes not present and unexcused, and a strict progression of the workshop offers little air for discussion. And when talks are re-scheduled on short notice in case that a speech is dropped out, attaining guests definitely wonder why the presenter is talking about something that does not match the previously announced talk. In this respect, we believe that the organization of a workshop in the classical sense must be reconsidered. It is not enough of compelling the presenters to pay the registration fee only and to let the participants being impassive or taken away mentally. With this work, we address several propositions to become implemented in the future workshop organization. With that, we hope to contribute to the identification of scientific workshops as a place of interaction.
Efficient 3D Space Time Space Block Code for Future Terrestrial Digital TV
Venue: arXiv cs.NI 2008
Year: 2008

This article introduces a 3D space-time-space block code for future terrestrial digital TV in single frequency networks. The proposed 3D code is based on a double layer structure designed for inter-cell and intra-cell space time coded transmissions. We show that this new structure is particularly efficient for SFN environments regardless of the location of the receiver. It is then suitable for fixed, portable and mobile receptions.
Asymptotic stability region of slotted-Aloha
Venue: arXiv cs.IT 2008
Year: 2008

We analyze the stability of standard, buffered, slotted-Aloha systems. Specifically, we consider a set of $N$ users, each equipped with an infinite buffer. Packets arrive into user $i$'s buffer according to some stationary ergodic Markovian process of intensity $λ_i$. At the beginning of each slot, if user $i$ has packets in its buffer, it attempts to transmit a packet with fixed probability $p_i$ over a shared resource / channel. The transmission is successful only when no other user attempts to use the channel. The stability of such systems has been open since their very first analysis in 1979 by Tsybakov and Mikhailov. In this paper, we propose an approximate stability condition, that is provably exact when the number of users $N$ grows large. We provide theoretical evidence and numerical experiments to explain why the proposed approximate stability condition is extremely accurate even for systems with a restricted number of users (even two or three). We finally extend the results to the case of more efficient CSMA systems.
Analysis and Performance Comparison of DVB-T and DTMB Systems for Terrestrial Digital TV
Venue: arXiv cs.NI 2008
Year: 2008

Orthogonal frequency-division multiplexing (OFDM) is the most popular transmission technology in digital terrestrial broadcasting (DTTB), adopted by many DTTB standards. In this paper, the bit error rate (BER) performance of two DTTB systems, namely cyclic prefix OFDM (CP-OFDM) based DVB-T and time domain synchronous OFDM (TDS-OFDM) based DTMB, is evaluated in different channel conditions. Spectrum utilization and power efficiency are also discussed to demonstrate the transmission overhead of both systems. Simulation results show that the performances of the two systems are much close. Given the same ratio of guard interval (GI), the DVB-T outperforms DTMB in terms of signal to noise ratio (SNR) in Gaussian and Ricean channels, while DTMB behaves better performance in Rayleigh channel in higher code rates and higher orders of constellation thanks to its efficient channel coding and interleaving scheme.
Secrecy Capacity over Correlated Ergodic Fading Channel
Venue: arXiv cs.IT 2008
Year: 2008

We investigate the secrecy capacity of an ergodic fading wiretap channel in which the main channel is correlated with the eavesdropper channel. In this study, the full Channel State Information (CSI) is assumed, and thus the transmitter knows the channel gains of the legitimate receiver and the eavesdropper. By analyzing the resulting secrecy capacity we quantify the loss of the secrecy capacity due to the correlation. In addition, we study the asymptotic behavior of the secrecy capacity as Signal-to-Noise Ratio (SNR) tends to infinity. The capacity of an ordinary fading channel logarithmically increases with SNR. On the contrary, the secrecy capacity converges into a limit which can be an upper bound on the secrecy capacity over the fading wiretap channel. We find a closed form of the upper bound for the correlated Rayleigh wiretap channel which also includes the independent case as a special one. Our work shows that the upper bound is determined by only two channel parameters; the correlation coefficient and the ratio of the main to the eavesdropper channel gains that will be called PCC and CGR respectively. The analysis of the upper bound tells how the two channel parameters affect the secrecy capacity and leads to the conclusion that the excessively large signal power does not provide any advantage in the secrecy capacity, and the loss due to the correlation is especially serious in low CGR regime.