OpenRaiser/Intern-Atlas huggingface dataset:
Graph-based classification of multiple observation sets
Venue: arXiv cs.CV 2009
Year: 2009

We consider the problem of classification of an object given multiple observations that possibly include different transformations. The possible transformations of the object generally span a low-dimensional manifold in the original signal space. We propose to take advantage of this manifold structure for the effective classification of the object represented by the observation set. In particular, we design a low complexity solution that is able to exploit the properties of the data manifolds with a graph-based algorithm. Hence, we formulate the computation of the unknown label matrix as a smoothing process on the manifold under the constraint that all observations represent an object of one single class. It results into a discrete optimization problem, which can be solved by an efficient and low complexity algorithm. We demonstrate the performance of the proposed graph-based algorithm in the classification of sets of multiple images. Moreover, we show its high potential in video-based face recognition, where it outperforms state-of-the-art solutions that fall short of exploiting the manifold structure of the face image data sets.
P is not equal to NP
Venue: arXiv cs.CC 2009
Year: 2009

SAT is not in P, is true and provable in a simply consistent extension B' of a first order theory B of computing, with a single finite axiom characterizing a universal Turing machine. Therefore, P is not equal to NP, is true and provable in a simply consistent extension B" of B.
Combining Advanced Visualization and Automatized Reasoning for Webometrics: A Test Study
Venue: arXiv cs.IR 2009
Year: 2009

This paper presents a first attempt at performing a precise and automatic identification of the linking behaviour in a scientific domain through the analysis of the communication of the related academic institutions on the web. The proposed approach is based on the paradigm of multiple viewpoint data analysis (MVDA) than can be fruitfully exploited to highlight relationships between data, like websites, carrying several kinds of description. It uses the MultiSOM clustering and mapping method. The domain that has been chosen for this study is the domain of Computer Science in Germany. The analysis is conduced on a set of 438 websites of this domain using all together, thematic, geographic and linking information. It highlights interesting results concerning both global and local linking behaviour.
A Bayesian Framework for Collaborative Multi-Source Signal Detection
Venue: arXiv cs.IT 2009
Year: 2009

This paper introduces a Bayesian framework to detect multiple signals embedded in noisy observations from a sensor array. For various states of knowledge on the communication channel and the noise at the receiving sensors, a marginalization procedure based on recent tools of finite random matrix theory, in conjunction with the maximum entropy principle, is used to compute the hypothesis selection criterion. Quite remarkably, explicit expressions for the Bayesian detector are derived which enable to decide on the presence of signal sources in a noisy wireless environment. The proposed Bayesian detector is shown to outperform the classical power detector when the noise power is known and provides very good performance for limited knowledge on the noise power. Simulations corroborate the theoretical results and quantify the gain achieved using the proposed Bayesian framework.
Allocation of control and data channels for Large-Scale Wireless Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

Both IEEE 802.15.4 and 802.15.4a standards allow for dynamic channel allocation and use of multiple channels available at their physical layers but its MAC protocols are designed only for single channel. Also, sensor's transceivers such as CC2420 provide multiple channels and as shown in [1], [2] and [3] channel switch latency of CC2420 transceiver is just about 200$μ$s. In order to enhance both energy efficiency and to shorten end to end delay, we propose, in this report, a spectrum-efficient frequency allocation schemes that are able to statically assign control channels and dynamically reuse data channels for Personal Area Networks (PANs) inside a Large-Scale WSN based on UWB technology.
Resource Allocation for Downlink Cellular OFDMA Systems: Part II - Practical Algorithms and Optimal Reuse Factor
Venue: arXiv cs.IT 2009
Year: 2009

In a companion paper, we characterized the optimal resource allocation in terms of power control and subcarrier assignment, for a downlink sectorized OFDMA system. In our model, the network is assumed to be one dimensional for the sake of analysis. We also assume that a certain part of the available bandwidth is likely to be reused by different base stations while that the other part of the bandwidth is shared in an orthogonal way between these base stations. The optimal resource allocation characterized in Part I is obtained by minimizing the total power spent by the network under the constraint that all users rate requirements are satisfied. When optimal resource allocation is used, any user receives data either in the reused bandwidth or in the protected bandwidth, but not in both (except for at most one pivot-user in each cell). We also proposed an algorithm that determines the optimal values of users resource allocation parameters. The optimal allocation algorithm proposed in Part I requires a large number of operations. In the present paper, we propose a distributed practical resource allocation algorithm with low complexity. We study the asymptotic behavior of both this simplified resource allocation algorithm and the optimal resource allocation algorithm of Part I as the number of users in each cell tends to infinity. Our analysis allows to prove that the proposed simplified algorithm is asymptotically optimal. As a byproduct of our analysis, we characterize the optimal value of the frequency reuse factor.
Universally Utility-Maximizing Privacy Mechanisms
Venue: arXiv cs.DB 2009
Year: 2009

