OpenRaiser/Intern-Atlas huggingface dataset:
Common Knowledge in Email Exchanges
Venue: arXiv cs.LO 2012
Year: 2012

We consider a framework in which a group of agents communicates by means of emails, with the possibility of replies, forwards and blind carbon copies (BCC). We study the epistemic consequences of such email exchanges by introducing an appropriate epistemic language and semantics. This allows us to find out what agents learn from the emails they receive and to determine when a group of agents acquires common knowledge of the fact that an email was sent. We also show that in our framework from the epistemic point of view the BCC feature of emails cannot be simulated using messages without BCC recipients.
Mitigation of Random Query String DoS via Gossip
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents a mitigation scheme to cope with the random query string Denial of Service (DoS) attack, which is based on a vulnerability of current Content Delivery Networks (CDNs). The attack exploits the fact that edge servers composing a CDN, receiving an HTTP request for a resource with an appended random query string never saw before, ask the origin server for a (novel) copy of the resource. Such characteristics can be employed to take an attack against the origin server by exploiting edge servers. Our strategy adopts a simple gossip protocol executed by edge servers to detect the attack. Based on such a detection, countermeasures can be taken to protect the origin server and the CDN against the attack. We provide simulation results that show the viability of our approach.
On the Diversity Order and Coding Gain of Multi-Source Multi-Relay Cooperative Wireless Networks with Binary Network Coding
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a multi-source multi-relay cooperative wireless network with binary modulation and binary network coding is studied. The system model encompasses: i) a demodulate-and-forward protocol at the relays, where the received packets are forwarded regardless of their reliability; and ii) a maximum-likelihood optimum demodulator at the destination, which accounts for possible demodulations errors at the relays. An asymptotically-tight and closed-form expression of the end-to-end error probability is derived, which clearly showcases diversity order and coding gain of each source. Unlike other papers available in the literature, the proposed framework has three main distinguishable features: i) it is useful for general network topologies and arbitrary binary encoding vectors; ii) it shows how network code and two-hop forwarding protocol affect diversity order and coding gain; and ii) it accounts for realistic fading channels and demodulation errors at the relays. The framework provides three main conclusions: i) each source achieves a diversity order equal to the separation vector of the network code; ii) the coding gain of each source decreases with the number of mixed packets at the relays; and iii) if the destination cannot take into account demodulation errors at the relays, it loses approximately half of the diversity order.
On the algebraic representation of selected optimal non-linear binary codes
Venue: arXiv cs.IT 2012
Year: 2012

Revisiting an approach by Conway and Sloane we investigate a collection of optimal non-linear binary codes and represent them as (non-linear) codes over Z4. The Fourier transform will be used in order to analyze these codes, which leads to a new algebraic representation involving subgroups of the group of units in a certain ring. One of our results is a new representation of Best's (10, 40, 4) code as a coset of a subgroup in the group of invertible elements of the group ring Z4[Z5]. This yields a particularly simple algebraic decoding algorithm for this code. The technique at hand is further applied to analyze Julin's (12, 144, 4) code and the (12, 24, 12) Hadamard code. It can also be used in order to construct a (non-optimal) binary (14, 56, 6) code.
Degrees of Freedom Region of the MIMO Interference Channel with Output Feedback and Delayed CSIT
Venue: arXiv cs.IT 2012
Year: 2012

The two-user multiple-input multiple-output (MIMO) interference channel (IC) with arbitrary number of antennas at each terminal is considered and the degrees of freedom (DoF) region is characterized in the presence of noiseless channel output feedback from each receiver to its respective transmitter and availability of delayed channel state information at the transmitters (CSIT). It is shown that having output feedback and delayed CSIT can strictly enlarge the DoF region of the MIMO IC when compared to the case in which only delayed CSIT is present. The proposed coding schemes that achieve the corresponding DoF region with feedback and delayed CSIT utilize both resources, i.e., feedback and delayed CSIT in a non-trivial manner. It is also shown that the DoF region with local feedback and delayed CSIT is equal to the DoF region with global feedback and delayed CSIT, i.e., local feedback and delayed CSIT is equivalent to global feedback and delayed CSIT from the perspective of the degrees of freedom region. The converse is proved for a stronger setting in which the channels to the two receivers need not be statistically equivalent.
A General Framework for the Optimization of Energy Harvesting Communication Systems with Battery Imperfections
Venue: arXiv cs.IT 2012
Year: 2012

