OpenRaiser/Intern-Atlas huggingface dataset:
Everywhere-Sparse Spanners via Dense Subgraphs
Venue: arXiv cs.DS 2012
Year: 2012

The significant progress in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped spanners that are everywhere-sparse (small maximum degree). This disparity is in line with other network design problems, where the maximum-degree objective has been a notorious technical challenge. Our main result is for the Lowest Degree 2-Spanner (LD2S) problem, where the goal is to compute a 2-spanner of an input graph so as to minimize the maximum degree. We design a polynomial-time algorithm achieving approximation factor $\tilde O(Δ^{3-2\sqrt{2}}) \approx \tilde O(Δ^{0.172})$, where $Δ$ is the maximum degree of the input graph. The previous $\tilde O(Δ^{1/4})$ -approximation was proved nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998]. Our main conceptual contribution is to establish a formal connection between LD2S and a variant of the Densest k-Subgraph (DkS) problem. Specifically, we design for both problems strong relaxations based on the Sherali-Adams linear programming (LP) hierarchy, and show that "faithful" randomized rounding of the DkS-variant can be used to round LD2S solutions. Our notion of faithfulness intuitively means that all vertices and edges are chosen with probability proportional to their LP value, but the precise formulation is more subtle. Unfortunately, the best algorithms known for DkS use the Lovász-Schrijver LP hierarchy in a non-faithful way [Bhaskara, Charikar, Chlamtac, Feige, and Vijayaraghavan, STOC 2010]. Our main technical contribution is to overcome this shortcoming, while still matching the gap that arises in random graphs by planting a subgraph with same log-density.
Distributed Linear Precoder Optimization and Base Station Selection for an Uplink Heterogeneous Network
Venue: arXiv cs.IT 2012
Year: 2012

In a heterogeneous wireless cellular network, each user may be covered by multiple access points such as macro/pico/relay/femto base stations (BS). An effective approach to maximize the sum utility (e.g., system throughput) in such a network is to jointly optimize users' linear procoders as well as their base station associations. In this paper we first show that this joint optimization problem is NP-hard and thus is difficult to solve to global optimality. To find a locally optimal solution, we formulate the problem as a noncooperative game in which the users and the BSs both act as players. We introduce a set of new utility functions for the players and show that every Nash equilibrium (NE) of the resulting game is a stationary solution of the original sum utility maximization problem. Moreover, we develop a best-response type algorithm that allows the players to distributedly reach a NE of the game. Simulation results show that the proposed distributed algorithm can effectively relieve local BS congestion and simultaneously achieve high throughput and load balancing in a heterogeneous network.
On cyclically-interval edge colorings of trees
Venue: arXiv cs.DM 2012
Year: 2012

For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $φ:E(G)\rightarrow\{1,2,\ldots,t\}$ is called a proper edge $t$-coloring of a graph $G$ if adjacent edges are colored differently and each of $t$ colors is used. An arbitrary nonempty subset of consecutive integers is called an interval. If $φ$ is a proper edge $t$-coloring of a graph $G$ and $x\in V(G)$, then $S_G(x,φ)$ denotes the set of colors of edges of $G$ which are incident with $x$. A proper edge $t$-coloring $φ$ of a graph $G$ is called a cyclically-interval $t$-coloring if for any $x\in V(G)$ at least one of the following two conditions holds: a) $S_G(x,φ)$ is an interval, b) $\{1,2,\ldots,t\}\setminus S_G(x,φ)$ is an interval. For any $t\in \mathbb{N}$, let $\mathfrak{M}_t$ be the set of graphs for which there exists a cyclically-interval $t$-coloring, and let $$\mathfrak{M}\equiv\bigcup_{t\geq1}\mathfrak{M}_t.$$ For an arbitrary tree $G$, it is proved that $G\in\mathfrak{M}$ and all possible values of $t$ are found for which $G\in\mathfrak{M}_t.$
Geometric Computations on Indecisive and Uncertain Points
Venue: arXiv cs.CG 2012
Year: 2012

We study computing geometric problems on uncertain points. An uncertain point is a point that does not have a fixed location, but rather is described by a probability distribution. When these probability distributions are restricted to a finite number of locations, the points are called indecisive points. In particular, we focus on geometric shape-fitting problems and on building compact distributions to describe how the solutions to these problems vary with respect to the uncertainty in the points. Our main results are: (1) a simple and efficient randomized approximation algorithm for calculating the distribution of any statistic on uncertain data sets; (2) a polynomial, deterministic and exact algorithm for computing the distribution of answers for any LP-type problem on an indecisive point set; and (3) the development of shape inclusion probability (SIP) functions which captures the ambient distribution of shapes fit to uncertain or indecisive point sets and are admissible to the two algorithmic constructions.
Bounds on List Decoding Gabidulin Codes
Venue: arXiv cs.IT 2012
Year: 2012

