OpenRaiser/Intern-Atlas huggingface dataset:
Learning to Place New Objects
Venue: arXiv cs.RO 2011
Year: 2011

The ability to place objects in the environment is an important skill for a personal robot. An object should not only be placed stably, but should also be placed in its preferred location/orientation. For instance, a plate is preferred to be inserted vertically into the slot of a dish-rack as compared to be placed horizontally in it. Unstructured environments such as homes have a large variety of object types as well as of placing areas. Therefore our algorithms should be able to handle placing new object types and new placing areas. These reasons make placing a challenging manipulation task. In this work, we propose a supervised learning algorithm for finding good placements given the point-clouds of the object and the placing area. It learns to combine the features that capture support, stability and preferred placements using a shared sparsity structure in the parameters. Even when neither the object nor the placing area is seen previously in the training set, our algorithm predicts good placements. In extensive experiments, our method enables the robot to stably place several new objects in several new placing areas with 98% success-rate; and it placed the objects in their preferred placements in 92% of the cases.
Asynchronous Physical-layer Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

A key issue in physical-layer network coding (PNC) is how to deal with the asynchrony between signals transmitted by multiple transmitters. That is, symbols transmitted by different transmitters could arrive at the receiver with symbol misalignment as well as relative carrier-phase offset. A second important issue is how to integrate channel coding with PNC to achieve reliable communication. This paper investigates these two issues and makes the following contributions: 1) We propose and investigate a general framework for decoding at the receiver based on belief propagation (BP). The framework can effectively deal with symbol and phase asynchronies while incorporating channel coding at the same time. 2) For unchannel-coded PNC, we show that for BPSK and QPSK modulations, our BP method can significantly reduce the asynchrony penalties compared with prior methods. 3) For unchannel-coded PNC, with half symbol offset between the transmitters, our BP method can drastically reduce the performance penalty due to phase asynchrony, from more than 6 dB to no more than 1 dB. 4) For channel-coded PNC, with our BP method, both symbol and phase asynchronies actually improve the system performance compared with the perfectly synchronous case. Furthermore, the performance spread due to different combinations of symbol and phase offsets between the transmitters in channel-coded PNC is only around 1 dB. The implication of 3) is that if we could control the symbol arrival times at the receiver, it would be advantageous to deliberately introduce a half symbol offset in unchannel-coded PNC. The implication of 4) is that when channel coding is used, symbol and phase asynchronies are not major performance concerns in PNC.
A recursive field-normalized bibliometric performance indicator: An application to the field of library and information science
Venue: arXiv cs.DL 2011
Year: 2011

Two commonly used ideas in the development of citation-based research performance indicators are the idea of normalizing citation counts based on a field classification scheme and the idea of recursive citation weighing (like in PageRank-inspired indicators). We combine these two ideas in a single indicator, referred to as the recursive mean normalized citation score indicator, and we study the validity of this indicator. Our empirical analysis shows that the proposed indicator is highly sensitive to the field classification scheme that is used. The indicator also has a strong tendency to reinforce biases caused by the classification scheme. Based on these observations, we advise against the use of indicators in which the idea of normalization based on a field classification scheme and the idea of recursive citation weighing are combined.
Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
Venue: arXiv cs.SI 2011
Year: 2011

Studies of community structure and evolution in large social networks require a fast and accurate algorithm for community detection. As the size of analyzed communities grows, complexity of the community detection algorithm needs to be kept close to linear. The Label Propagation Algorithm (LPA) has the benefits of nearly-linear running time and easy implementation, thus it forms a good basis for efficient community detection methods. In this paper, we propose new update rule and label propagation criterion in LPA to improve both its computational efficiency and the quality of communities that it detects. The speed is optimized by avoiding unnecessary updates performed by the original algorithm. This change reduces significantly (by order of magnitude for large networks) the number of iterations that the algorithm executes. We also evaluate our generalization of the LPA update rule that takes into account, with varying strength, connections to the neighborhood of a node considering a new label. Experiments on computer generated networks and a wide range of social networks show that our new rule improves the quality of the detected communities compared to those found by the original LPA. The benefit of considering positive neighborhood strength is pronounced especially on real-world networks containing sufficiently large fraction of nodes with high clustering coefficient.
Delays and the Capacity of Continuous-time Channels
Venue: arXiv cs.IT 2011
Year: 2011