Energy harvesting has emerged as a powerful technology for complementing current battery-powered communication systems in order to extend their lifetime. In this paper a general framework is introduced for the optimization of communication systems in which the transmitter is able to harvest energy from its environment. Assuming that the energy arrival process is known non-causally at the transmitter, the structure of the optimal transmission scheme, which maximizes the amount of transmitted data by a given deadline, is identified. Our framework includes models with continuous energy arrival as well as battery constraints. A battery that suffers from energy leakage is studied further, and the optimal transmission scheme is characterized for a constant leakage rate.
Exact Performance Analysis of Partial Relay Selection Based on Shadowing Side Information over Generalized Composite Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

Relay technology has recently gained great interest in millimeter wave (60 GHz or above) radio frequencies as a promising transmission technique improving the quality of service, providing high data rate, and extending the coverage area without additional transmit power in deeply shadowed fading environments. The performance of relay-based systems considerably depends on which relay selection protocols (RSPs) are used. These RSPs are typically using the channel side information (CSI). Specifically, the relay terminal (RT) is chosen among all available RTs by a central entity (CE) which receives all RTs' CSI via feedback channels. However, in the millimeter wave radio frequencies, the rate of the CSI variation is much higher than that of the CSI variation in 6 GHz frequencies under the same mobility conditions, which evidently results in a serious problem causing that the CSI at the CE is inaccurate for the RSP since the feedback channels have a backhaul / transmission delay. However and fortunately, the shadowing side information (SSI) varies very slowly in comparison to the rate of the CSI variation. In this context, we propose in this paper a partial-RSP in dual-hop amplify-and-forward relaying system, which utilize only the SSI of the RTs instead of their CSI. Then for the performance analysis, we obtain an exact average unified performance (AUP) of the proposed SSI-based partial-RSP for a variety shadowed fading environments. In particular, we offer a generic AUP expression whose special cases include the average bit error probability (ABEP) analysis for binary modulation schemes, the ergodic capacity analysis and the moments-generating function (MGF)-based characterization. The correctness of our newly theoretical results is validated with some selected numerical examples in an extended generalized-K fading environment.
Learning to relate images: Mapping units, complex cells and simultaneous eigenspaces
Venue: arXiv cs.CV 2012
Year: 2012

A fundamental operation in many vision tasks, including motion understanding, stereopsis, visual odometry, or invariant recognition, is establishing correspondences between images or between images and data from other modalities. We present an analysis of the role that multiplicative interactions play in learning such correspondences, and we show how learning and inferring relationships between images can be viewed as detecting rotations in the eigenspaces shared among a set of orthogonal matrices. We review a variety of recent multiplicative sparse coding methods in light of this observation. We also review how the squaring operation performed by energy models and by models of complex cells can be thought of as a way to implement multiplicative interactions. This suggests that the main utility of including complex cells in computational models of vision may be that they can encode relations not invariances.
Self-Adjusting Networks to Minimize Expected Path Length
Venue: arXiv cs.NI 2012
Year: 2012

