OpenRaiser/Intern-Atlas huggingface dataset:
Tensor-SIFT based Earth Mover's Distance for Contour Tracking
Venue: arXiv cs.CV 2010
Year: 2010

Contour tracking in adverse environments is a challenging problem due to cluttered background, illumination variation, occlusion, and noise, among others. This paper presents a robust contour tracking method by contributing to some of the key issues involved, including (a) a region functional formulation and its optimization; (b) design of a robust and effective feature; and (c) development of an integrated tracking algorithm. First, we formulate a region functional based on robust Earth Mover's distance (EMD) with kernel density for distribution modeling, and propose a two-phase method for its optimization. In the first phase, letting the candidate contour be fixed, we express EMD as the transportation problem and solve it by the simplex algorithm. Next, using the theory of shape derivative, we make a perturbation analysis of the contour around the best solution to the transportation problem. This leads to a partial differential equation (PDE) that governs the contour evolution. Second, we design a novel and effective feature for tracking applications. We propose a dimensionality reduction method by tensor decomposition, achieving a low-dimensional description of SIFT features called Tensor-SIFT for characterizing local image region properties. Applicable to both color and gray-level images, Tensor-SIFT is very distinctive, insensitive to illumination changes, and noise. Finally, we develop an integrated algorithm that combines various techniques of the simplex algorithm, narrow-band level set and fast marching algorithms. Particularly, we introduce an inter-frame initialization method and a stopping criterion for the termination of PDE iteration. Experiments in challenging image sequences show that the proposed work has promising performance.
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
Venue: arXiv cs.CC 2010
Year: 2010

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests if C is identically zero. Klivans & Spielman (STOC 2001) observed that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005). We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time poly(nd^k), regardless of the base field. The only field for which polynomial time algorithms were previously known is F=Q (Kayal & Saraf, FOCS 2009, and Saxena & Seshadhri, FOCS 2010). This is the first blackbox algorithm for depth-3 circuits that does not use the rank based approaches of Karnin & Shpilka (CCC 2008). We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a sps(k,d,n) circuit to k variables, but preserves the identity structure.
Improved Social Welfare Bounds for GSP at Equilibrium
Venue: arXiv cs.GT 2010
Year: 2010

The Generalized Second Price auction is the primary method by which sponsered search advertisements are sold. We study the performance of this auction under various equilibrium concepts. In particular, we demonstrate that the Bayesian Price of Anarchy is at most $2(1-1/e)^{-1} \approx 3.16$, significantly improving upon previously known bounds. Our techniques are intuitively straightforward and extend in a number of ways. For one, our result extends to a bound on the performance of GSP at coarse correlated equilibria, which captures (for example) a repeated-auction setting in which agents apply regret-minimizing bidding strategies. In addition, our analysis is robust against the presence of byzantine agents who cannot be assumed to participate rationally. Additionally, we present tight bounds for the social welfare obtained at pure NE for the special case of an auction for 3 slots, and discuss potential methods for extending this analysis to an arbitrary number of slots.
The emergence of the physical world from information processing
Venue: arXiv cs.OH 2010
Year: 2010

This paper links the conjecture that the physical world is a virtual reality to the findings of modern physics. What is usually the subject of science fiction is here proposed as a scientific theory open to empirical evaluation. We know from physics how the world behaves, and from computing how information behaves, so whether the physical world arises from ongoing information processing is a question science can evaluate. A prima facie case for the virtual reality conjecture is presented. If a photon is a pixel on a multi-dimensional grid that gives rise to space, the speed of light could reflect its refresh rate. If mass, charge and energy all arise from processing, the many conservation laws of physics could reduce to a single law of dynamic information conservation. If the universe is a virtual reality, then its big bang creation could be simply when the system was booted up. Deriving core physics from information processing could reconcile relativity and quantum theory, with the former how processing creates the space-time operating system and the latter how it creates energy and matter applications.
Distributed Construction of the Critical Geometric Graph in Dense Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Wireless sensor networks are often modeled in terms of a dense deployment of smart sensor nodes in a two-dimensional region. Give a node deployment, the \emph{critical geometric graph (CGG)} over these locations (i.e., the connected \emph{geometric graph (GG)} with the smallest radius) is a useful structure since it provides the most accurate proportionality between hop-count and Euclidean distance. Hence, it can be used for GPS-free node localisation as well as minimum distance packet forwarding. It is also known to be asymptotically optimal for network transport capacity and power efficiency. In this context, we propose DISCRIT, a distributed and asynchronous algorithm for obtaining an approximation of the CGG on the node locations. The algorithm does not require the knowledge of node locations or internode distances, nor does it require pair-wise RSSI (Received Signal Strength Indication) measurements to be made. Instead, the algorithm makes use of successful Hello receipt counts (obtained during a Hello-protocol-based neighbour discovery process) as edge weights, along with a simple distributed min-max computation algorithm. In this paper, we first provide the theory for justifying the use of the above edge weights. Then we provide extensive simulation results to demonstrate the efficacy of DISCRIT in obtaining an approximation of the CGG. Finally, we show how the CGG obtained from DISCRIT performs when used in certain network self-organisation algorithms.
Catalan structures and Catalan pairs
Venue: arXiv cs.DM 2010
Year: 2010

