OpenRaiser/Intern-Atlas huggingface dataset:
A new sufficient condition for sum-rate tightness in quadratic Gaussian multiterminal source coding
Venue: arXiv cs.IT 2010
Year: 2010

This work considers the quadratic Gaussian multiterminal (MT) source coding problem and provides a new sufficient condition for the Berger-Tung sum-rate bound to be tight. The converse proof utilizes a set of virtual remote sources given which the MT sources are block independent with a maximum block size of two. The given MT source coding problem is then related to a set of two-terminal problems with matrix-distortion constraints, for which a new lower bound on the sum-rate is given. Finally, a convex optimization problem is formulated and a sufficient condition derived for the optimal BT scheme to satisfy the subgradient based Karush-Kuhn-Tucker condition. The set of sum-rate tightness problems defined by our new sufficient condition subsumes all previously known tight cases, and opens new direction for a more general partial solution.
Consistent digital line segments
Venue: arXiv cs.DM 2010
Year: 2010

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of Chun et al.
MiBoard: Multiplayer Interactive Board Game
Venue: arXiv cs.CY 2010
Year: 2010

Serious games have recently emerged as an avenue for curriculum delivery. Serious games incorporate motivation and entertainment while providing pointed curriculum for the user. This paper presents a serious game, called MiBoard, currently being developed from the iSTART Intelligent Tutoring System. MiBoard incorporates a multiplayer interaction that iSTART was previously unable to provide. This multiplayer interaction produces a wide variation across game trials, while also increasing the repeat playability for users. This paper presents a demonstration of the MiBoard system and the expectations for its application.
Robust Beamforming for Security in MIMO Wiretap Channels with Imperfect CSI
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we investigate methods for reducing the likelihood that a message transmitted between two multiantenna nodes is intercepted by an undetected eavesdropper. In particular, we focus on the judicious transmission of artificial interference to mask the desired signal at the time it is broadcast. Unlike previous work that assumes some prior knowledge of the eavesdropper's channel and focuses on maximizing secrecy capacity, we consider the case where no information regarding the eavesdropper is available, and we use signal-to-interference-plus-noise-ratio (SINR) as our performance metric. Specifically, we focus on the problem of maximizing the amount of power available to broadcast a jamming signal intended to hide the desired signal from a potential eavesdropper, while maintaining a prespecified SINR at the desired receiver. The jamming signal is designed to be orthogonal to the information signal when it reaches the desired receiver, assuming both the receiver and the eavesdropper employ optimal beamformers and possess exact channel state information (CSI). In practice, the assumption of perfect CSI at the transmitter is often difficult to justify. Therefore, we also study the resulting performance degradation due to the presence of imperfect CSI, and we present robust beamforming schemes that recover a large fraction of the performance in the perfect CSI case. Numerical simulations verify our analytical performance predictions, and illustrate the benefit of the robust beamforming schemes.
PhishDef: URL Names Say It All
Venue: arXiv cs.CR 2010
Year: 2010

Phishing is an increasingly sophisticated method to steal personal user information using sites that pretend to be legitimate. In this paper, we take the following steps to identify phishing URLs. First, we carefully select lexical features of the URLs that are resistant to obfuscation techniques used by attackers. Second, we evaluate the classification accuracy when using only lexical features, both automatically and hand-selected, vs. when using additional features. We show that lexical features are sufficient for all practical purposes. Third, we thoroughly compare several classification algorithms, and we propose to use an online method (AROW) that is able to overcome noisy training data. Based on the insights gained from our analysis, we propose PhishDef, a phishing detection system that uses only URL names and combines the above three elements. PhishDef is a highly accurate method (when compared to state-of-the-art approaches over real datasets), lightweight (thus appropriate for online and client-side deployment), proactive (based on online classification rather than blacklists), and resilient to training data inaccuracies (thus enabling the use of large noisy training data).
The Exponential Time Complexity of Computing the Probability That a Graph is Connected
Venue: arXiv cs.CC 2010
Year: 2010

We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in Omega(m/ log^2 m) for simple graphs of m edges under the Exponential Time Hypothesis.
Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems
Venue: arXiv cs.DS 2010
Year: 2010