Given a network infrastructure (e.g., data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measure for the performance, efficiency and power consumption of the network. In this work we initiate a study on self-adjusting networks: networks that use local-distributed mechanisms to adjust the position of the nodes (e.g., virtual machines) in the network to best fit the route requests distribution. Finding the optimal placement of nodes is defined as the minimum expected path length (MEPL) problem. This is a generalization of the minimum linear arrangement (MLA) problem where the network infrastructure is a line and the computation is done centrally. In contrast to previous work, we study the distributed version and give efficient and simple approximation algorithms for interesting and practically relevant special cases of the problem. In particular, we consider grid networks in which the distribution of requests is a symmetric product distribution. In this setting, we show that a simple greedy policy of position switching between neighboring nodes to locally minimize an objective function, achieves good approximation ratios. We are able to prove this result using the useful notions of expected rank of the distribution and the expected distance to the center of the graph.
LSM is not generated by binary functions
Venue: arXiv cs.CC 2012
Year: 2012

The material in this note is now superseded by arXiv:1108.5288v4. Bulatov et al. [1] defined the operation of (efficient) pps_ω-definability in order to study the computational complexity of certain approximate counting problems. They asked whether all log-supermodular functions can be defined by binary implication and unary functions in this sense. We give a negative answer to this question.
CinemaGazer: a System for Watching Video at Very High Speed
Venue: arXiv cs.HC 2012
Year: 2012

This paper presents a technology that enables the watching of videos at very high speed. Subtitles are widely used in DVD movies, and provide useful supplemental information for understanding video contents. We propose a "two-level fast-forwarding" scheme for videos with subtitles, which controls the speed of playback depending on the context: very fast during segments without language, such as subtitles or speech, and "understandably fast" during segments with such language. This makes it possible to watch videos at a higher speed than usual while preserving the entertainment values of the contents. We also propose "centering" and "fading" features for the display of subtitles to reduce fatigue when watching high-speed video. We implement a versatile video encoder that enables movie viewing with two-level fast-forwarding on any mobile device by specifying the speed of playback, the reading rate, or the overall viewing time. The effectiveness of our proposed method was demonstrated in an evaluation study.
Two-Variable Logic with Two Order Relations
Venue: arXiv cs.LO 2012
Year: 2012

It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relation and some further unary relations is EXPSPACE-complete. Actually, EXPSPACE-completeness already holds for structures that do not include the induced successor relation. As a special case, the EXPSPACE upper bound applies to two-variable logic over structures with two linear orders. A further consequence is that satisfiability of two-variable logic over data words with a linear order on positions and a linear order and successor relation on the data is decidable in EXPSPACE. As a complementing result, it is shown that over structures with two total preorder relations as well as over structures with one total preorder and two linear order relations, the finite satisfiability problem for two-variable logic is undecidable.
Optimisation of hybrid high-modulus/high-strength carbon fiber reinforced plastic composite drive
Venue: arXiv cs.CE 2012
Year: 2012

This study deals with the optimisation of hybrid composite drive shafts operating at subcritical or supercritical speeds, using a genetic algorithm. A formulation for the flexural vibrations of a composite drive shaft mounted on viscoelastic supports including shear effects is developed. In particular, an analytic stability criterion is developed to ensure the integrity of the system in the supercritical regime. Then it is shown that the torsional strength can be computed with the maximum stress criterion. A shell method is developed for computing drive shaft torsional buckling. The optimisation of a helicopter tail rotor driveline is then performed. In particular, original hybrid shafts consisting of high-modulus and high-strength carbon fibre reinforced epoxy plies were studied. The solutions obtained using the method presented here made it possible to greatly decrease the number of shafts and the weight of the driveline under subcritical conditions, and even more under supercritical conditions. This study yielded some general rules for designing an optimum composite shaft without any need for optimisation algorithms.
Jellyfish: Networking Data Centers Randomly
Venue: arXiv cs.NI 2012
Year: 2012

Industry experience indicates that the ability to incrementally expand data centers is essential. However, existing high-bandwidth network designs have rigid structure that interferes with incremental expansion. We present Jellyfish, a high-capacity network interconnect, which, by adopting a random graph topology, yields itself naturally to incremental expansion. Somewhat surprisingly, Jellyfish is more cost-efficient than a fat-tree: A Jellyfish interconnect built using the same equipment as a fat-tree, supports as many as 25% more servers at full capacity at the scale of a few thousand nodes, and this advantage improves with scale. Jellyfish also allows great flexibility in building networks with different degrees of oversubscription. However, Jellyfish's unstructured design brings new challenges in routing, physical layout, and wiring. We describe and evaluate approaches that resolve these challenges effectively, indicating that Jellyfish could be deployed in today's data centers.
Data formats for phonological corpora
Venue: arXiv cs.CL 2012
Year: 2012

The goal of the present chapter is to explore the possibility of providing the research (but also the industrial) community that commonly uses spoken corpora with a stable portfolio of well-documented standardised formats that allow a high re-use rate of annotated spoken resources and, as a consequence, better interoperability across tools used to produce or exploit such resources.
World Shares of Publications of the USA, EU-27, and China Compared and Predicted using the New Interface of the Web-of-Science versus Scopus
Venue: arXiv cs.DL 2012
Year: 2012

The new interface of the Web of Science (of Thomson Reuters) enables users to retrieve sets larger than 100,000 documents in a single search. This makes it possible to compare publication trends for China, the USA, EU-27, and a number of smaller countries. China no longer grew exponentially during the 2000s, but linearly. Contrary to previous predictions on the basis of exponential growth or Scopus data, the cross-over of the lines for China and the USA is postponed to the next decade (after 2020) according to this data. These long extrapolations, however, should be used only as indicators and not as predictions. Along with the dynamics in the publication trends, one also has to take into account the dynamics of the databases used for the measurement.
Beyond Traditional DTN Routing: Social Networks for Opportunistic Communication
Venue: arXiv cs.NI 2012
Year: 2012

This article examines the evolution of routing protocols for intermittently connected ad hoc networks and discusses the trend toward social-based routing protocols. A survey of current routing solutions is presented, where routing protocols for opportunistic networks are classified based on the network graph employed. The need to capture performance tradeoffs from a multi-objective perspective is highlighted.
Security of a biometric identity-based encryption scheme
Venue: arXiv cs.CR 2012
Year: 2012

Biometric identity-based encryption (Bio-IBE) is a kind of fuzzy identity-based encryption (fuzzy IBE) where a ciphertext encrypted under an identity w' can be decrypted using a secret key corresponding to the identity w which is close to w' as measured by some metric. Recently, Yang et al. proposed a constant-size Bio-IBE scheme and proved that it is secure against adaptive chosen-ciphertext attack (CCA2) in the random oracle model. Unfortunately, in this paper, we will show that their Bio-IBE scheme is even not chosen-plaintext secure. Specifically, user w using his secret key is able to decrypt any ciphertext encrypted under an identity w' even though w is not close to w'.
Robust Beamforming in Interference Channels with Imperfect Transmitter Channel Information
Venue: arXiv cs.IT 2012
Year: 2012

We consider $K$ links operating concurrently in the same spectral band. Each transmitter has multiple antennas, while each receiver uses a single antenna. This setting corresponds to the multiple-input single-output interference channel. We assume perfect channel state information at the single-user decoding receivers whereas the transmitters only have estimates of the true channels. The channel estimation errors are assumed to be bounded in elliptical regions whose geometry is known at the transmitters. Robust beamforming optimizes worst-case received power gains, and a Pareto optimal point is a worst-case achievable rate tuple from which it is impossible to increase a link's performance without degrading the performance of another. We characterize the robust beamforming vectors necessary to operate at any Pareto optimal point. Moreover, these beamforming vectors are parameterized by $K(K-1)$ real-valued parameters. We analyze the system's spectral efficiency at high and low signal-to-noise ratio (SNR). Zero forcing transmission achieves full multiplexing gain at high SNR only if the estimation errors scale linearly with inverse SNR. If the errors are SNR independent, then single-user transmission is optimal at high SNR. At low SNR, robust maximum ratio transmission optimizes the minimum energy per bit for reliable communication. Numerical simulations illustrate the gained theoretical results.
Positive words carry less information than negative words
Venue: arXiv cs.CL 2012
Year: 2012

We show that the frequency of word use is not only determined by the word length \cite{Zipf1935} and the average information content \cite{Piantadosi2011}, but also by its emotional content. We have analyzed three established lexica of affective word usage in English, German, and Spanish, to verify that these lexica have a neutral, unbiased, emotional content. Taking into account the frequency of word usage, we find that words with a positive emotional content are more frequently used. This lends support to Pollyanna hypothesis \cite{Boucher1969} that there should be a positive bias in human expression. We also find that negative words contain more information than positive words, as the informativeness of a word increases uniformly with its valence decrease. Our findings support earlier conjectures about (i) the relation between word frequency and information content, and (ii) the impact of positive emotions on communication and social links.
Demodulating Subsampled Direct Sequence Spread Spectrum Signals using Compressive Signal Processing
Venue: arXiv cs.IT 2012
Year: 2012

We show that to lower the sampling rate in a spread spectrum communication system using Direct Sequence Spread Spectrum (DSSS), compressive signal processing can be applied to demodulate the received signal. This may lead to a decrease in the power consumption or the manufacturing price of wireless receivers using spread spectrum technology. The main novelty of this paper is the discovery that in spread spectrum systems it is possible to apply compressive sensing with a much simpler hardware architecture than in other systems, making the implementation both simpler and more energy efficient. Our theoretical work is exemplified with a numerical experiment using the IEEE 802.15.4 standard's 2.4 GHz band specification. The numerical results support our theoretical findings and indicate that compressive sensing may be used successfully in spread spectrum communication systems. The results obtained here may also be applicable in other spread spectrum technologies, such as Code Division Multiple Access (CDMA) systems.
String Indexing for Patterns with Wildcards
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of indexing a string $t$ of length $n$ to report the occurrences of a query pattern $p$ containing $m$ characters and $j$ wildcards. Let $occ$ be the number of occurrences of $p$ in $t$, and $σ$ the size of the alphabet. We obtain the following results. - A linear space index with query time $O(m+σ^j \log \log n + occ)$. This significantly improves the previously best known linear space index by Lam et al. [ISAAC 2007], which requires query time $Θ(jn)$ in the worst case. - An index with query time $O(m+j+occ)$ using space $O(σ^{k^2} n \log^k \log n)$, where $k$ is the maximum number of wildcards allowed in the pattern. This is the first non-trivial bound with this query time. - A time-space trade-off, generalizing the index by Cole et al. [STOC 2004]. We also show that these indexes can be generalized to allow variable length gaps in the pattern. Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.
LINPRO: linear inverse problem library for data contaminated by statistical noise
Venue: arXiv cs.MS 2012
Year: 2012

The library LINPRO which provides solution to the linear inverse problem for data contaminated by a statistical noise is presented. The library makes use of two methods: Maximum Entropy Method and Singular Value Decomposition. As an example it has been applied to perform an analytic continuation of the imaginary time propagator obtained within the Quantum Monte Carlo method.