A Catalan pair is a pair of binary relations (S,R) satisfying certain axioms. These objects are enumerated by the well-known Catalan numbers, and have been introduced with the aim of giving a common language to most of the structures counted by Catalan numbers. Here, we give a simple method to pass from the recursive definition of a generic Catalan structure to the recursive definition of the Catalan pair on the same structure, thus giving an automatic way to interpret Catalan structures in terms of Catalan pairs. We apply our method to many well-known Catalan structures, focusing on the meaning of the relations S and R in each considered case.
Realizable Paths and the NL vs L Problem
Venue: arXiv cs.CC 2010
Year: 2010

A celebrated theorem of Savitch states that NSPACE(S) is contained in DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch's theorem itself has not been improved in the last four decades, studying the space complexity of several special cases of ST-CONNECTIVITY has provided new insights into the space-bounded complexity classes. In this paper, we introduce new kind of graph connectivity problems which we call graph realizability problems. All of our graph realizability problems are generalizations of UNDIRECTED ST-CONNECTIVITY. ST-REALIZABILITY, the most general graph realizability problem, is LogCFL-complete. We define the corresponding complexity classes that lie between L and LogCFL and study their relationships. As special cases of our graph realizability problems we define two natural problems, BALANCED ST-CONNECTIVITY and POSITIVE BALANCED ST-CONNECTIVITY, that lie between L and NL. We present a deterministic O(lognloglogn) space algorithm for BALANCED ST-CONNECTIVITY. More generally we prove that SGSLogCFL, a generalization of BALANCED ST-CONNECTIVITY, is contained in DSPACE(lognloglogn). To achieve this goal we generalize several concepts (such as graph squaring and transitive closure) and algorithms (such as parallel algorithms) known in the context of UNDIRECTED ST-CONNECTIVITY.
Understanding Cascading Failures in Power Grids
Venue: arXiv cs.SI 2010
Year: 2010

In the past, we have observed several large blackouts, i.e. loss of power to large areas. It has been noted by several researchers that these large blackouts are a result of a cascade of failures of various components. As a power grid is made up of several thousands or even millions of components (relays, breakers, transformers, etc.), it is quite plausible that a few of these components do not perform their function as desired. Their failure/misbehavior puts additional burden on the working components causing them to misbehave, and thus leading to a cascade of failures. The complexity of the entire power grid makes it difficult to model each and every individual component and study the stability of the entire system. For this reason, it is often the case that abstract models of the working of the power grid are constructed and then analyzed. These models need to be computationally tractable while serving as a reasonable model for the entire system. In this work, we construct one such model for the power grid, and analyze it.
Progressive Decoding for Data Availability and Reliability in Distributed Networked Storage
Venue: arXiv cs.DC 2010
Year: 2010

To harness the ever growing capacity and decreasing cost of storage, providing an abstraction of dependable storage in the presence of crash-stop and Byzantine failures is compulsory. We propose a decentralized Reed Solomon coding mechanism with minimum communication overhead. Using a progressive data retrieval scheme, a data collector contacts only the necessary number of storage nodes needed to guarantee data integrity. The scheme gracefully adapts the cost of successful data retrieval to the number of storage node failures. Moreover, by leveraging the Welch-Berlekamp algorithm, it avoids unnecessary computations. Compared to the state-of-the-art decoding scheme, the implementation and evaluation results show that our progressive data retrieval scheme has up to 35 times better computation performance for low Byzantine node rates. Additionally, the communication cost in data retrieval is derived analytically and corroborated by Monte-Carlo simulation results. Our implementation is flexible in that the level of redundancy it provides is independent of the number of data generating nodes, a requirement for distributed storage systems
World of Movable Objects. Part 1
Venue: arXiv cs.HC 2010
Year: 2010

