OpenRaiser/Intern-Atlas huggingface dataset:
An additive combinatorics approach to the log-rank conjecture in communication complexity
Venue: arXiv cs.CC 2011
Year: 2011

For a $\{0,1\}$-valued matrix $M$ let $\rm{CC}(M)$ denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovász and Saks [FOCS 1988] states that $\rm{CC}(M) \leq \log^c(\rm{rank}(M))$ for some absolute constant $c$ where $\rm{rank}(M)$ denotes the rank of $M$ over the field of real numbers. We show that $\rm{CC}(M)\leq c \cdot \rm{rank}(M)/\log \rm{rank}(M)$ for some absolute constant $c$, assuming a well-known conjecture from additive combinatorics known as the Polynomial Freiman-Ruzsa (PFR) conjecture. Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, where this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].
A note on the expressive power of linear orders
Venue: arXiv cs.LO 2011
Year: 2011

This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order logic with a linear order and this permutation is as expressive as FO(Bit).
Fast Distributed Computation of Distances in Networks
Venue: arXiv cs.DC 2011
Year: 2011

This paper presents a distributed algorithm to simultaneously compute the diameter, radius and node eccentricity in all nodes of a synchronous network. Such topological information may be useful as input to configure other algorithms. Previous approaches have been modular, progressing in sequential phases using building blocks such as BFS tree construction, thus incurring longer executions than strictly required. We present an algorithm that, by timely propagation of available estimations, achieves a faster convergence to the correct values. We show local criteria for detecting convergence in each node. The algorithm avoids the creation of BFS trees and simply manipulates sets of node ids and hop counts. For the worst scenario of variable start times, each node i with eccentricity ecc(i) can compute: the node eccentricity in diam(G)+ecc(i)+2 rounds; the diameter in 2*diam(G)+ecc(i)+2 rounds; and the radius in diam(G)+ecc(i)+2*radius(G) rounds.
Robust Max-Product Belief Propagation
Venue: arXiv cs.CE 2011
Year: 2011

We study the problem of optimizing a graph-structured objective function under \emph{adversarial} uncertainty. This problem can be modeled as a two-persons zero-sum game between an Engineer and Nature. The Engineer controls a subset of the variables (nodes in the graph), and tries to assign their values to maximize an objective function. Nature controls the complementary subset of variables and tries to minimize the same objective. This setting encompasses estimation and optimization problems under model uncertainty, and strategic problems with a graph structure. Von Neumann's minimax theorem guarantees the existence of a (minimax) pair of randomized strategies that provide optimal robustness for each player against its adversary. We prove several structural properties of this strategy pair in the case of graph-structured payoff function. In particular, the randomized minimax strategies (distributions over variable assignments) can be chosen in such a way to satisfy the Markov property with respect to the graph. This significantly reduces the problem dimensionality. Finally we introduce a message passing algorithm to solve this minimax problem. The algorithm generalizes max-product belief propagation to this new domain.
Efficient and Universal Corruption Resilient Fountain Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we present a new family of fountain codes which overcome adversarial errors. That is, we consider the possibility that some portion of the arriving packets of a rateless erasure code are corrupted in an undetectable fashion. In practice, the corrupted packets may be attributed to a portion of the communication paths which are controlled by an adversary or to a portion of the sources that are malicious. The presented codes resemble and extend LT and Raptor codes. Yet, their benefits over existing coding schemes are manifold. First, to overcome the corrupted packets, our codes use information theoretic techniques, rather than cryptographic primitives. Thus, no secret channel between the senders and the receivers is required. Second, the encoders in the suggested scheme are oblivious to the strength of the adversary, yet perform as if its strength was known in advance. Third, the sparse structure of the codes facilitates efficient decoding. Finally, the codes easily fit a decentralized scenario with several sources, when no communication between the sources is allowed. We present both exhaustive as well as efficient decoding rules. Beyond the obvious use as a rateless codes, our codes have important applications in distributed computing.
Improving the Load Balancing Performance of Vlasiator
Venue: arXiv cs.DC 2011
Year: 2011