Any physical channel of communication offers two potential reasons why its capacity (the number of bits it can transmit in a unit of time) might be unbounded: (1) Infinitely many choices of signal strength at any given instant of time, and (2) Infinitely many instances of time at which signals may be sent. However channel noise cancels out the potential unboundedness of the first aspect, leaving typical channels with only a finite capacity per instant of time. The latter source of infinity seems less studied. A potential source of unreliability that might restrict the capacity also from the second aspect is delay: Signals transmitted by the sender at a given point of time may not be received with a predictable delay at the receiving end. Here we examine this source of uncertainty by considering a simple discrete model of delay errors. In our model the communicating parties get to subdivide time as microscopically finely as they wish, but still have to cope with communication delays that are macroscopic and variable. The continuous process becomes the limit of our process as the time subdivision becomes infinitesimal. We taxonomize this class of communication channels based on whether the delays and noise are stochastic or adversarial; and based on how much information each aspect has about the other when introducing its errors. We analyze the limits of such channels and reach somewhat surprising conclusions: The capacity of a physical channel is finitely bounded only if at least one of the two sources of error (signal noise or delay noise) is adversarial. In particular the capacity is finitely bounded only if the delay is adversarial, or the noise is adversarial and acts with knowledge of the stochastic delay. If both error sources are stochastic, or if the noise is adversarial and independent of the stochastic delay, then the capacity of the associated physical channel is infinite.
Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants
Venue: arXiv cs.CC 2011
Year: 2011

Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploies the Map/Reduce paradigm over a fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.
Diversity-multiplexing Gain Tradeoff: a Tool in Algebra?
Venue: arXiv cs.IT 2011
Year: 2011

Since the invention of space-time coding numerous algebraic methods have been applied in code design. In particular algebraic number theory and central simple algebras have been on the forefront of the research. In this paper we are turning the table and asking whether information theory can be used as a tool in algebra. We will first derive some corollaries from diversity-multiplexing gain (DMT) bounds by Zheng and Tse and later show how these results can be used to analyze the unit group of orders of certain division algebras. The authors do not claim that the algebraic results are new, but we do find that this interesting relation between algebra and information theory is quite surprising and worth pointing out.
Broadcast Channels with Delayed Finite-Rate Feedback: Predict or Observe?
Venue: arXiv cs.IT 2011
Year: 2011

Most multiuser precoding techniques require accurate transmitter channel state information (CSIT) to maintain orthogonality between the users. Such techniques have proven quite fragile in time-varying channels because the CSIT is inherently imperfect due to estimation and feedback delay, as well quantization noise. An alternative approach recently proposed by Maddah-Ali and Tse (MAT) allows for significant multiplexing gain in the multi-input single-output (MISO) broadcast channel (BC) even with transmit CSIT that is completely stale, i.e. uncorrelated with the current channel state. With $K$ users, their scheme claims to lose only a $\log(K)$ factor relative to the full $K$ degrees of freedom (DoF) attainable in the MISO BC with perfect CSIT for large $K$. However, their result does not consider the cost of the feedback, which is potentially very large in high mobility (short channel coherence time). In this paper, we more closely examine the MAT scheme and compare its DoF gain to single user transmission (which always achieves 1 DoF) and partial CSIT linear precoding (which achieves up to $K$). In particular, assuming the channel coherence time is $N$ symbol periods and the feedback delay is $N_{\rm fd}$ we show that when $N < (1+o(1)) K \log K$ (short coherence time), single user transmission performs best, whereas for $N> (1+o(1)) (N_{\rm fd}+ K / \log K)(1-\log^{-1}K)^{-1}$ (long coherence time), zero-forcing precoding outperforms the other two. The MAT scheme is optimal for intermediate coherence times, which for practical parameter choices is indeed quite a large and significant range, even accounting for the feedback cost.
Personal Marks and Community Certificates: Detecting Clones in Mobile Wireless Networks of Smart-Phones
Venue: arXiv cs.CR 2011
Year: 2011

We consider the problem of detecting clones in wireless mobile adhoc networks. We assume that one of the devices of the network has been cloned. Everything, including certificates and secret keys. This can happen quite easily, because of a virus that immediately after sending all the content of the infected device to the adversary destroys itself, or just because the owner has left his device unattended for a few minutes in a hostile environment. The problem is to detect this attack. We propose a solution in networks of mobile devices carried by individuals. These networks are composed by nodes that have the capability of using short-range communication technology like blue-tooth or Wi-Fi, where nodes are carried by mobile users, and where links appear and disappear according to the social relationships between the users. Our idea is to use social physical contacts, securely collected by wireless personal smart-phones, as a biometric way to authenticate the legitimate owner of the device and detect the clone attack. We introduce two mechanisms: Personal Marks and Community Certificates. Personal Marks is a simple cryptographic protocol that works very well when the adversary is an insider, a malicious node in the network that is part, or not very far, from the social community of the original device that has been cloned. Community Certificates work very well when the adversary is an outsider, a node that has the goal of using the stolen credentials when interacting with other nodes that are far in the social network from the original device. When combined, these mechanisms provide an excellent protection against this very strong attack. We prove our ideas and solutions with extensive simulations in a real world scenario-with mobility traces collected in a real life experiment
Scalably Scheduling Power-Heterogeneous Processors
Venue: arXiv cs.DS 2011
Year: 2011