A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Privacy can be rigorously quantified using the framework of {\em differential privacy}, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a {\em geometric mechanism} $M^*$ -- a discrete variant of the simple and well-studied Laplace mechanism -- that is {\em simultaneously expected loss-minimizing} for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: {\em every} potential user $u$, no matter what its side information and preferences, derives as much utility from $M^*$ as from interacting with a differentially private mechanism $M_u$ that is optimally tailored to $u$.
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we can find in deterministic poly(n^{\log n},\log |k|) time "either" a nontrivial factor of f(x) "or" a nontrivial automorphism of k[x]/(f(x)) of order n. This main tool leads to various new GRH-free results, most striking of which are: (1) Given a noncommutative algebra over a finite field, we can find a zero divisor in deterministic subexponential time. (2) Given a positive integer r such that either 8|r or r has at least two distinct odd prime factors. There is a deterministic polynomial time algorithm to find a nontrivial factor of the r-th cyclotomic polynomial over a finite field. In this paper, following the seminal work of Lenstra (1991) on constructing isomorphisms between finite fields, we further generalize classical Galois theory constructs like cyclotomic extensions, Kummer extensions, Teichmuller subgroups, to the case of commutative semisimple algebras with automorphisms. These generalized constructs help eliminate the dependence on GRH.
Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability
Venue: arXiv cs.CC 2009
Year: 2009

