OpenRaiser/Intern-Atlas huggingface dataset:
A Critique of "Solving the P/NP Problem Under Intrinsic Uncertainty", arXiv:0811.0463
Venue: arXiv cs.CC 2009
Year: 2009

Although whether P equals NP is an important, open problem in computer science, and although Jaeger's 2008 paper, "Solving the P/NP Problem Under Intrinsic Uncertainty" (arXiv:0811.0463) presents an attempt at tackling the problem by discussing the possibility that all computation is uncertain to some degree, there are a number of logical oversights present in that paper which preclude it from serious consideration toward having resolved P-versus-NP. There are several differences between the model of computation presented in Jaeger's paper and the standard model, as well as several bold assumptions that are not well supported in Jaeger's paper or in the literature. In addition, we find several omissions of rigorous proof that ultimately weaken this paper to a point where it cannot be considered a candidate solution to the P-versus-NP problem.
Approximation Algorithms for Key Management in Secure Multicast
Venue: arXiv cs.DS 2009
Year: 2009

Many data dissemination and publish-subscribe systems that guarantee the privacy and authenticity of the participants rely on symmetric key cryptography. An important problem in such a system is to maintain the shared group key as the group membership changes. We consider the problem of determining a key hierarchy that minimizes the average communication cost of an update, given update frequencies of the group members and an edge-weighted undirected graph that captures routing costs. We first present a polynomial-time approximation scheme for minimizing the average number of multicast messages needed for an update. We next show that when routing costs are considered, the problem is NP-hard even when the underlying routing network is a tree network or even when every group member has the same update frequency. Our main result is a polynomial time constant-factor approximation algorithm for the general case where the routing network is an arbitrary weighted graph and group members have nonuniform update frequencies.
Online Maximizing Weighted Throughput In A Fading Channel
Venue: arXiv cs.IT 2009
Year: 2009

We consider online scheduling weighted packets with time constraints over a fading channel. Packets arrive at the transmitter in an online manner. Each packet has a value and a deadline by which it should be sent. The fade state of the channel determines the throughput obtained per unit of time and the channel's quality may change over time. In this paper, we design online algorithms to maximize weighted throughput, defined as the total value of the packets sent by their respective deadlines. Competitive ratio is employed to measure an online algorithm's performance. For this problem and one of its variants, we present two online algorithms with competitive ratios 2.618 and 2 respectively.
Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton
Venue: arXiv cs.FL 2009
Year: 2009

The problem of computing the edit-distance between a string and a finite automaton arises in a variety of applications in computational biology, text processing, and speech recognition. This paper presents linear-space algorithms for computing the edit-distance between a string and an arbitrary weighted automaton over the tropical semiring, or an unambiguous weighted automaton over an arbitrary semiring. It also gives an efficient linear-space algorithm for finding an optimal alignment of a string and such a weighted automaton.
Theoretical Analysis of Cyclic Frequency Domain Noise and Feature Detection for Cognitive Radio Systems
Venue: arXiv cs.IT 2009
Year: 2009

In cognitive radio systems, cyclostationary feature detection plays an important role in spectrum sensing, especially in low SNR cases. To configure the detection threshold under a certain noise level and a pre-set miss detection probability Pf, it's important to derive the theoretical distribution of the observation variable. In this paper, noise distribution in cyclic frequency domain has been studied and Generalized Extreme Value (GEV) distribution is found to be a precise match. Maximum likelihood estimation is applied to estimate the parameters of GEV. Monte Carlo simulation has been carried out to show that the simulated ROC curve is coincided with the theoretical ROC curve, which proves the efficiency of the theoretical distribution model.
Interference Alignment with Limited Feedback
Venue: arXiv cs.IT 2009
Year: 2009

We consider single-antenna interference networks where M sources, each with an average transmit power of P/M, communicate with M destinations over frequency-selective channels (with L taps each) and each destination has perfect knowledge of its channels from each of the sources. Assuming that there exist error-free non-interfering broadcast feedback links from each destination to all the nodes (i.e., sources and destinations) in the network, we show that naive interference alignment, in conjunction with vector quantization of the impulse response coefficients according to the scheme proposed in Mukkavilli et al., IEEE Trans. IT, 2003, achieves full spatial multiplexing gain of M/2, provided that the number of feedback bits broadcast by each destination is at least M(L-1) log P.
A representation of non-uniformly sampled deterministic and random signals and their reconstruction using sample values and derivatives
Venue: arXiv cs.IT 2009
Year: 2009