This whitepaper describes the load-balancing performance issues that are observed and tackled during the petascaling of the Vlasiator codes. Vlasiator is a Vlasov-hybrid simulation code developed in Finnish Meteorological Institute (FMI). Vlasiator models the communications associated with the spatial grid operated on as a hypergraph and partitions the grid using the parallel hypergraph partitioning scheme (PHG) of the Zoltan partitioning framework. The result of partitioning determines the distribution of grid cells to processors. It is observed that the partitioning phase takes a substantial percentage of the overall computation time. Alternative (graph-partitioning-based) schemes that perform almost as well as the hypergraph partitioning scheme and that require less preprocessing overhead and better balance are proposed and investigated. A comparison in terms of effect on running time, preprocessing overhead and load-balancing quality of Zoltan's PHG, ParMeTiS, and PT-SCOTCH are presented. Test results on Jüelich BlueGene/P cluster are presented.
3D Model Retrieval Based on Semantic and Shape Indexes
Venue: arXiv cs.IR 2011
Year: 2011

The size of 3D models used on the web or stored in databases is becoming increasingly high. Then, an efficient method that allows users to find similar 3D objects for a given 3D model query has become necessary. Keywords and the geometry of a 3D model cannot meet the needs of users' retrieval because they do not include the semantic information. In this paper, a new method has been proposed to 3D models retrieval using semantic concepts combined with shape indexes. To obtain these concepts, we use the machine learning methods to label 3D models by k-means algorithm in measures and shape indexes space. Moreover, semantic concepts have been organized and represented by ontology language OWL and spatial relationships are used to disambiguate among models of similar appearance. The SPARQL query language has been used to question the information displayed in this language and to compute the similarity between two 3D models. We interpret our results using the Princeton Shape Benchmark Database and the results show the performance of the proposed new approach to retrieval 3D models. Keywords: 3D Model, 3D retrieval, measures, shape indexes, semantic, ontology
Efficient Dense Gaussian Elimination over the Finite Field with Two Elements
Venue: arXiv cs.MS 2011
Year: 2011

In this work we describe an efficient implementation of a hierarchy of algorithms for Gaussian elimination upon dense matrices over the field with two elements. We discuss both well-known and new algorithms as well as our implementations in the M4RI library, which has been adopted into Sage. The focus of our discussion is a block iterative algorithm for PLE decomposition which is inspired by the M4RI algorithm. The implementation presented in this work provides considerable performance gains in practice when compared to the previously fastest implementation. We provide performance figures on x86_64 CPUs to demonstrate the alacrity of our approach.
Exploring Twitter Hashtags
Venue: arXiv cs.CL 2011
Year: 2011

Twitter messages often contain so-called hashtags to denote keywords related to them. Using a dataset of 29 million messages, I explore relations among these hashtags with respect to co-occurrences. Furthermore, I present an attempt to classify hashtags into five intuitive classes, using a machine-learning approach. The overall outcome is an interactive Web application to explore Twitter hashtags.
A Markov Random Field Topic Space Model for Document Retrieval
Venue: arXiv cs.IR 2011
Year: 2011

This paper proposes a novel statistical approach to intelligent document retrieval. It seeks to offer a more structured and extensible mathematical approach to the term generalization done in the popular Latent Semantic Analysis (LSA) approach to document indexing. A Markov Random Field (MRF) is presented that captures relationships between terms and documents as probabilistic dependence assumptions between random variables. From there, it uses the MRF-Gibbs equivalence to derive joint probabilities as well as local probabilities for document variables. A parameter learning method is proposed that utilizes rank reduction with singular value decomposition in a matter similar to LSA to reduce dimensionality of document-term relationships to that of a latent topic space. Experimental results confirm the ability of this approach to effectively and efficiently retrieve documents from substantial data sets.
Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position
Venue: arXiv cs.CG 2011
Year: 2011

The interference at a wireless node s can be modelled by the number of wireless nodes whose transmission ranges cover s. Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum interference. We consider the model introduced by von Rickenback et al. (2005), in which each transmission range is represented by a ball and edges in the communication graph are symmetric. The problem is NP-complete in two dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. Furthermore, even in one dimension (the highway model), the problem's complexity is unknown and the maximum interference of a set of n wireless nodes can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we show how to solve the problem efficiently in settings typical for wireless ad hoc networks. In particular, we show that if node positions are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, for any fixed d, then the topology given by the closure of the Euclidean minimum spanning tree of P has maximum interference O(log n) with high probability. We extend this bound to a general class of communication graphs over a broad set of probability distributions. Next we present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on the expected maximum interference. Finally, we discuss an empirical evaluation of our algorithm with a suite of simulation results.
An Enhanced Indexing And Ranking Technique On The Semantic Web
Venue: arXiv cs.AI 2011
Year: 2011

