OpenRaiser/Intern-Atlas huggingface dataset:
Alternating-Offer Bargaining Games over the Gaussian Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

This paper tackles the problem of how two selfish users jointly determine the operating point in the achievable rate region of a two-user Gaussian interference channel through bargaining. In previous work, incentive conditions for two users to cooperate using a simple version of Han-Kobayashi scheme was studied and the Nash bargaining solution (NBS) was used to obtain a fair operating point. Here a noncooperative bargaining game of alternating offers is adopted to model the bargaining process and rates resulting from the equilibrium outcome are analyzed. In particular, it is shown that the operating point resulting from the formulated bargaining game depends on the cost of delay in bargaining and how bargaining proceeds. If the associated bargaining problem is regular, a unique perfect equilibrium exists and lies on the individual rational efficient frontier of the achievable rate region. Besides, the equilibrium outcome approaches the NBS if the bargaining costs of both users are negligible.
Visual-hint Boundary to Segment Algorithm for Image Segmentation
Venue: arXiv cs.CV 2010
Year: 2010

Image segmentation has been a very active research topic in image analysis area. Currently, most of the image segmentation algorithms are designed based on the idea that images are partitioned into a set of regions preserving homogeneous intra-regions and inhomogeneous inter-regions. However, human visual intuition does not always follow this pattern. A new image segmentation method named Visual-Hint Boundary to Segment (VHBS) is introduced, which is more consistent with human perceptions. VHBS abides by two visual hint rules based on human perceptions: (i) the global scale boundaries tend to be the real boundaries of the objects; (ii) two adjacent regions with quite different colors or textures tend to result in the real boundaries between them. It has been demonstrated by experiments that, compared with traditional image segmentation method, VHBS has better performance and also preserves higher computational efficiency.
Transmission Capacity of Spectrum Sharing Ad-hoc Networks with Multiple Antennas
Venue: arXiv cs.IT 2010
Year: 2010

Two coexisting ad-hoc networks, primary and secondary, are considered, where each node of the primary network has a single antenna, while each node of the secondary network is equipped with multiple antennas. Using multiple antennas, each secondary transmitter uses some of its spatial transmit degrees of freedom (STDOF) to null its interference towards the primary receivers, while each secondary receiver employs interference cancelation using some of its spatial receive degrees of freedom (SRDOF). This paper derives the optimal STDOF for nulling and SRDOF for interference cancelation that maximize the scaling of the transmission capacity of the secondary network with respect to the number of antennas, when the secondary network operates under an outage constraint at the primary receivers. With a single receive antenna, using a fraction of the total STDOF for nulling at each secondary transmitter maximizes the transmission capacity. With multiple transmit and receive antennas and fixing all but one STDOF for nulling, using a fraction of the total SRDOF to cancel the nearest interferers maximizes the transmission capacity of the secondary network.
Engineering Time-dependent One-To-All Computation
Venue: arXiv cs.DS 2010
Year: 2010

Very recently a new algorithm to the nonnegative single-source shortest path problem on road networks has been discovered. It is very cache-efficient, but only on static road networks. We show how to augment it to the time-dependent scenario. The advantage if the new approach is that it settles nodes, even for a profile query, by scanning all downward edges. We improve the scanning of the downward edges with techniques developed for time-dependent many-to-many computations.
Hitting forbidden minors: Approximation and Kernelization
Venue: arXiv cs.DS 2010
Year: 2010

We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the F-deletion problem when F contains a planar graph. We give (1) a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer. (2) an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F contains graph $θ_c$ as a minor for a fixed integer $c$. The graph $θ_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.
An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
Venue: arXiv cs.MS 2010
Year: 2010

We present an exact and complete algorithm to isolate the real solutions of a zero-dimensional bivariate polynomial system. The proposed algorithm constitutes an elimination method which improves upon existing approaches in a number of points. First, the amount of purely symbolic operations is significantly reduced, that is, only resultant computation and square-free factorization is still needed. Second, our algorithm neither assumes generic position of the input system nor demands for any change of the coordinate system. The latter is due to a novel inclusion predicate to certify that a certain region is isolating for a solution. Our implementation exploits graphics hardware to expedite the resultant computation. Furthermore, we integrate a number of filtering techniques to improve the overall performance. Efficiency of the proposed method is proven by a comparison of our implementation with two state-of-the-art implementations, that is, LPG and Maple's isolate. For a series of challenging benchmark instances, experiments show that our implementation outperforms both contestants.
Profile Based Sub-Image Search in Image Databases
Venue: arXiv cs.CV 2010
Year: 2010