We show that a natural online algorithm for scheduling jobs on a heterogeneous multiprocessor, with arbitrary power functions, is scalable for the objective function of weighted flow plus energy.
A Secure RFID Deactivation/Activation Mechanism for Supporting Customer Service and Consumer Shopping
Venue: arXiv cs.CR 2011
Year: 2011

RFID has been regarded as a time and money-saving solution for a wide variety of applications, such as manufacturing, supply chain management, and inventory control, etc. However, there are some security problems on RFID in the product managements. The most concerned issues are the tracking and the location privacy. Numerous scholars tried to solve these problems, but their proposals do not include the after-sales service. In this paper, we propose a purchase and after-sales service RFID scheme for shopping mall. The location privacy, confidentiality, data integrity, and some security protection are hold in this propose mechanism.
Ontological Crises in Artificial Agents' Value Systems
Venue: arXiv cs.AI 2011
Year: 2011

Decision-theoretic agents predict and evaluate the results of their actions using a model, or ontology, of their environment. An agent's goal, or utility function, may also be specified in terms of the states of, or entities within, its ontology. If the agent may upgrade or replace its ontology, it faces a crisis: the agent's original goal may not be well-defined with respect to its new ontology. This crisis must be resolved before the agent can make plans towards achieving its goals. We discuss in this paper which sorts of agents will undergo ontological crises and why we may want to create such agents. We present some concrete examples, and argue that a well-defined procedure for resolving ontological crises is needed. We point to some possible approaches to solving this problem, and evaluate these methods on our examples.
STiCMAC: A MAC Protocol for Robust Space-Time Coding in Cooperative Wireless LANs
Venue: arXiv cs.NI 2011
Year: 2011

Relay-assisted cooperative wireless communication has been shown to have significant performance gains over the legacy direct transmission scheme. Compared with single relay based cooperation schemes, utilizing multiple relays further improves the reliability and rate of transmissions. Distributed space-time coding (DSTC), as one of the schemes to utilize multiple relays, requires tight coordination between relays and does not perform well in a distributed environment with mobility. In this paper, a cooperative medium access control (MAC) layer protocol, called \emph{STiCMAC}, is designed to allow multiple relays to transmit at the same time in an IEEE 802.11 network. The transmission is based on a novel DSTC scheme called \emph{randomized distributed space-time coding} (\emph{R-DSTC}), which requires minimum coordination. Unlike conventional cooperation schemes that pick nodes with good links, \emph{STiCMAC} picks a \emph{transmission mode} that could most improve the end-to-end data rate. Any station that correctly receives from the source can act as a relay and participate in forwarding. The MAC protocol is implemented in a fully decentralized manner and is able to opportunistically recruit relays on the fly, thus making it \emph{robust} to channel variations and user mobility. Simulation results show that the network capacity and delay performance are greatly improved, especially in a mobile environment.
Voronoi Diagram: The Generator Recognition Problem
Venue: arXiv cs.CG 2011
Year: 2011

For the analysis of systems consisting of small, regular objects, the methods of mathematical morphology applied to images of these systems are well-suited. One of these methods is the use of Voronoi polygons. It was found that the Voronoi tessellation method represents a powerful tool for the analysis of thin film morphology and provides nanostructural information to many multi-particle assemblies. In these notes, several morphological algorithms are analyzed and we study how to join all of them to design a graphical user interface (GUI) that provides as input for the system the "AFM image" and interprets the output of the system in terms of errors and generators coordinates.
Community structure of complex software systems: Analysis and applications
Venue: arXiv cs.SI 2011
Year: 2011

Due to notable discoveries in the fast evolving field of complex networks, recent research in software engineering has also focused on representing software systems with networks. Previous work has observed that these networks follow scale-free degree distributions and reveal small-world phenomena, while we here explore another property commonly found in different complex networks, i.e. community structure. We adopt class dependency networks, where nodes represent software classes and edges represent dependencies among them, and show that these networks reveal a significant community structure, characterized by similar properties as observed in other complex networks. However, although intuitive and anticipated by different phenomena, identified communities do not exactly correspond to software packages. We empirically confirm our observations on several networks constructed from Java and various third party libraries, and propose different applications of community detection to software engineering.
A Methodology for Optimizing Multithreaded System Scalability on Multi-cores
Venue: arXiv cs.DC 2011
Year: 2011