An open question about Gabidulin codes is whether polynomial-time list decoding beyond half the minimum distance is possible or not. In this contribution, we give a lower and an upper bound on the list size, i.e., the number of codewords in a ball around the received word. The lower bound shows that if the radius of this ball is greater than the Johnson radius, this list size can be exponential and hence, no polynomial-time list decoding is possible. The upper bound on the list size uses subspace properties.
Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
Venue: arXiv cs.FL 2012
Year: 2012

Deciding in an efficient way weak probabilistic bisimulation in the context of Probabilistic Automata is an open problem for about a decade. In this work we close this problem by proposing a procedure that checks in polynomial time the existence of a weak combined transition satisfying the step condition of the bisimulation. We also present several extensions of weak combined transitions, such as hyper-transitions and the new concepts of allowed weak combined and hyper-transitions and of equivalence matching, that turn out to be verifiable in polynomial time as well. These results set the ground for the development of more effective compositional analysis algorithms for probabilistic systems.
Hypothesis testing using pairwise distances and associated kernels (with Appendix)
Venue: arXiv cs.LG 2012
Year: 2012

We provide a unifying framework linking two classes of statistics used in two-sample and independence testing: on the one hand, the energy distances and distance covariances from the statistics literature; on the other, distances between embeddings of distributions to reproducing kernel Hilbert spaces (RKHS), as established in machine learning. The equivalence holds when energy distances are computed with semimetrics of negative type, in which case a kernel may be defined such that the RKHS distance between distributions corresponds exactly to the energy distance. We determine the class of probability distributions for which kernels induced by semimetrics are characteristic (that is, for which embeddings of the distributions to an RKHS are injective). Finally, we investigate the performance of this family of kernels in two-sample and independence tests: we show in particular that the energy distance most commonly employed in statistics is just one member of a parametric family of kernels, and that other choices from this family can yield more powerful tests.
An efficient implementation of the algorithm computing the Borel-fixed points of a Hilbert scheme
Venue: arXiv cs.SC 2012
Year: 2012

Borel-fixed ideals play a key role in the study of Hilbert schemes. Indeed each component and each intersection of components of a Hilbert scheme contains at least one Borel-fixed point, i.e. a point corresponding to a subscheme defined by a Borel-fixed ideal. Moreover Borel-fixed ideals have good combinatorial properties, which make them very interesting in an algorithmic perspective. In this paper, we propose an implementation of the algorithm computing all the saturated Borel-fixed ideals with number of variables and Hilbert polynomial assigned, introduced from a theoretical point of view in the paper "Segment ideals and Hilbert schemes of points", Discrete Mathematics 311 (2011).
Rule-weighted and terminal-weighted context-free grammars have identical expressivity
Venue: arXiv cs.CL 2012
Year: 2012

Two formalisms, both based on context-free grammars, have recently been proposed as a basis for a non-uniform random generation of combinatorial objects. The former, introduced by Denise et al, associates weights with letters, while the latter, recently explored by Weinberg et al in the context of random generation, associates weights to transitions. In this short note, we use a simple modification of the Greibach Normal Form transformation algorithm, due to Blum and Koch, to show the equivalent expressivities, in term of their induced distributions, of these two formalisms.
How Can Journal Impact Factors be Normalized across Fields of Science? An Assessment in terms of Percentile Ranks and Fractional Counts
Venue: arXiv cs.DL 2012
Year: 2012

Using the CD-ROM version of the Science Citation Index 2010 (N = 3,705 journals), we study the (combined) effects of (i) fractional counting on the impact factor (IF) and (ii) transformation of the skewed citation distributions into a distribution of 100 percentiles and six percentile rank classes (top-1%, top-5%, etc.). Do these approaches lead to field-normalized impact measures for journals? In addition to the two-year IF (IF2), we consider the five-year IF (IF5), the respective numerators of these IFs, and the number of Total Cites, counted both as integers and fractionally. These various indicators are tested against the hypothesis that the classification of journals into 11 broad fields by PatentBoard/National Science Foundation provides statistically significant between-field effects. Using fractional counting the between-field variance is reduced by 91.7% in the case of IF5, and by 79.2% in the case of IF2. However, the differences in citation counts are not significantly affected by fractional counting. These results accord with previous studies, but the longer citation window of a fractionally counted IF5 can lead to significant improvement in the normalization across fields.
Indexing Reverse Top-k Queries
Venue: arXiv cs.DB 2012
Year: 2012