With the fast growth of the Internet, more and more information is available on the Web. The Semantic Web has many features which cannot be handled by using the traditional search engines. It extracts metadata for each discovered Web documents in RDF or OWL formats, and computes relations between documents. We proposed a hybrid indexing and ranking technique for the Semantic Web which finds relevant documents and computes the similarity among a set of documents. First, it returns with the most related document from the repository of Semantic Web Documents (SWDs) by using a modified version of the ObjectRank technique. Then, it creates a sub-graph for the most related SWDs. Finally, It returns the hubs and authorities of these document by using the HITS algorithm. Our technique increases the quality of the results and decreases the execution time of processing the user's query.
From Good Practices to Effective Policies for Preventing Errors in Spreadsheets
Venue: arXiv cs.SE 2011
Year: 2011

Thanks to the enormous flexibility they provide, spreadsheets are considered a priceless blessing by many end-users. Many spreadsheets, however, contain errors which can lead to severe consequences in some cases. To manage these risks, quality managers in companies are often asked to develop appropriate policies for preventing spreadsheet errors. Good policies should specify rules which are based on "known-good" practices. While there are many proposals for such practices in literature written by practitioners and researchers, they are often not consistent with each other. Therefore no general agreement has been reached yet and no science-based "golden rules" have been published. This paper proposes an expert-based, retrospective approach to the identification of good practices for spreadsheets. It is based on an evaluation loop that cross-validates the findings of human domain experts against rules implemented in a semi-automated spreadsheet workbench, taking into account the context in which the spreadsheets are used.
A Platform for Spreadsheet Composition
Venue: arXiv cs.SE 2011
Year: 2011

A huge amount of data is everyday managed in large organizations in many critical business sectors with the support of spreadsheet applications. The process of elaborating spreadsheet data is often performed in a distributed, collaborative way, where many actors enter data belonging to their local business domain to contribute to a global business view. The manual fusion of such data may lead to errors in copy-paste operations, loss of alignment and coherency due to multiple spreadsheet copies in circulation, as well as loss of data due to broken cross-spreadsheet links. In this paper we describe a methodology, based on a Spreadsheet Composition Platform, which greatly reduces these risks. The proposed platform seamlessly integrates the distributed spreadsheet elaboration, supports the commonly known spreadsheet tools for data processing and helps organizations to adopt a more controlled and secure environment for data fusion.
Multi-Gateway Cooperation in Multibeam Satellite Systems
Venue: arXiv cs.IT 2011
Year: 2011

Multibeam systems with hundreds of beams have been recently deployed in order to provide higher capacities by employing fractional frequency reuse. Furthermore, employing full frequency reuse and precoding over multiple beams has shown great throughput potential in literature. However, feeding all this data from a single gateway is not feasible based on the current frequency allocations. In this context, we investigate a range of scenarios involving beam clusters where each cluster is managed by a single gateway. More specifically, the following cases are considered for handling intercluster interference: a) conventional frequency colouring, b) joint processing within cluster, c) partial CSI sharing among clusters, d) partial CSI and data sharing among clusters. CSI sharing does not provide considerable performance gains with respect to b) but combined with data sharing offers roughly a 40% improvement over a) and a 15% over b).
Non-cooperative Feedback Rate Control Game for Channel State Information in Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

It has been well recognized that channel state information (CSI) feedback is of great importance for dowlink transmissions of closed-loop wireless networks. However, the existing work typically researched the CSI feedback problem for each individual mobile station (MS), and thus, cannot efficiently model the interactions among self-interested mobile users in the network level. To this end, in this paper, we propose an alternative approach to investigate the CSI feedback rate control problem in the analytical setting of a game theoretic framework, in which a multiple-antenna base station (BS) communicates with a number of co-channel MSs through linear precoder. Specifically, we first present a non-cooperative feedback-rate control game (NFC), in which each MS selects the feedback rate to maximize its performance in a distributed way. To improve efficiency from a social optimum point of view, we then introduce pricing, called the non-cooperative feedback-rate control game with price (NFCP). The game utility is defined as the performance gain by CSI feedback minus the price as a linear function of the CSI feedback rate. The existence of the Nash equilibrium of such games is investigated, and two types of feedback protocols (FDMA and CSMA) are studied. Simulation results show that by adjusting the pricing factor, the distributed NFCP game results in close optimal performance compared with that of the centralized scheme.
Joint Relay and Jammer Selection for Secure Two-Way Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate joint relay and jammer selection in two-way cooperative networks, consisting of two sources, a number of intermediate nodes, and one eavesdropper, with the constraints of physical layer security. Specifically, the proposed algorithms select two or three intermediate nodes to enhance security against the malicious eavesdropper. The first selected node operates in the conventional relay mode and assists the sources to deliver their data to the corresponding destinations using an amplify-and-forward protocol. The second and third nodes are used in different communication phases as jammers in order to create intentional interference upon the eavesdropper node. Firstly, we find that in a topology where the intermediate nodes are randomly and sparsely distributed, the proposed schemes with cooperative jamming outperform the conventional non-jamming schemes within a certain transmitted power regime. We also find that, in the scenario in which the intermediate nodes gather as a close cluster, the jamming schemes may be less effective than their non-jamming counterparts. Therefore, we introduce a hybrid scheme to switch between jamming and non-jamming modes. Simulation results validate our theoretical analysis and show that the hybrid switching scheme further improves the secrecy rate.
Sequentiality vs. Concurrency in Games and Logic
Venue: arXiv cs.LO 2011
Year: 2011