It is folklore particularly in numerical and computer sciences that, instead of solving some general problem f:A->B, additional structural information about the input x in A (that is any kind of promise that x belongs to a certain subset A' of A) should be taken advantage of. Some examples from real number computation show that such discrete advice can even make the difference between computability and uncomputability. We turn this into a both topological and combinatorial complexity theory of information, investigating for several practical problems how much advice is necessary and sufficient to render them computable. Specifically, finding a nontrivial solution to a homogeneous linear equation A*x=0 for a given singular real NxN-matrix A is possible when knowing rank(A)=0,1,...,N-1; and we show this to be best possible. Similarly, diagonalizing (i.e. finding a BASIS of eigenvectors of) a given real symmetric NxN-matrix is possible when knowing the number of distinct eigenvalues: an integer between 1 and N (the latter corresponding to the nondegenerate case). And again we show that N-fold (i.e. roughly log N bits of) additional information is indeed necessary in order to render this problem (continuous and) computable; whereas for finding SOME SINGLE eigenvector of A, providing the truncated binary logarithm of the least-dimensional eigenspace of A--i.e. Theta(log N)-fold advice--is sufficient and optimal.
Transmit Diversity v. Spatial Multiplexing in Modern MIMO Systems
Venue: arXiv cs.IT 2009
Year: 2009

A contemporary perspective on the tradeoff between transmit antenna diversity and spatial multiplexing is provided. It is argued that, in the context of most modern wireless systems and for the operating points of interest, transmission techniques that utilize all available spatial degrees of freedom for multiplexing outperform techniques that explicitly sacrifice spatial multiplexing for diversity. In the context of such systems, therefore, there essentially is no decision to be made between transmit antenna diversity and spatial multiplexing in MIMO communication. Reaching this conclusion, however, requires that the channel and some key system features be adequately modeled and that suitable performance metrics be adopted; failure to do so may bring about starkly different conclusions. As a specific example, this contrast is illustrated using the 3GPP Long-Term Evolution system design.
Frozen Footprints
Venue: arXiv cs.DL 2009
Year: 2009

Bibliometrics has the ambitious goal of measuring science. To this end, it exploits the way science is disseminated trough scientific publications and the resulting citation network of scientific papers. We survey the main historical contributions to the field, the most interesting bibliometric indicators, and the most popular bibliometric data sources. Moreover, we discuss distributions commonly used to model bibliometric phenomena and give an overview of methods to build bibliometric maps of science.
Two-way source coding with a helper
Venue: arXiv cs.IT 2009
Year: 2009

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions where a Markov form (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the "further" user, namely, User 2. We derive these regions explicitly for the Gaussian sources with square error distortion, analyze a trade-off between the rate from the helper and the rate from the source, and examine a special case where the helper has the freedom to send different messages, at different rates, to the encoder and the decoder.
Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs
Venue: arXiv cs.DS 2009
Year: 2009

We propose an improved algorithm for counting the number of Hamiltonian cycles in a directed graph. The basic idea of the method is sequential acceptance/rejection, which is successfully used in approximating the number of perfect matchings in dense bipartite graphs. As a consequence, a new bound on the number of Hamiltonian cycles in a directed graph is proved, by using the ratio of the number of 1-factors. Based on this bound, we prove that our algorithm runs in expected time of $O(n^{8.5})$ for dense problems. This improves the Markov chain method, the most powerful existing method, a factor of at least $n^{4.5}(\log n)^{4}$ in running time. This class of dense problems is shown to be nontrivial in counting, in the sense that it is $#$P-Complete.
Complex Agent Networks explaining the HIV epidemic among homosexual men in Amsterdam
Venue: arXiv cs.MA 2009
Year: 2009

Simulating the evolution of the Human Immunodeficiency Virus (HIV) epidemic requires a detailed description of the population network, especially for small populations in which individuals can be represented in detail and accuracy. In this paper, we introduce the concept of a Complex Agent Network(CAN) to model the HIV epidemics by combining agent-based modelling and complex networks, in which agents represent individuals that have sexual interactions. The applicability of CANs is demonstrated by constructing and executing a detailed HIV epidemic model for men who have sex with men (MSM) in Amsterdam, including a distinction between steady and casual relationships. We focus on MSM contacts because they play an important role in HIV epidemics and have been tracked in Amsterdam for a long time. Our experiments show good correspondence between the historical data of the Amsterdam cohort and the simulation results.
Obtaining Depth Maps From Color Images By Region Based Stereo Matching Algorithms
Venue: arXiv cs.CV 2009
Year: 2009

In the paper, region based stereo matching algorithms are developed for extraction depth information from two color stereo image pair. A filter eliminating unreliable disparity estimation was used for increasing reliability of the disparity map. Obtained results by algorithms were represented and compared.
Secret Sharing over Fast-Fading MIMO Wiretap Channels
Venue: arXiv cs.IT 2009
Year: 2009

Secret sharing over the fast-fading MIMO wiretap channel is considered. A source and a destination try to share secret information over a fast-fading MIMO channel in the presence of a wiretapper who also makes channel observations that are different from but correlated to those made by the destination. An interactive authenticated unrestricted public channel is also available for use by the source and destination in the secret sharing process. This falls under the "channel-type model with wiretapper" considered by Ahlswede and Csiszar. A minor extension of their result (to continuous channel alphabets) is employed to evaluate the key capacity of the fast-fading MIMO wiretap channel. The effects of spatial dimensionality provided by the use of multiple antennas at the source, destination, and wiretapper are then investigated.
Geometric scaling: a simple preconditioner for certain linear systems with discontinuous coefficients
Venue: arXiv cs.MS 2009
Year: 2009

Linear systems with large differences between coefficients ("discontinuous coefficients") arise in many cases in which partial differential equations(PDEs) model physical phenomena involving heterogeneous media. The standard approach to solving such problems is to use domain decomposition techniques, with domain boundaries conforming to the boundaries between the different media. This approach can be difficult to implement when the geometry of the domain boundaries is complicated or the grid is unstructured. This work examines the simple preconditioning technique of scaling the equations by dividing each equation by the Lp-norm of its coefficients. This preconditioning is called geometric scaling (GS). It has long been known that diagonal scaling can be useful in improving convergence, but there is no study on the general usefulness of this approach for discontinuous coefficients. GS was tested on several nonsymmetric linear systems with discontinuous coefficients derived from convection-diffusion elliptic PDEs with small to moderate convection terms. It is shown that GS improved the convergence properties of restarted GMRES and Bi-CGSTAB, with and without the ILUT preconditioner. GS was also shown to improve the distribution of the eigenvalues by reducing their concentration around the origin very significantly.
Bayesian Compressive Sensing via Belief Propagation
Venue: arXiv cs.IT 2009
Year: 2009

Compressive sensing (CS) is an emerging field based on the revelation that a small collection of linear projections of a sparse signal contains enough information for stable, sub-Nyquist signal acquisition. When a statistical characterization of the signal is available, Bayesian inference can complement conventional CS methods based on linear programming or greedy algorithms. We perform approximate Bayesian inference using belief propagation (BP) decoding, which represents the CS encoding matrix as a graphical model. Fast computation is obtained by reducing the size of the graphical model with sparse encoding matrices. To decode a length-N signal containing K large coefficients, our CS-BP decoding algorithm uses O(Klog(N)) measurements and O(Nlog^2(N)) computation. Finally, although we focus on a two-state mixture Gaussian model, CS-BP is easily adapted to other signal models.
Error-Trellis State Complexity of LDPC Convolutional Codes Based on Circulant Matrices
Venue: arXiv cs.IT 2009
Year: 2009

Let H(D) be the parity-check matrix of an LDPC convolutional code corresponding to the parity-check matrix H of a QC code obtained using the method of Tanner et al. We see that the entries in H(D) are all monomials and several rows (columns) have monomial factors. Let us cyclically shift the rows of H. Then the parity-check matrix H'(D) corresponding to the modified matrix H' defines another convolutional code. However, its free distance is lower-bounded by the minimum distance of the original QC code. Also, each row (column) of H'(D) has a factor different from the one in H(D). We show that the state-space complexity of the error-trellis associated with H'(D) can be significantly reduced by controlling the row shifts applied to H with the error-correction capability being preserved.
Importance Weighted Active Learning
Venue: arXiv cs.LG 2009
Year: 2009

We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. Experiments on passively labeled data show that this approach reduces the label complexity required to achieve good predictive performance on many learning problems.
Experience versus Talent Shapes the Structure of the Web
Venue: arXiv cs.CY 2009
Year: 2009

We use sequential large-scale crawl data to empirically investigate and validate the dynamics that underlie the evolution of the structure of the web. We find that the overall structure of the web is defined by an intricate interplay between experience or entitlement of the pages (as measured by the number of inbound hyperlinks a page already has), inherent talent or fitness of the pages (as measured by the likelihood that someone visiting the page would give a hyperlink to it), and the continual high rates of birth and death of pages on the web. We find that the web is conservative in judging talent and the overall fitness distribution is exponential, showing low variability. The small variance in talent, however, is enough to lead to experience distributions with high variance: The preferential attachment mechanism amplifies these small biases and leads to heavy-tailed power-law (PL) inbound degree distributions over all pages, as well as over pages that are of the same age. The balancing act between experience and talent on the web allows newly introduced pages with novel and interesting content to grow quickly and surpass older pages. In this regard, it is much like what we observe in high-mobility and meritocratic societies: People with entitlement continue to have access to the best resources, but there is just enough screening for fitness that allows for talented winners to emerge and join the ranks of the leaders. Finally, we show that the fitness estimates have potential practical applications in ranking query results.
Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains
Venue: arXiv cs.DS 2009
Year: 2009

We study generalized fixed-point equations over idempotent semirings and provide an efficient algorithm for the detection whether a sequence of Kleene's iterations stabilizes after a finite number of steps. Previously known approaches considered only bounded semirings where there are no infinite descending chains. The main novelty of our work is that we deal with semirings without the boundedness restriction. Our study is motivated by several applications from interprocedural dataflow analysis. We demonstrate how the reachability problem for weighted pushdown automata can be reduced to solving equations in the framework mentioned above and we describe a few applications to demonstrate its usability.
Multidimensional Flash Codes
Venue: arXiv cs.IT 2009
Year: 2009

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different levels corresponding to the number of electrons it contains. Increasing the cell level is easy; however, reducing a cell level forces all the other cells in the same block to be erased. This erasing operation is undesirable and therefore has to be used as infrequently as possible. We consider the problem of designing codes for this purpose, where k bits are stored using a block of n cells with q levels each. The goal is to maximize the number of bit writes before an erase operation is required. We present an efficient construction of codes that can store an arbitrary number of bits. Our construction can be viewed as an extension to multiple dimensions of the earlier work of Jiang and Bruck, where single-dimensional codes that can store only 2 bits were proposed.
Identification with Encrypted Biometric Data
Venue: arXiv cs.CR 2009
Year: 2009

Biometrics make human identification possible with a sample of a biometric trait and an associated database. Classical identification techniques lead to privacy concerns. This paper introduces a new method to identify someone using his biometrics in an encrypted way. Our construction combines Bloom Filters with Storage and Locality-Sensitive Hashing. We apply this error-tolerant scheme, in a Hamming space, to achieve biometric identification in an efficient way. This is the first non-trivial identification scheme dealing with fuzziness and encrypted data.
N-norm and N-conorm in Neutrosophic Logic and Set, and the Neutrosophic Topologies
Venue: arXiv cs.AI 2009
Year: 2009

In this paper we present the N-norms/N-conorms in neutrosophic logic and set as extensions of T-norms/T-conorms in fuzzy logic and set. Also, as an extension of the Intuitionistic Fuzzy Topology we present the Neutrosophic Topologies.