Sub-image search with high accuracy in natural images still remains a challenging problem. This paper proposes a new feature vector called profile for a keypoint in a bag of visual words model of an image. The profile of a keypoint captures the spatial geometry of all the other keypoints in an image with respect to itself, and is very effective in discriminating true matches from false matches. Sub-image search using profiles is a single-phase process requiring no geometric validation, yields high precision on natural images, and works well on small visual codebook. The proposed search technique differs from traditional methods that first generate a set of candidates disregarding spatial information and then verify them geometrically. Conventional methods also use large codebooks. We achieve a precision of 81% on a combined data set of synthetic and real natural images using a codebook size of 500 for top-10 queries; that is 31% higher than the conventional candidate generation approach.
Certifying cost annotations in compilers
Venue: arXiv cs.PL 2010
Year: 2010

We discuss the problem of building a compiler which can lift in a provably correct way pieces of information on the execution cost of the object code to cost annotations on the source code. To this end, we need a clear and flexible picture of: (i) the meaning of cost annotations, (ii) the method to prove them sound and precise, and (iii) the way such proofs can be composed. We propose a so-called labelling approach to these three questions. As a first step, we examine its application to a toy compiler. This formal study suggests that the labelling approach has good compositionality and scalability properties. In order to provide further evidence for this claim, we report our successful experience in implementing and testing the labelling approach on top of a prototype compiler written in OCAML for (a large fragment of) the C language.
Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis
Venue: arXiv cs.LO 2010
Year: 2010

The safety of infinite state systems can be checked by a backward reachability procedure. For certain classes of systems, it is possible to prove the termination of the procedure and hence conclude the decidability of the safety problem. Although backward reachability is property-directed, it can unnecessarily explore (large) portions of the state space of a system which are not required to verify the safety property under consideration. To avoid this, invariants can be used to dramatically prune the search space. Indeed, the problem is to guess such appropriate invariants. In this paper, we present a fully declarative and symbolic approach to the mechanization of backward reachability of infinite state systems manipulating arrays by Satisfiability Modulo Theories solving. Theories are used to specify the topology and the data manipulated by the system. We identify sufficient conditions on the theories to ensure the termination of backward reachability and we show the completeness of a method for invariant synthesis (obtained as the dual of backward reachability), again, under suitable hypotheses on the theories. We also present a pragmatic approach to interleave invariant synthesis and backward reachability so that a fix-point for the set of backward reachable states is more easily obtained. Finally, we discuss heuristics that allow us to derive an implementation of the techniques in the model checker MCMT, showing remarkable speed-ups on a significant set of safety problems extracted from a variety of sources.
The Failure Probability at Sink Node of Random Linear Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

In practice, since many communication networks are huge in scale or complicated in structure even dynamic, the predesigned network codes based on the network topology is impossible even if the topological structure is known. Therefore, random linear network coding was proposed as an acceptable coding technique. In this paper, we further study the performance of random linear network coding by analyzing the failure probabilities at sink node for different knowledge of network topology and get some tight and asymptotically tight upper bounds of the failure probabilities. In particular, the worst cases are indicated for these bounds. Furthermore, if the more information about the network topology is utilized, the better upper bounds are obtained. These bounds improve on the known ones. Finally, we also discuss the lower bound of this failure probability and show that it is also asymptotically tight.
New Frontiers of Network Security: The Threat Within
Venue: arXiv cs.CR 2010
Year: 2010

Nearly 70% of information security threats originate from inside an organization. Opportunities for insider threats have been increasing at an alarming rate with the latest trends of mobility (portable devices like Laptop, smart phones etc.), ubiquitous connectivity (wireless or through 3G connectivity) and this trend increases as more and more web-based applications are made available over the Internet. Insider threats are generally caused by current or ex-employees, contractors or partners, who have authorized access to the organization's network and servers. Theft of confidential information is often for either material gain or for willful damage. Easy availability of hacking tools on the Internet, USB devices and wireless connectivity provide for easy break-ins. The net result is losses worth millions of dollars in terms of IP theft, leakage of customer / individual information, etc. This paper presents an understanding of Insider threats, attackers and their motives and suggests mitigation techniques at the organization level
Parameter Selection in Periodic Nonuniform Sampling of Multiband Signals
Venue: arXiv cs.SY 2010
Year: 2010