Connections between the sequentiality/concurrency distinction and the semantics of proofs are investigated, with particular reference to games and Linear Logic.
Optoelectronic Reservoir Computing
Venue: arXiv cs.ET 2011
Year: 2011

Reservoir computing is a recently introduced, highly efficient bio-inspired approach for processing time dependent data. The basic scheme of reservoir computing consists of a non linear recurrent dynamical system coupled to a single input layer and a single output layer. Within these constraints many implementations are possible. Here we report an opto-electronic implementation of reservoir computing based on a recently proposed architecture consisting of a single non linear node and a delay line. Our implementation is sufficiently fast for real time information processing. We illustrate its performance on tasks of practical importance such as nonlinear channel equalization and speech recognition, and obtain results comparable to state of the art digital implementations.
Towards Designing a Biometric Measure for Enhancing ATM Security in Nigeria E-Banking System
Venue: arXiv cs.CR 2011
Year: 2011

Security measures at banks can play a critical, contributory role in preventing attacks on customers. These measures are of paramount importance when considering vulnerabilities and causation in civil litigation. Banks must meet certain standards in order to ensure a safe and secure banking environment for their customers. This paper focuses on vulnerabilities and the increasing wave of criminal activities occurring at Automated Teller Machines (ATMs) where quick cash is the prime target for criminals rather than at banks themselves. A biometric measure as a means of enhancing the security has emerged from the discourse. Keywords-Security, ATM, Biometric, Crime.
Invariant texture analysis through Local Binary Patterns
Venue: arXiv cs.CV 2011
Year: 2011

In many image processing applications, such as segmentation and classification, the selection of robust features descriptors is crucial to improve the discrimination capabilities in real world scenarios. In particular, it is well known that image textures constitute power visual cues for feature extraction and classification. In the past few years the local binary pattern (LBP) approach, a texture descriptor method proposed by Ojala et al., has gained increased acceptance due to its computational simplicity and more importantly for encoding a powerful signature for describing textures. However, the original algorithm presents some limitations such as noise sensitivity and its lack of rotational invariance which have led to many proposals or extensions in order to overcome such limitations. In this paper we performed a quantitative study of the Ojala's original LBP proposal together with other recently proposed LBP extensions in the presence of rotational, illumination and noisy changes. In the experiments we have considered two different databases: Brodatz and CUReT for different sizes of LBP masks. Experimental results demonstrated the effectiveness and robustness of the described texture descriptors for images that are subjected to geometric or radiometric changes.
A model of Cross Language Retrieval for IT domain papers through a map of ACM Computing Classification System
Venue: arXiv cs.DL 2011
Year: 2011

This article presents a concept model, and the associated tool to help advanced learners to find adapted bibliography. The purpose is the use of an IT representation as educational research software for newcomers in research. We use an ontology based on the ACM's Computing Classification System in order to find scientific articles directly related to the new researcher's domain without any formal request. An ontology translation in French is automatically proposed and can be based on Web 2.0 enhanced by a community of users. A visualization and navigation model is proposed to make it more accessible and examples are given to show the interface of our tool: Ontology Navigator.
Statistical Sign Language Machine Translation: from English written text to American Sign Language Gloss
Venue: arXiv cs.CL 2011
Year: 2011

This works aims to design a statistical machine translation from English text to American Sign Language (ASL). The system is based on Moses tool with some modifications and the results are synthesized through a 3D avatar for interpretation. First, we translate the input text to gloss, a written form of ASL. Second, we pass the output to the WebSign Plug-in to play the sign. Contributions of this work are the use of a new couple of language English/ASL and an improvement of statistical machine translation based on string matching thanks to Jaro-distance.