Shannon in his 1949 paper suggested the use of derivatives to increase the W*T product of the sampled signal. Use of derivatives enables improved reconstruction particularly in the case of non-uniformly sampled signals. An FM-AM representation for Lagrange/Hermite type interpolation and a reconstruction technique are discussed. The representation using a product of a polynomial and exponential of a polynomial is extensible to two dimensions. When the directly available information is inadequate, estimation of the signal and its derivative based on the correlation characteristics of Gaussian filtered noise has been studied. This requires computation of incomplete normal integrals. Reduction methods for reducing multivariate normal variables include multistage partitioning, dynamic path integral and Hermite expansion for computing the probability integrals necessary for estimating the mean of the signal and its derivative at points intermediate between zero or threshold crossings. The signals and their derivatives as measured or estimated are utilized to reconstruct the signal at a desired sampling rate.
Perfect Phylogeny Haplotyping is Complete for Logspace
Venue: arXiv cs.CC 2009
Year: 2009

Haplotyping is the bioinformatics problem of predicting likely haplotypes based on given genotypes. It can be approached using Gusfield's perfect phylogeny haplotyping (PPH) method for which polynomial and linear time algorithms exist. These algorithm use sophisticated data structures or do a stepwise transformation of the genotype data into haplotype data and, therefore, need a linear amount of space. We are interested in the exact computational complexity of PPH and show that it can be solved space-efficiently by an algorithm that needs only a logarithmic amount of space. Together with the recently proved L-hardness of PPH, we establish L-completeness. Our algorithm relies on a new characterization for PPH in terms of bipartite graphs, which can be used both to decide and construct perfect phylogenies for genotypes efficiently.
Selective-Fading Multiple-Access MIMO Channels: Diversity-Multiplexing Tradeoff and Dominant Outage Event Regions
Venue: arXiv cs.IT 2009
Year: 2009

We establish the optimal diversity-multiplexing (DM) tradeoff for coherent selective-fading multiple-access MIMO channels and provide corresponding code design criteria. As a byproduct, on the conceptual level, we find an interesting relation between the DM tradeoff framework and the notion of dominant error event regions, first introduced in the AWGN case by Gallager, IEEE Trans. IT, 1985. This relation allows us to accurately characterize the error mechanisms in MIMO fading multiple-access channels. In particular, we find that, for a given rate tuple, the maximum achievable diversity order is determined by a single outage event that dominates the total error probability exponentially in SNR. Finally, we examine the distributed space-time code construction proposed by Badr and Belfiore, Int. Zurich Seminar on Commun., 2008, using the code design criteria derived in this paper.
Can the Utility of Anonymized Data be used for Privacy Breaches?
Venue: arXiv cs.DB 2009
Year: 2009

Group based anonymization is the most widely studied approach for privacy preserving data publishing. This includes k-anonymity, l-diversity, and t-closeness, to name a few. The goal of this paper is to raise a fundamental issue on the privacy exposure of the current group based approach. This has been overlooked in the past. The group based anonymization approach basically hides each individual record behind a group to preserve data privacy. If not properly anonymized, patterns can actually be derived from the published data and be used by the adversary to breach individual privacy. For example, from the medical records released, if patterns such as people from certain countries rarely suffer from some disease can be derived, then the information can be used to imply linkage of other people in an anonymized group with this disease with higher likelihood. We call the derived patterns from the published data the foreground knowledge. This is in contrast to the background knowledge that the adversary may obtain from other channels as studied in some previous work. Finally, we show by experiments that the attack is realistic in the privacy benchmark dataset under the traditional group based anonymization approach.
An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves
Venue: arXiv cs.CR 2009
Year: 2009

We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in $X$ and $Y$ are low with respect to their genera. The finite base fields $\FF_q$ are arbitrary, but their sizes should not grow too fast compared to the genus. For such families, the group structure and discrete logarithms can be computed in subexponential time of $L_{q^g}(1/3, O(1))$. The runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve.
Quantified Multimodal Logics in Simple Type Theory
Venue: arXiv cs.AI 2009
Year: 2009

We present a straightforward embedding of quantified multimodal logic in simple type theory and prove its soundness and completeness. Modal operators are replaced by quantification over a type of possible worlds. We present simple experiments, using existing higher-order theorem provers, to demonstrate that the embedding allows automated proofs of statements in these logics, as well as meta properties of them.
Generalized Kernel-based Visual Tracking
Venue: arXiv cs.CV 2009
Year: 2009