This book is about the transformation of screen objects into movable and resizable and about the design of applications entirely on the basis of such elements. The screen objects have a wide variety of shapes; they can be either graphical objects or controls; there are solitary objects and very complex objects parts of which are involved in individual, synchronous, and related movements. Objects can be involved in forward movements and rotation; they can be resized and reconfigured; all these movements and situations are considered. On the basis of total movability, the new type of programs - user-driven applications - are designed. These applications continue to work according to their main purposes, but the whole control of WHAT, WHEN, and HOW must appear on the screen is passed from designers to users. Due to the size restriction used on CoRR, the book is divided here into two parts and one appendix is deleted. At www.sourceforge.net in the project MoveableGraphics the whole book is available in a single file together with the accompanying application and source codes.
Cross-Composition: A New Technique for Kernelization Lower Bounds
Venue: arXiv cs.CC 2010
Year: 2010

We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem Q if an instance of Q with polynomially bounded parameter value can express the logical OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) we show that if an NP-complete problem cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless the polynomial hierarchy collapses. Our technique generalizes and strengthens the recent techniques of using OR-composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Chromatic Number, Clique, and Weighted Feedback Vertex Set do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set.
QoS-enabled ANFIS Dead Reckoning Algorithm for Distributed Interactive Simulation
Venue: arXiv cs.NI 2010
Year: 2010

Dead Reckoning mechanisms are usually used to estimate the position of simulated entity in virtual environment. However, this technique often ignores available contextual information that may be influential to the state of an entity, sacrificing remote predictive accuracy in favor of low computational complexity. A novel extension of Dead Reckoning is suggested in this paper to increase the network availability and fulfill the required Quality of Service in large scale distributed simulation application. The proposed algorithm is referred to as ANFIS Dead Reckoning, which stands for Adaptive Neuro-based Fuzzy Inference System Dead Reckoning is based on a fuzzy inference system which is trained by the learning algorithm derived from the neuronal networks and fuzzy inference theory. The proposed mechanism takes its based on the optimization approach to calculate the error threshold violation in networking games. Our model shows it primary benefits especially in the decision making of the behavior of simulated entities and preserving the consistence of the simulation.
Power Allocation Games in Wireless Networks of Multi-antenna Terminals
Venue: arXiv cs.IT 2010
Year: 2010

We consider wireless networks that can be modeled by multiple access channels in which all the terminals are equipped with multiple antennas. The propagation model used to account for the effects of transmit and receive antenna correlations is the unitary-invariant-unitary model, which is one of the most general models available in the literature. In this context, we introduce and analyze two resource allocation games. In both games, the mobile stations selfishly choose their power allocation policies in order to maximize their individual uplink transmission rates; in particular they can ignore some specified centralized policies. In the first game considered, the base station implements successive interference cancellation (SIC) and each mobile station chooses his best space-time power allocation scheme; here, a coordination mechanism is used to indicate to the users the order in which the receiver applies SIC. In the second framework, the base station is assumed to implement single-user decoding. For these two games a thorough analysis of the Nash equilibrium is provided: the existence and uniqueness issues are addressed; the corresponding power allocation policies are determined by exploiting random matrix theory; the sum-rate efficiency of the equilibrium is studied analytically in the low and high signal-to-noise ratio regimes and by simulations in more typical scenarios. Simulations show that, in particular, the sum-rate efficiency is high for the type of systems investigated and the performance loss due to the use of the proposed suboptimum coordination mechanism is very small.
Gaussian Broadcast Channels with an Orthogonal and Bidirectional Cooperation Link
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers a system where one transmitter broadcasts a single common message to two receivers linked by a bidirectional cooperation channel, which is assumed to be orthogonal to the downlink channel. Assuming a simplified setup where, in particular, scalar relaying protocols are used and channel coding is not exploited, we want to provide elements of response to several questions of practical interest. Here are the main underlying issues: 1. The way of recombining the signals at the receivers; 2. The optimal number of cooperation rounds; 3. The way of cooperating (symmetrically or asymmetrically; which receiver should start cooperating in the latter case); 4. The influence of spectral resources. These issues are considered by studying the performance of the assumed system through analytical results when they are derivable and through simulation results. For the particular choices we made, the results sometimes do not coincide with those available for the discrete counterpart of the studied channel.
Nonlinear threshold Boolean automata networks and phase transitions
Venue: arXiv cs.DM 2010
Year: 2010