We consider the recently introduced monochromatic reverse top-k queries which ask for, given a new tuple q and a dataset D, all possible top-k queries on D union {q} for which q is in the result. Towards this problem, we focus on designing indexes in two dimensions for repeated (or batch) querying, a novel but practical consideration. We present the insight that by representing the dataset as an arrangement of lines, a critical k-polygon can be identified and used exclusively to respond to reverse top-k queries. We construct an index based on this observation which has guaranteed worst-case query cost that is logarithmic in the size of the k-polygon. We implement our work and compare it to related approaches, demonstrating that our index is fast in practice. Furthermore, we demonstrate through our experiments that a k-polygon is comprised of a small proportion of the original data, so our index structure consumes little disk space.
Interleaving Commands: a Threat to the Interoperability of Smartcard Based Security Applications
Venue: arXiv cs.CR 2012
Year: 2012

Although smartcards are widely used, secure smartcard interoperability has remained a significant challenge. Usually each manufacturer provides a closed environment for their smartcard based applications including the microchip, associated firmware and application software. While the security of this "package" can be tested and certified for example based on the Common Criteria, the secure and convenient interoperability with other smartcards and smartcard applications is not guaranteed. Ideally one would have a middleware that can support various smartcards and smartcard applications. In our ongoing research we study this scenario with the goal to develop a way to certify secure smartcard interoperability in such an environment. Here we discuss and experimentally demonstrate one critical security problem: if several smartcards are connected via a middleware it is possible that a smartcard of type S receives commands that were supposed to be executed on a different smartcard of type S'. Such "external commands" can interleave with the commands that were supposed to be executed on S. Here we demonstrate this problem experimentally with a Common Criteria certified digital signature process on two commercially available smartcards. Importantly, in some of these cases the digital signature processes terminate without generating an error message or warning to the user.
Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
Venue: arXiv cs.CC 2012
Year: 2012

Three decades of research in communication complexity have led to the invention of a number of techniques to lower bound randomized communication complexity. The majority of these techniques involve properties of large submatrices (rectangles) of the truth-table matrix defining a communication problem. The only technique that does not quite fit is information complexity, which has been investigated over the last decade. Here, we connect information complexity to one of the most powerful "rectangular" techniques: the recently-introduced smooth corruption (or "smooth rectangle") bound. We show that the former subsumes the latter under rectangular input distributions. We conjecture that this subsumption holds more generally, under arbitrary distributions, which would resolve the long-standing direct sum question for randomized communication. As an application, we obtain an optimal $Ω(n)$ lower bound on the information complexity---under the {\em uniform distribution}---of the so-called orthogonality problem (ORT), which is in turn closely related to the much-studied Gap-Hamming-Distance (GHD). The proof of this bound is along the lines of recent communication lower bounds for GHD, but we encounter a surprising amount of additional technical detail.
Variable Selection for Latent Dirichlet Allocation
Venue: arXiv cs.LG 2012
Year: 2012

In latent Dirichlet allocation (LDA), topics are multinomial distributions over the entire vocabulary. However, the vocabulary usually contains many words that are not relevant in forming the topics. We adopt a variable selection method widely used in statistical modeling as a dimension reduction tool and combine it with LDA. In this variable selection model for LDA (vsLDA), topics are multinomial distributions over a subset of the vocabulary, and by excluding words that are not informative for finding the latent topic structure of the corpus, vsLDA finds topics that are more robust and discriminative. We compare three models, vsLDA, LDA with symmetric priors, and LDA with asymmetric priors, on heldout likelihood, MCMC chain consistency, and document classification. The performance of vsLDA is better than symmetric LDA for likelihood and classification, better than asymmetric LDA for consistency and classification, and about the same in the other comparisons.
A Comprehensive Study of CRM through Data Mining Techniques
Venue: arXiv cs.DB 2012
Year: 2012

In today's competitive scenario in corporate world, "Customer Retention" strategy in Customer Relationship Management (CRM) is an increasingly pressed issue. Data mining techniques play a vital role in better CRM. This paper attempts to bring a new perspective by focusing the issue of data mining applications, opportunities and challenges in CRM. It covers the topic such as customer retention, customer services, risk assessment, fraud detection and some of the data mining tools which are widely used in CRM.
Rakeness in the design of Analog-to-Information Conversion of Sparse and Localized Signals
Venue: arXiv cs.IT 2012
Year: 2012

Design of Random Modulation Pre-Integration systems based on the restricted-isometry property may be suboptimal when the energy of the signals to be acquired is not evenly distributed, i.e. when they are both sparse and localized. To counter this, we introduce an additional design criterion, that we call rakeness, accounting for the amount of energy that the measurements capture from the signal to be acquired. Hence, for localized signals a proper system tuning increases the rakeness as well as the average SNR of the samples used in its reconstruction. Yet, maximizing average SNR may go against the need of capturing all the components that are potentially non-zero in a sparse signal, i.e., against the restricted isometry requirement ensuring reconstructability. What we propose is to administer the trade-off between rakeness and restricted isometry in a statistical way by laying down an optimization problem. The solution of such an optimization problem is the statistic of the process generating the random waveforms onto which the signal is projected to obtain the measurements. The formal definition of such a problems is given as well as its solution for signals that are either localized in frequency or in more generic domain. Sample applications, to ECG signals and small images of printed letters and numbers, show that rakeness-based design leads to non-negligible improvements in both cases.
Capacity Allocation and Pricing Strategies for Wireless Femtocell Services
Venue: arXiv cs.NI 2012
Year: 2012