We show how to quantify scalability with the Universal Scalability Law (USL) by applying it to performance measurements of memcached, J2EE, and Weblogic on multi-core platforms. Since commercial multicores are essentially black-boxes, the accessible performance gains are primarily available at the application level. We also demonstrate how our methodology can identify the most significant performance tuning opportunities to optimize application scalability, as well as providing an easy means for exploring other aspects of the multi-core system design space.
Performance of Hybrid Concatenated Trellis Codes CPFSK with Iterative Decoding over Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

Concatenation is a method of building long codes out of shorter ones, it attempts to meet the problem of decoding complexity by breaking the required computation into manageable segments. Concatenated Continuous Phase Frequency Shift Keying (CPFSK) facilitates powerful error correction. CPFSK also has the advantage of being bandwidth efficient and compatible with nonlinear amplifiers. Bandwidth efficient concatenated coded modulation schemes were designed for communication over Additive White Gaussian noise (AWGN), and Rayleigh fading channels. An analytical bounds on the performance of serial concatenated convolutional codes (SCCC), and parallel concatenated convolutionalcodes (PCCC), were derived as a base of comparison with the third category known as hybrid concatenated trellis codes scheme (HCTC). An upper bound to the average maximum-likelihood bit error probability of the three schemes were obtained. Design rules for the parallel, outer, and inner codes that maximize the interleaver's gain were discussed. Finally, a low complexity iterative decoding algorithm that yields a better performance is proposed.
Default-all is dangerous!
Venue: arXiv cs.DB 2011
Year: 2011

We show that the default-all propagation scheme for database annotations is dangerous. Dangerous here means that it can propagate annotations to the query output which are semantically irrelevant to the query the user asked. This is the result of considering all relationally equivalent queries and returning the union of their where-provenance in an attempt to define a propagation scheme that is insensitive to query rewriting. We propose an alternative query-rewrite-insensitive (QRI) where-provenance called minimum propagation. It is analogous to the minimum witness basis for why-provenance, straight-forward to evaluate, and returns all relevant and only relevant annotations.
A Geometric Approach to Matrix Ordering
Venue: arXiv cs.DS 2011
Year: 2011

We present a recursive way to partition hypergraphs which creates and exploits hypergraph geometry and is suitable for many-core parallel architectures. Such partitionings are then used to bring sparse matrices in a recursive Bordered Block Diagonal form (for processor-oblivious parallel LU decomposition) or recursive Separated Block Diagonal form (for cache-oblivious sparse matrix-vector multiplication). We show that the quality of the obtained partitionings and orderings is competitive by comparing obtained fill-in for LU decomposition with SuperLU (with better results for 8 of the 28 test matrices) and comparing cut sizes for sparse matrix-vector multiplication with Mondriaan (with better results for 4 of the 12 test matrices). The main advantage of the new method is its speed: it is on average 21.6 times faster than Mondriaan.
Citadel E-Learning: A New Dimension to Learning System
Venue: arXiv cs.CY 2011
Year: 2011

E-learning has been an important policy for education planners for many years in developed countries. This policy has been adopted by education in some developing countries; it is therefore expedient to study its emergence in the Nigerian education system. The birth of contemporary technology shows that there is higher requirement for education even in the work force. This has been an eye opener to importance of Education which conveniently can be achieved through E-learning. This work presents CITADEL E-learning approach to Nigeria institutions; its ubiquity, its implementations, its flexibility, portability, ease of use and feature that are synonymous to the standard of education in Nigeria and how it can be enhanced to improve learning for both educators and learners to help them in their learning endeavour.
Symbolic-manipulation constructions of Hilbert-space metrics in quantum mechanics
Venue: arXiv cs.SC 2011
Year: 2011

The problem of the determination of the Hilbert-space metric which renders a given Hamiltonian $H$ self-adjoint is addressed from the point of view of applicability of computer-assisted algebraic manipulations. An exactly solvable example of the so called Gegenbauerian quantum-lattice oscillator is recalled for the purpose. Both the construction of suitable metric (basically, the solution of the Dieudonne's operator equation) and the determination of its domain of positivity are shown facilitated by the symbolic algebraic manipulations and by MAPLE-supported numerics and graphics.
Improved Linear Programming Decoding using Frustrated Cycles
Venue: arXiv cs.IT 2011
Year: 2011

We consider transmission over a binary-input additive white Gaussian noise channel using low-density parity-check codes. One of the most popular techniques for decoding low-density parity-check codes is the linear programming decoder. In general, the linear programming decoder is suboptimal. I.e., the word error rate is higher than the optimal, maximum a posteriori decoder. In this paper we present a systematic approach to enhance the linear program decoder. More precisely, in the cases where the linear program outputs a fractional solution, we give a simple algorithm to identify frustrated cycles which cause the output of the linear program to be fractional. Then adding these cycles, adaptively to the basic linear program, we show improved word error rate performance.