Periodic nonuniform sampling has been considered in literature as an effective approach to reduce the sampling rate far below the Nyquist rate for sparse spectrum multiband signals. In the presence of non-ideality the sampling parameters play an important role on the quality of reconstructed signal. Also the average sampling ratio is directly dependent on the sampling parameters that they should be chosen for a minimum rate and complexity. In this paper we consider the effect of sampling parameters on the reconstruction error and the sampling ratio and suggest feasible approaches for achieving an optimal sampling and reconstruction.
Non-uniform sampling and reconstruction of multi-band signals and its application in wideband spectrum sensing of cognitive radio
Venue: arXiv cs.IT 2010
Year: 2010

Sampling theories lie at the heart of signal processing devices and communication systems. To accommodate high operating rates while retaining low computational cost, efficient analog-to digital (ADC) converters must be developed. Many of limitations encountered in current converters are due to a traditional assumption that the sampling state needs to acquire the data at the Nyquist rate, corresponding to twice the signal bandwidth. In this thesis a method of sampling far below the Nyquist rate for sparse spectrum multiband signals is investigated. The method is called periodic non-uniform sampling, and it is useful in a variety of applications such as data converters, sensor array imaging and image compression. Firstly, a model for the sampling system in the frequency domain is prepared. It relates the Fourier transform of observed compressed samples with the unknown spectrum of the signal. Next, the reconstruction process based on the topic of compressed sensing is provided. We show that the sampling parameters play an important role on the average sample ratio and the quality of the reconstructed signal. The concept of condition number and its effect on the reconstructed signal in the presence of noise is introduced, and a feasible approach for choosing a sample pattern with a low condition number is given. We distinguish between the cases of known spectrum and unknown spectrum signals respectively. One of the model parameters is determined by the signal band locations that in case of unknown spectrum signals should be estimated from sampled data. Therefore, we applied both subspace methods and non-linear least square methods for estimation of this parameter. We also used the information theoretic criteria (Akaike and MDL) and the exponential fitting test techniques for model order selection in this case.
Divergence-based characterization of fundamental limitations of adaptive dynamical systems
Venue: arXiv cs.IT 2010
Year: 2010

Adaptive dynamical systems arise in a multitude of contexts, e.g., optimization, control, communications, signal processing, and machine learning. A precise characterization of their fundamental limitations is therefore of paramount importance. In this paper, we consider the general problem of adaptively controlling and/or identifying a stochastic dynamical system, where our {\em a priori} knowledge allows us to place the system in a subset of a metric space (the uncertainty set). We present an information-theoretic meta-theorem that captures the trade-off between the metric complexity (or richness) of the uncertainty set, the amount of information acquired online in the process of controlling and observing the system, and the residual uncertainty remaining after the observations have been collected. Following the approach of Zames, we quantify {\em a priori} information by the Kolmogorov (metric) entropy of the uncertainty set, while the information acquired online is expressed as a sum of information divergences. The general theory is used to derive new minimax lower bounds on the metric identification error, as well as to give a simple derivation of the minimum time needed to stabilize an uncertain stochastic linear system.
Abstraction for Epistemic Model Checking of Dining Cryptographers-based Protocols
Venue: arXiv cs.LO 2010
Year: 2010

The paper describes an abstraction for protocols that are based on multiple rounds of Chaum's Dining Cryptographers protocol. It is proved that the abstraction preserves a rich class of specifications in the logic of knowledge, including specifications describing what an agent knows about other agents' knowledge. This result can be used to optimize model checking of Dining Cryptographers-based protocols, and applied within a methodology for knowledge-based program implementation and verification. Some case studies of such an application are given, for a protocol that uses the Dining Cryptographers protocol as a primitive in an anonymous broadcast system. Performance results are given for model checking knowledge-based specifications in the concrete and abstract models of this protocol, and some new conclusions about the protocol are derived.
Predicting Coding Effort in Projects Containing XML Code
Venue: arXiv cs.SE 2010
Year: 2010

This paper studies the problem of predicting the coding effort for a subsequent year of development by analysing metrics extracted from project repositories, with an emphasis on projects containing XML code. The study considers thirteen open source projects and applies machine learning algorithms to generate models to predict one-year coding effort, measured in terms of lines of code added, modified and deleted. Both organisational and code metrics associated to revisions are taken into account. The results show that coding effort is highly determined by the expertise of developers while source code metrics have little effect on improving the accuracy of estimations of coding effort. The study also shows that models trained on one project are unreliable at estimating effort in other projects.
Transmitting Video-on-Demand Effectively
Venue: arXiv cs.MM 2010
Year: 2010