We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients and also need to be sequentially activated before they can provide service. Formally, we are given a set \F of n facilities with facility-opening costs {f_i}, a set of m clients, and connection costs {c_{ij}} specifying the cost of assigning a client j to a facility i, a root node r denoting the depot, and a time metric d on \F\cup{r}. Our goal is to open a subset F of facilities, find a path P starting at r and spanning F to activate the open facilities, and connect each client j to a facility ϕ(j)\in F, so as to minimize \sum_{i\in F}f_i +\sum_{clients j}(c_{ϕ(j),j}+t_j), where t_j is the time taken to reach ϕ(j) along path P. We call this the minimum latency uncapacitated facility location (MLUFL) problem. Our main result is an O(\log n\max{\log n,\log m})-approximation for MLUFL. We also show that any improvement in this approximation guarantee, implies an improvement in the (current-best) approximation factor for group Steiner tree. We obtain constant approximations for two natural special cases of the problem: (a) related MLUFL (metric connection costs that are a scalar multiple of the time metric); (b) metric uniform MLUFL (metric connection costs, unform time-metric). Our LP-based methods are versatile and easily adapted to yield approximation guarantees for MLUFL in various more general settings, such as (i) when the latency-cost of a client is a function of the delay faced by the facility to which it is connected; and (ii) the k-route version, where k vehicles are routed in parallel to activate the open facilities. Our LP-based understanding of MLUFL also offers some LP-based insights into ML, which we believe is a promising direction for obtaining improvements for ML.
Reinforcement Learning by Comparing Immediate Reward
Venue: arXiv cs.LG 2010
Year: 2010

This paper introduces an approach to Reinforcement Learning Algorithm by comparing their immediate rewards using a variation of Q-Learning algorithm. Unlike the conventional Q-Learning, the proposed algorithm compares current reward with immediate reward of past move and work accordingly. Relative reward based Q-learning is an approach towards interactive learning. Q-Learning is a model free reinforcement learning method that used to learn the agents. It is observed that under normal circumstances algorithm take more episodes to reach optimal Q-value due to its normal reward or sometime negative reward. In this new form of algorithm agents select only those actions which have a higher immediate reward signal in comparison to previous one. The contribution of this article is the presentation of new Q-Learning Algorithm in order to maximize the performance of algorithm and reduce the number of episode required to reach optimal Q-value. Effectiveness of proposed algorithm is simulated in a 20 x20 Grid world deterministic environment and the result for the two forms of Q-Learning Algorithms is given.
Google matrix of business process management
Venue: arXiv cs.CY 2010
Year: 2010

Development of efficient business process models and determination of their characteristic properties are subject of intense interdisciplinary research. Here, we consider a business process model as a directed graph. Its nodes correspond to the units identified by the modeler and the link direction indicates the causal dependencies between units. It is of primary interest to obtain the stationary flow on such a directed graph, which corresponds to the steady-state of a firm during the business process. Following the ideas developed recently for the World Wide Web, we construct the Google matrix for our business process model and analyze its spectral properties. The importance of nodes is characterized by Page-Rank and recently proposed CheiRank and 2DRank, respectively. The results show that this two-dimensional ranking gives a significant information about the influence and communication properties of business model units. We argue that the Google matrix method, described here, provides a new efficient tool helping companies to make their decisions on how to evolve in the exceedingly dynamic global market.
Explicit Substitutions for Contextual Type Theory
Venue: arXiv cs.LO 2010
Year: 2010

In this paper, we present an explicit substitution calculus which distinguishes between ordinary bound variables and meta-variables. Its typing discipline is derived from contextual modal type theory. We first present a dependently typed lambda calculus with explicit substitutions for ordinary variables and explicit meta-substitutions for meta-variables. We then present a weak head normalization procedure which performs both substitutions lazily and in a single pass thereby combining substitution walks for the two different classes of variables. Finally, we describe a bidirectional type checking algorithm which uses weak head normalization and prove soundness.
Pure Type Systems without Explicit Contexts
Venue: arXiv cs.LO 2010
Year: 2010

We present an approach to type theory in which the typing judgments do not have explicit contexts. Instead of judgments of shape "Gamma |- A : B", our systems just have judgments of shape "A : B". A key feature is that we distinguish free and bound variables even in pseudo-terms. Specifically we give the rules of the "Pure Type System" class of type theories in this style. We prove that the typing judgments of these systems correspond in a natural way with those of Pure Type Systems as traditionally formulated. I.e., our systems have exactly the same well-typed terms as traditional presentations of type theory. Our system can be seen as a type theory in which all type judgments share an identical, infinite, typing context that has infinitely many variables for each possible type. For this reason we call our system "Gamma_infinity". This name means to suggest that our type judgment "A : B" should be read as "Gamma_infinity |- A : B", with a fixed infinite type context called "Gamma_infinity".
Underlay Cognitive Radio with Full or Partial Channel Quality Information
Venue: arXiv cs.IT 2010
Year: 2010