In this report, we present a formal approach that addresses the problem of emergence of phase transitions in stochastic and attractive nonlinear threshold Boolean automata networks. Nonlinear networks considered are informally defined on the basis of classical stochastic threshold Boolean automata networks in which specific interaction potentials of neighbourhood coalition are taken into account. More precisely, specific nonlinear terms compose local transition functions that define locally the dynamics of such networks. Basing our study on nonlinear networks, we exhibit new results, from which we derive conditions of phase transitions.
Lossy Broadcasting in Two-Way Relay Networks with Common Reconstructions
Venue: arXiv cs.IT 2010
Year: 2010

The broadcast phase (downlink transmission) of the two-way relay network is studied in the source coding and joint source-channel coding settings. The rates needed for reliable communication are characterised for a number of special cases including: small distortions, deterministic distortion measures, and jointly Gaussian sources with quadratic distortion measures. The broadcast problem is also studied with common-reconstruction decoding constraints, and the rates needed for reliable communication are characterised for all discrete memoryless sources and per-letter distortion measures.
Analysis of Generalized Impact Factor and Indices of Journals
Venue: arXiv cs.DL 2010
Year: 2010

Analyzing the relationships among the parameters for quantifying the quality of research published in journals is a challenging task. In this paper, we analyze the relationships between impact factor, h-index, and g-index of a journal. To keep our analysis simple and easy to understand, we consider a generalized version of the impact factor where there is no time window. In the absence of the time window, the impact factor converges to the number of citations received per paper. This is not only justified for the impact factor, it simplifies the analysis of h-index and g-index as well because addition of a time window in the form of years complicates the computation of indices too. We derive the expressions for the relationships among impact factor, h-index, and g-index and validate them using a given set of publication-citation data.
Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing
Venue: arXiv cs.CG 2010
Year: 2010

We investigate the problem of finding reverse nearest neighbors efficiently. Although provably good solutions exist for this problem in low or fixed dimensions, to this date the methods proposed in high dimensions are mostly heuristic. We introduce a method that is both provably correct and efficient in all dimensions, based on a reduction of the problem to one instance of $\e$-nearest neighbor search plus a controlled number of instances of {\em exhaustive $r$-\pleb}, a variant of {\em Point Location among Equal Balls} where all the $r$-balls centered at the data points that contain the query point are sought for, not just one. The former problem has been extensively studied and elegantly solved in high dimensions using Locality-Sensitive Hashing (LSH) techniques. By contrast, the latter problem has a complexity that is still not fully understood. We revisit the analysis of the LSH scheme for exhaustive $r$-\pleb using a somewhat refined notion of locality-sensitive family of hash function, which brings out a meaningful output-sensitive term in the complexity of the problem. Our analysis, combined with a non-isometric lifting of the data, enables us to answer exhaustive $r$-\pleb queries (and down the road reverse nearest neighbors queries) efficiently. Along the way, we obtain a simple algorithm for answering exact nearest neighbor queries, whose complexity is parametrized by some {\em condition number} measuring the inherent difficulty of a given instance of the problem.
Optimal Utility-Energy tradeoff in Delay Constrained Random Access Networks
Venue: arXiv cs.IT 2010
Year: 2010

Rate, energy and delay are three main parameters of interest in ad-hoc networks. In this paper, we discuss the problem of maximizing network utility and minimizing energy consumption while satisfying a given transmission delay constraint for each packet. We formulate this problem in the standard convex optimization form and subsequently discuss the tradeoff between utility, energy and delay in such framework. Also, in order to adapt for the distributed nature of the network, a distributed algorithm where nodes decide on choosing transmission rates and probabilities based on their local information is introduced.
Energy and Utility Optimization in Wireless Networks with Random Access
Venue: arXiv cs.IT 2010
Year: 2010

Energy consumption is a main issue of concern in wireless networks. Energy minimization increases the time that networks' nodes work properly without recharging or substituting batteries. Another criterion for network performance is data transmission rate which is usually quantified by a network utility function. There exists an inherent tradeoff between these criteria and enhancing one of them can deteriorate the other one. In this paper, we consider both Network Utility Maximization (NUM) and energy minimization in a bi-criterion optimization problem. The problem is formulated for Random Access (RA) Medium Access Control (MAC) for ad-hoc networks. First, we optimize performance of the MAC and define utility as a monotonically increasing function of link throughputs. We investigate the optimal tradeoff between energy and utility in this part. In the second part, we define utility as a function of end to end rates and optimize MAC and transport layers simultaneously. We calculate optimal persistence probabilities and end-to-end rates. Finally, by means of duality theorem, we decompose the problem into smaller subproblems, which are solved at node and network layers separately. This decomposition avoids need for a central unit while sustaining benefits of layering.