Now-a-days internet has become a vast source of entertainment & new services are available in quick succession which provides entertainment to the users. One of this service i.e. Video-on-Demand is most hyped service in this context. Transferring the video over the network with less error is the main objective of the service providers. In this paper we present an algorithm for routing the video to the user in an effective manner along with a method that ensures less error rate than others.
On Achievable Rates of the Two-user Symmetric Gaussian Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

We study the Han-Kobayashi (HK) achievable sum rate for the two-user symmetric Gaussian interference channel. We find the optimal power split ratio between the common and private messages (assuming no time-sharing), and derive a closed form expression for the corresponding sum rate. This provides a finer understanding of the achievable HK sum rate, and allows for precise comparisons between this sum rate and that of orthogonal signaling. One surprising finding is that despite the fact that the channel is symmetric, allowing for asymmetric power split ratio at both users (i.e., asymmetric rates) can improve the sum rate significantly. Considering the high SNR regime, we specify the interference channel value above which the sum rate achieved using asymmetric power splitting outperforms the symmetric case.
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence
Venue: arXiv cs.DC 2010
Year: 2010

We study the {edge-coloring} problem in the message-passing model of distributed computing. This is one of the most fundamental and well-studied problems in this area. Currently, the best-known deterministic algorithms for (2Delta -1)-edge-coloring requires O(Delta) + log-star n time \cite{PR01}, where Delta is the maximum degree of the input graph. Also, recent results of \cite{BE10} for vertex-coloring imply that one can get an O(Delta)-edge-coloring in O(Delta^{epsilon} \cdot \log n) time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta log n) time, for an arbitrarily small constant epsilon > 0. In this paper we devise a drastically faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(Delta)-edge-coloring in O(Delta^{epsilon}) + log-star n time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta) + log-star n time. This result improves the previous state-of-the-art {exponentially} in a wide range of Delta, specifically, for 2^{Omega(\log-star n)} \leq Delta \leq polylog(n). In addition, for small values of Delta our deterministic algorithm outperforms all the existing {randomized} algorithms for this problem. On our way to these results we study the {vertex-coloring} problem on the family of graphs with bounded {neighborhood independence}. This is a large family, which strictly includes line graphs of r-hypergraphs for any r = O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to {general} graphs. Our main technical contribution is a subroutine that computes an O(Delta/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p^2) + \log-star n time, for a parameter p, 1 \leq p \leq Delta.
How to evaluate universities in terms of their relative citation impacts: Fractional counting of citations and the normalization of differences among disciplines
Venue: arXiv cs.DL 2010
Year: 2010

Fractional counting of citations can improve on ranking of multi-disciplinary research units (such as universities) by normalizing the differences among fields of science in terms of differences in citation behavior. Furthermore, normalization in terms of citing papers abolishes the unsolved questions in scientometrics about the delineation of fields of science in terms of journals and normalization when comparing among different journals. Using publication and citation data of seven Korean research universities, we demonstrate the advantages and the differences in the rankings, explain the possible statistics, and suggest ways to visualize the differences in (citing) audiences in terms of a network.
Constructing Two Edge-Disjoint Hamiltonian Cycles in Locally Twisted Cubes
Venue: arXiv cs.DC 2010
Year: 2010

The $n$-dimensional hypercube network $Q_n$ is one of the most popular interconnection networks since it has simple structure and is easy to implement. The $n$-dimensional locally twisted cube, denoted by $LTQ_n$, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as $Q_n$. One advantage of $LTQ_n$ is that the diameter is only about half of the diameter of $Q_n$. Recently, some interesting properties of $LTQ_n$ were investigated. In this paper, we construct two edge-disjoint Hamiltonian cycles in the locally twisted cube $LTQ_n$, for any integer $n\geqslant 4$. The presence of two edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the locally twisted cube.
Regular Expressions, au point
Venue: arXiv cs.FL 2010
Year: 2010

We introduce a new technique for constructing a finite state deterministic automaton from a regular expression, based on the idea of marking a suitable set of positions inside the expression, intuitively representing the possible points reached after the processing of an initial prefix of the input string. Pointed regular expressions join the elegance and the symbolic appealingness of Brzozowski's derivatives, with the effectiveness of McNaughton and Yamada's labelling technique, essentially combining the best of the two approaches.