Underlay cognitive radios (UCRs) allow a secondary user to enter a primary user's spectrum through intelligent utilization of multiuser channel quality information (CQI) and sharing of codebook. The aim of this work is to study two-user Gaussian UCR systems by assuming the full or partial knowledge of multiuser CQI. Key contribution of this work is motivated by the fact that the full knowledge of multiuser CQI is not always available. We first establish a location-aided UCR model where the secondary user is assumed to have partial CQI about the secondary-transmitter to primary-receiver link as well as full CQI about the other links. Then, new UCR approaches are proposed and carefully analyzed in terms of the secondary user's achievable rate, denoted by $C_2$, the capacity penalty to primary user, denoted by $ΔC_1$, and capacity outage probability. Numerical examples are provided to visually compare the performance of UCRs with full knowledge of multiuser CQI and the proposed approaches with partial knowledge of multiuser CQI.
Secret-key Agreement with Channel State Information at the Transmitter
Venue: arXiv cs.IT 2010
Year: 2010

We study the capacity of secret-key agreement over a wiretap channel with state parameters. The transmitter communicates to the legitimate receiver and the eavesdropper over a discrete memoryless wiretap channel with a memoryless state sequence. The transmitter and the legitimate receiver generate a shared secret key, that remains secret from the eavesdropper. No public discussion channel is available. The state sequence is known noncausally to the transmitter. We derive lower and upper bounds on the secret-key capacity. The lower bound involves constructing a common state reconstruction sequence at the legitimate terminals and binning the set of reconstruction sequences to obtain the secret-key. For the special case of Gaussian channels with additive interference (secret-keys from dirty paper channel) our bounds differ by 0.5 bit/symbol and coincide in the high signal-to-noise-ratio and high interference-to-noise-ratio regimes. For the case when the legitimate receiver is also revealed the state sequence, we establish that our lower bound achieves the the secret-key capacity. In addition, for this special case, we also propose another scheme that attains the capacity and requires only causal side information at the transmitter and the receiver.
The Capacity of the Semi-Deterministic Cognitive Interference Channel and its Application to Constant Gap Results for the Gaussian Channel
Venue: arXiv cs.IT 2010
Year: 2010

The cognitive interference channel (C-IFC) consists of a classical two-user interference channel in which the message of one user (the "primary" user) is non-causally available at the transmitter of the other user (the "cognitive" user). We obtain the capacity of the semi-deterministic C-IFC: a discrete memoryless C-IFC in which the cognitive receiver output is a noise-less deterministic function of the channel inputs. We then use the insights obtained from the capacity-achieving scheme for the semi-deterministic model to derive new, unified and tighter constant gap results for the complex-valued Gaussian C-IFC. We prove: (1) a constant additive gap (difference between inner and outer bounds) of half a bit/sec/Hz per real dimension, of relevance at high SNRs, and (b) a constant multiplicative gap (ratio between outer and inner bounds) of a factor two, of relevance at low SNRs
Open-Loop Spatial Multiplexing and Diversity Communications in Ad Hoc Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the performance of open-loop multi-antenna point-to-point links in ad hoc networks with slotted ALOHA medium access control (MAC). We consider spatial multiplexing transmission with linear maximum ratio combining and zero forcing receivers, as well as orthogonal space time block coded transmission. New closed-form expressions are derived for the outage probability, throughput and transmission capacity. Our results demonstrate that both the best performing scheme and the optimum number of transmit antennas depend on different network parameters, such as the node intensity and the signal-to-interference-and-noise ratio operating value. We then compare the performance to a network consisting of single-antenna devices and an idealized fully centrally coordinated MAC. These results show that multi-antenna schemes with a simple decentralized slotted ALOHA MAC can outperform even idealized single-antenna networks in various practical scenarios.
Fuzzy Ontology Representation using OWL 2
Venue: arXiv cs.LO 2010
Year: 2010

The need to deal with vague information in Semantic Web languages is rising in importance and, thus, calls for a standard way to represent such information. We may address this issue by either extending current Semantic Web languages to cope with vagueness, or by providing a procedure to represent such information within current standard languages and tools. In this work, we follow the latter approach, by identifying the syntactic differences that a fuzzy ontology language has to cope with, and by proposing a concrete methodology to represent fuzzy ontologies using OWL 2 annotation properties. We also report on the prototypical implementations.
Temporal Starvation in CSMA Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