In this work we generalize the plain MS trackers and attempt to overcome standard mean shift trackers' two limitations. It is well known that modeling and maintaining a representation of a target object is an important component of a successful visual tracker. However, little work has been done on building a robust template model for kernel-based MS tracking. In contrast to building a template from a single frame, we train a robust object representation model from a large amount of data. Tracking is viewed as a binary classification problem, and a discriminative classification rule is learned to distinguish between the object and background. We adopt a support vector machine (SVM) for training. The tracker is then implemented by maximizing the classification score. An iterative optimization scheme very similar to MS is derived for this purpose.
Minimizing Communication in Linear Algebra
Venue: arXiv cs.CC 2009
Year: 2009

In 1981 Hong and Kung proved a lower bound on the amount of communication needed to perform dense, matrix-multiplication using the conventional $O(n^3)$ algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo and Tiskin gave a new proof of this result and extended it to the parallel case. In both cases the lower bound may be expressed as $Ω$(#arithmetic operations / $\sqrt{M}$), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, $LDL^T$ factorization, QR factorization, algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices, and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth) we get lower bounds on the number of messages required to move it (latency). We illustrate how to extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix), to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or if we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph theoretic problems. We point out recently designed algorithms for dense LU, Cholesky, QR, eigenvalue and the SVD problems that attain these lower bounds; implementations of LU and QR show large speedups over conventional linear algebra algorithms in standard libraries like LAPACK and ScaLAPACK. Many open problems remain.
Where are your Manners? Sharing Best Community Practices in the Web 2.0
Venue: arXiv cs.CY 2009
Year: 2009

The Web 2.0 fosters the creation of communities by offering users a wide array of social software tools. While the success of these tools is based on their ability to support different interaction patterns among users by imposing as few limitations as possible, the communities they support are not free of rules (just think about the posting rules in a community forum or the editing rules in a thematic wiki). In this paper we propose a framework for the sharing of best community practices in the form of a (potentially rule-based) annotation layer that can be integrated with existing Web 2.0 community tools (with specific focus on wikis). This solution is characterized by minimal intrusiveness and plays nicely within the open spirit of the Web 2.0 by providing users with behavioral hints rather than by enforcing the strict adherence to a set of rules.
The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition
Venue: arXiv cs.CG 2009
Year: 2009

A spanner graph on a set of points in $R^d$ contains a shortest path between any pair of points with length at most a constant factor of their Euclidean distance. In this paper we investigate new models and aim to interpret why good spanners 'emerge' in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. Our main result is to show that if edges are built in an arbitrary order but an edge is built if and only if its endpoints are not 'close' to the endpoints of an existing edge, the graph is a $(1 + \eps)$-spanner with a linear number of edges, constant average degree, and the total edge length as a small logarithmic factor of the cost of the minimum spanning tree. As a side product, we show a simple greedy algorithm for constructing optimal size well-separated pair decompositions that may be of interest on its own.
Automatic Summarization System coupled with a Question-Answering System (QAAS)
Venue: arXiv cs.IR 2009
Year: 2009

To select the most relevant sentences of a document, it uses an optimal decision algorithm that combines several metrics. The metrics processes, weighting and extract pertinence sentences by statistical and informational algorithms. This technique might improve a Question-Answering system, whose function is to provide an exact answer to a question in natural language. In this paper, we present the results obtained by coupling the Cortex summarizer with a Question-Answering system (QAAS). Two configurations have been evaluated. In the first one, a low compression level is selected and the summarization system is only used as a noise filter. In the second configuration, the system actually functions as a summarizer, with a very high level of compression. Our results on French corpus demonstrate that the coupling of Automatic Summarization system with a Question-Answering system is promising. Then the system has been adapted to generate a customized summary depending on the specific question. Tests on a french multi-document corpus have been realized, and the personalized QAAS system obtains the best performances.
Performance of Cognitive Radio Systems with Imperfect Radio Environment Map Information
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we describe the effect of imperfections in the radio environment map (REM) information on the performance of cognitive radio (CR) systems. Via simulations we explore the relationship between the required precision of the REM and various channel/system properties. For example, the degree of spatial correlation in the shadow fading is a key factor as is the interference constraint employed by the primary user. Based on the CR interferers obtained from the simulations, we characterize the temporal behavior of such systems by computing the level crossing rates (LCRs) of the cumulative interference represented by these CRs. This evaluates the effect of short term fluctuations above acceptable interference levels due to the fast fading. We derive analytical formulae for the LCRs in Rayleigh and Rician fast fading conditions. The analytical results are verified by Monte Carlo simulations.
Deterministic Relay Networks with State Information
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by fading channels and erasure channels, the problem of reliable communication over deterministic relay networks is studied, in which relay nodes receive a function of the incoming signals and a random network state. An achievable rate is characterized for the case in which destination nodes have full knowledge of the state information. If the relay nodes receive a linear function of the incoming signals and the state in a finite field, then the achievable rate is shown to be optimal, meeting the cut-set upper bound on the capacity. This result generalizes on a unified framework the work of Avestimehr, Diggavi, and Tse on the deterministic networks with state dependency, the work of Dana, Gowaikar, Palanki, Hassibi, and Effros on linear erasure networks with interference, and the work of Smith and Vishwanath on linear erasure networks with broadcast.
A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
Venue: arXiv cs.LO 2009
Year: 2009

Graded modal logic is the formal language obtained from ordinary (propositional) modal logic by endowing its modal operators with cardinality constraints. Under the familiar possible-worlds semantics, these augmented modal operators receive interpretations such as "It is true at no fewer than 15 accessible worlds that...", or "It is true at no more than 2 accessible worlds that...". We investigate the complexity of satisfiability for this language over some familiar classes of frames. This problem is more challenging than its ordinary modal logic counterpart--especially in the case of transitive frames, where graded modal logic lacks the tree-model property. We obtain tight complexity bounds for the problem of determining the satisfiability of a given graded modal logic formula over the classes of frames characterized by any combination of reflexivity, seriality, symmetry, transitivity and the Euclidean property.
An Object-Oriented and Fast Lexicon for Semantic Generation
Venue: arXiv cs.CL 2009
Year: 2009

This paper is about the technical design of a large computational lexicon, its storage, and its access from a Prolog environment. Traditionally, efficient access and storage of data structures is implemented by a relational database management system. In Delilah, a lexicon-based NLP system, efficient access to the lexicon by the semantic generator is vital. We show that our highly detailed HPSG-style lexical specifications do not fit well in the Relational Model, and that they cannot be efficiently retrieved. We argue that they fit more naturally in the Object-Oriented Model. Although storage of objects is redundant, we claim that efficient access is still possible by applying indexing, and compression techniques from the Relational Model to the Object-Oriented Model. We demonstrate that it is possible to implement object-oriented storage and fast access in ISO Prolog.
The Game of Cipher Beads
Venue: arXiv cs.DL 2009
Year: 2009

Comparison between the various impact factors of a few Russian journals demonstrates the deficiencies of the popular citation indices.
Searching the Nodes of a Graph: Theory and Algorithms
Venue: arXiv cs.DM 2009
Year: 2009

One or more searchers must capture an invisible evader hiding in the nodes of a graph. We study this graph search problem; we emphasize that we study the capture of a node-located evader, which has received less attention than edge search. We show that in general graphs the problem of node search is easier than that of edge search (however node search is NP-complete, just like edge search). We concentrate on the internal monotone connected (IMC) node search of trees and show that it is essentially equivalent to IMC edge search. For IMC node search on general graphs we present a new algorithm: GSST (Guaranteed Search by Spanning Tree) which clears the graph G by performing all its clearing moves along a spanning tree T of G. We prove the existence of probabilistically complete variants of GSST. Our experiments also indicate that GSST can efficiently node-clear large graphs given only a small running time. An implementation of GSST is also provided and made publicly available.
Auctions with Online Supply
Venue: arXiv cs.GT 2009
Year: 2009

We study the problem of selling identical goods to n unit-demand bidders in a setting in which the total supply of goods is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation. Our main result is a separation between these two models. We show that all truthful mechanisms, even randomized, achieve a diminishing fraction of the optimal social welfare (namely, no better than a Omega(loglog n) approximation) in the adversarial setting. In sharp contrast, in the stochastic model, under a standard monotone hazard-rate condition, we present a truthful mechanism that achieves a constant approximation. We show that the monotone hazard rate condition is necessary, and also characterize a natural subclass of truthful mechanisms in our setting, the set of online-envy-free mechanisms. All of the mechanisms we present fall into this class, and we prove almost optimal lower bounds for such mechanisms. Since auctions with unknown supply are regularly run in many online-advertising settings, our main results emphasize the importance of considering distributional information in the design of auctions in such environments.