Indoor cell phone users often suffer from poor connectivity. One promising solution, femtocell technology, has been rapidly developed and deployed over the past few years. One of the biggest challenges for femtocell deployment is lack of a clear business model. This paper investigates the economic incentive for the cellular operator (also called macrocell operator) to enable femtocell service by leasing spectrum resource to an independent femtocell operator. On the one hand, femtocell services can increase communication service quality and thus increase the efficiency of the spectrum resource. On the other hand, femtocell services may introduce more competition to the market. We model the interactions between a macrocell operator, a femtocell operator, and users as a three-stage dynamic game, and derive the equilibrium pricing and capacity allocation decisions. We show that when spectrum resources are very limited, the macrocell operator has incentive to lease spectrum to femtocell operators, as femtocell service can provide access to more users and efficiently increase the coverage. However, when the total spectrum resource is large, femtocell service offers significant competition to macrocell service. Macrocell operator thus has less incentive to enable femtocell service. We also investigate the issue of additional operational cost and limited coverage of femtocell service on equilibrium decisions, consumer surplus and social welfare.
Information Spectrum Approach to Overflow Probability of Variable-Length Codes with Conditional Cost Function
Venue: arXiv cs.IT 2012
Year: 2012

Lossless variable-length source coding with unequal cost function is considered for general sources. In this problem, the codeword cost instead of codeword length is important. The infimum of average codeword cost has already been determined for general sources. We consider the overflow probability of codeword cost and determine the infimum of achievable overflow threshold. Our analysis is on the basis of information-spectrum methods and hence valid through the general source.
Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates
Venue: arXiv cs.NI 2012
Year: 2012

We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, which is determined by the signal-to-interference-plus-noise ratio (SINR). Each wireless link has a utility function mapping SINR values to the respective data rates. We have to decide which transmissions are performed simultaneously and (depending on the problem variant) also which transmission powers are used. In the capacity-maximization problem, one strives to maximize the overall network throughput, i.e., the summed utility of all links. For arbitrary utility functions (not necessarily continuous ones), we present an O(log n)-approximation when having n communication requests. This algorithm is built on a constant-factor approximation for the special case of the respective problem where utility functions only consist of a single step. In other words, each link has an individual threshold and we aim at maximizing the number of links whose threshold is satisfied. On the way, this improves the result in [Kesselheim, SODA 2011] by not only extending it to individual thresholds but also showing a constant approximation factor independent of assumptions on the underlying metric space or the network parameters. In addition, we consider the latency-minimization problem. Here, each link has a demand, e.g., representing an amount of data. We have to compute a schedule of shortest possible length such that for each link the demand is fulfilled, that is the overall summed utility (or data transferred) is at least as large as its demand. Based on the capacity-maximization algorithm, we show an O(log^2 n)-approximation for this problem.
Image Enhancement with Statistical Estimation
Venue: arXiv cs.MM 2012
Year: 2012

Contrast enhancement is an important area of research for the image analysis. Over the decade, the researcher worked on this domain to develop an efficient and adequate algorithm. The proposed method will enhance the contrast of image using Binarization method with the help of Maximum Likelihood Estimation (MLE). The paper aims to enhance the image contrast of bimodal and multi-modal images. The proposed methodology use to collect mathematical information retrieves from the image. In this paper, we are using binarization method that generates the desired histogram by separating image nodes. It generates the enhanced image using histogram specification with binarization method. The proposed method has showed an improvement in the image contrast enhancement compare with the other image.
Comparison of CSMA based MAC protocols of wireless sensor networks
Venue: arXiv cs.NI 2012
Year: 2012

Energy conservation has been an important area of interest in Wireless Sensor networks (WSNs). Medium Access Control (MAC) protocols play an important role in energy conservation. In this paper, we describe CSMA based MAC protocols for WSN and analyze the simulation results of these protocols. We implemented S-MAC, T-MAC, B-MAC, B-MAC+, X-MAC, DMAC and Wise-MAC in TOSSIM, a simulator which unlike other simulators simulates the same code running on real hardware. Previous surveys mainly focused on the classification of MAC protocols according to the techniques being used or problem dealt with and presented a theoretical evaluation of protocols. This paper presents the comparative study of CSMA based protocols for WSNs, showing which MAC protocol is suitable in a particular environment and supports the arguments with the simulation results. The comparative study can be used to find the best suited MAC protocol for wireless sensor networks in different environments.