It is well known that links in CSMA wireless networks are prone to starvation. Prior works focused almost exclusively on equilibrium starvation. In this paper, we show that links in CSMA wireless networks are also susceptible to temporal starvation. Specifically, although some links have good equilibrium throughputs and do not suffer from equilibrium starvation, they can still have no throughput for extended periods from time to time. Given its impact on quality of service, it is important to understand and characterize temporal starvation. To this end, we develop a "trap theory" to analyze temporal throughput fluctuation. The trap theory serves two functions. First, it allows us to derive new mathematical results that shed light on the transient behavior of CSMA networks. For example, we show that the duration of a trap, during which some links receive no throughput, is insensitive to the distributions of the backoff countdown and transmission time (packet duration) in the CSMA protocol. Second, we can develop analytical tools for computing the "degrees of starvation" for CSMA networks to aid network design. For example, given a CSMA network, we can determine whether it suffers from starvation, and if so, which links will starve. Furthermore, the likelihood and durations of temporal starvation can also be computed. We believe that the ability to identify and characterize temporal starvation as established in this paper will serve as an important first step toward the design of effective remedies for it.
Internal Location Based System for Mobile Devices Using Passive RFID
Venue: arXiv cs.NI 2010
Year: 2010

We have explored our own innovative work about the design & development of internal location-identification system for mobile devices based on integration of RFID and wireless technology. The function of our system is based on strategically located passive RFID tags placed on objects around building which are identified using an RFID reader attached to a mobile device. The mobile device reads the RFID tag and through the wireless network, sends the request to the server. The server resolves the request and sends the desired location-based information back to the mobile device. We had addressed that we can go through the RFID technology for internal location identification (indoor), which provides us better location accuracy because of no contact between the tag and the reader, and the system requires no line of sight. In this paper we had also focused on the issues of RFID technologies i.e. Non-line-of-sight & High inventory speeds.
Simultaneous Interval Graphs
Venue: arXiv cs.DS 2010
Year: 2010

In a recent paper, we introduced the simultaneous representation problem (defined for any graph class C) and studied the problem for chordal, comparability and permutation graphs. For interval graphs, the problem is defined as follows. Two interval graphs G_1 and G_2, sharing some vertices I (and the corresponding induced edges), are said to be `simultaneous interval graphs' if there exist interval representations R_1 and R_2 of G_1 and G_2, such that any vertex of I is mapped to the same interval in both R_1 and R_2. Equivalently, G_1 and G_2 are simultaneous interval graphs if there exist edges E' between G_1-I and G_2-I such that G_1 \cup G_2 \cup E' is an interval graph. Simultaneous representation problems are related to simultaneous planar embeddings, and have applications in any situation where it is desirable to consistently represent two related graphs, for example: interval graphs capturing overlaps of DNA fragments of two similar organisms; or graphs connected in time, where one is an updated version of the other. In this paper we give an O(n^2*logn) time algorithm for recognizing simultaneous interval graphs,where n = |G_1 \cup G_2|. This result complements the polynomial time algorithms for recognizing probe interval graphs and provides an efficient algorithm for the interval graph sandwich problem for the special case where the set of optional edges induce a complete bipartite graph.
Priority Range Trees
Venue: arXiv cs.CG 2010
Year: 2010

We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let $S$ be a set of $n$ points in the plane, where each point $p$ in $S$ is assigned a weight $w(p)$ that is polynomial in $n$, and define the rank of $p$ to be $r(p)=\lfloor \log w(p) \rfloor$. Then the priority range tree can be used to report all points in a three- or four-sided query range $R$ with rank at least $\lfloor \log w \rfloor$ in time $O(\log W/w + k)$, and report $k$ highest-rank points in $R$ in time $O(\log\log n + \log W/w' + k)$, where $W=\sum_{p\in S}{w(p)}$, $w'$ is the smallest weight of any point reported, and $k$ is the output size. All times assume the standard RAM model of computation. If the query range of interest is three sided, then the priority range tree occupies $O(n)$ space, otherwise $O(n\log n)$ space is used to answer four-sided queries. These queries are motivated by the Weber--Fechner Law, which states that humans perceive and interpret data on a logarithmic scale.
MIMO Identical Eigenmode Transmission System (IETS) - A Channel Decomposition Perspective
Venue: arXiv cs.IT 2010
Year: 2010

In the past few years considerable attention has been given to the design of Multiple-Input Multiple-Output (MIMO) Eigenmode Transmission Systems (EMTS). This paper presents an in-depth analysis of a new MIMO eigenmode transmission strategy. The non-linear decomposition technique called Geometric Mean Decomposition (GMD) is employed for the formation of eigenmodes over MIMO flatfading channel. Exploiting GMD technique, identical, parallel and independent transmission pipes are created for data transmission at higher rate. The system based on such decomposition technique is referred to as MIMO Identical Eigenmode Transmission System (IETS). The comparative analysis of the MIMO transceiver design exploiting nonlinear and linear decomposition techniques for variable constellation is presented in this paper. The new transmission strategy is tested in combination with the Vertical Bell Labs Layered Space Time (V-BLAST) decoding scheme using different number of antennas on both sides of the communication link. The analysis is supported by various simulation results.