OpenRaiser/Intern-Atlas huggingface dataset:
Hypothesize and Bound: A Computational Focus of Attention Mechanism for Simultaneous N-D Segmentation, Pose Estimation and Classification Using Shape Priors
Venue: arXiv cs.CV 2011
Year: 2011

Given the ever increasing bandwidth of the visual information available to many intelligent systems, it is becoming essential to endow them with a sense of what is worthwhile their attention and what can be safely disregarded. This article presents a general mathematical framework to efficiently allocate the available computational resources to process the parts of the input that are relevant to solve a given perceptual problem. By this we mean to find the hypothesis H (i.e., the state of the world) that maximizes a function L(H), representing how well each hypothesis "explains" the input. Given the large bandwidth of the sensory input, fully evaluating L(H) for each hypothesis H is computationally infeasible (e.g., because it would imply checking a large number of pixels). To address this problem we propose a mathematical framework with two key ingredients. The first one is a Bounding Mechanism (BM) to compute lower and upper bounds of L(H), for a given computational budget. These bounds are much cheaper to compute than L(H) itself, can be refined at any time by increasing the budget allocated to a hypothesis, and are frequently enough to discard a hypothesis. To compute these bounds, we develop a novel theory of shapes and shape priors. The second ingredient is a Focus of Attention Mechanism (FoAM) to select which hypothesis' bounds should be refined next, with the goal of discarding non-optimal hypotheses with the least amount of computation. The proposed framework: 1) is very efficient since most hypotheses are discarded with minimal computation; 2) is parallelizable; 3) is guaranteed to find the globally optimal hypothesis; and 4) its running time depends on the problem at hand, not on the bandwidth of the input. We instantiate the proposed framework for the problem of simultaneously estimating the class, pose, and a noiseless version of a 2D shape in a 2D image.
Distributed Stochastic Approximation for Constrained and Unconstrained Optimization
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we analyze the convergence of a distributed Robbins-Monro algorithm for both constrained and unconstrained optimization in multi-agent systems. The algorithm searches for local minima of a (nonconvex) objective function which is supposed to coincide with a sum of local utility functions of the agents. The algorithm under study consists of two steps: a local stochastic gradient descent at each agent and a gossip step that drives the network of agents to a consensus. It is proved that i) an agreement is achieved between agents on the value of the estimate, ii) the algorithm converges to the set of Kuhn-Tucker points of the optimization problem. The proof relies on recent results about differential inclusions. In the context of unconstrained optimization, intelligible sufficient conditions are provided in order to ensure the stability of the algorithm. In the latter case, we also provide a central limit theorem which governs the asymptotic fluctuations of the estimate. We illustrate our results in the case of distributed power allocation for ad-hoc wireless networks.
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
Venue: arXiv cs.DS 2011
Year: 2011

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1,...,M} or in a directed n-node graph with edge weights in {-M,..., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Theta(n)-node undirected graph with weights in {1,...,O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed by Itai and Rodeh [SIAM J. Computing 1978 and STOC'77]. A direct consequence of our efficient reductions are O (Mn^{omega})-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1,M] and directed graphs with integral weights from the interval [-M,M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M^{0.681}n^{2.575}) by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n^{3-eps})-time algorithm (eps>0) for minimum weight cycle immediately implies a O(n^{3-delta})-time algorithm (delta>0) for APSP.
A Coinductive Calculus for Asynchronous Side-effecting Processes
Venue: arXiv cs.LO 2011
Year: 2011

We present an abstract framework for concurrent processes in which atomic steps have generic side effects, handled according to the principle of monadic encapsulation of effects. Processes in this framework are potentially infinite resumptions, modelled using final coalgebras over the monadic base. As a calculus for such processes, we introduce a concurrent extension of Moggi's monadic metalanguage of effects. We establish soundness and completeness of a natural equational axiomatisation of this calculus. Moreover, we identify a corecursion scheme that is explicitly definable over the base language and provides flexible expressive means for the definition of new operators on processes, such as parallel composition. As a worked example, we prove the safety of a generic mutual exclusion scheme using a verification logic built on top of the equational calculus.
Subexponential convergence for information aggregation on regular trees
Venue: arXiv cs.MA 2011
Year: 2011

We consider the decentralized binary hypothesis testing problem on trees of bounded degree and increasing depth. For a regular tree of depth t and branching factor k>=2, we assume that the leaves have access to independent and identically distributed noisy observations of the 'state of the world' s. Starting with the leaves, each node makes a decision in a finite alphabet M, that it sends to its parent in the tree. Finally, the root decides between the two possible states of the world based on the information it receives. We prove that the error probability vanishes only subexponentially in the number of available observations, under quite general hypotheses. More precisely the case of binary messages, decay is subexponential for any decision rule. For general (finite) message alphabet M, decay is subexponential for 'node-oblivious' decision rules, that satisfy a mild irreducibility condition. In the latter case, we propose a family of decision rules with close-to-optimal asymptotic behavior.
Social Welfare in One-sided Matching Markets without Money
Venue: arXiv cs.GT 2011
Year: 2011

We study social welfare in one-sided matching markets where the goal is to efficiently allocate n items to n agents that each have a complete, private preference list and a unit demand over the items. Our focus is on allocation mechanisms that do not involve any monetary payments. We consider two natural measures of social welfare: the ordinal welfare factor which measures the number of agents that are at least as happy as in some unknown, arbitrary benchmark allocation, and the linear welfare factor which assumes an agent's utility linearly decreases down his preference lists, and measures the total utility to that achieved by an optimal allocation. We analyze two matching mechanisms which have been extensively studied by economists. The first mechanism is the random serial dictatorship (RSD) where agents are ordered in accordance with a randomly chosen permutation, and are successively allocated their best choice among the unallocated items. The second mechanism is the probabilistic serial (PS) mechanism of Bogomolnaia and Moulin [8], which computes a fractional allocation that can be expressed as a convex combination of integral allocations. The welfare factor of a mechanism is the infimum over all instances. For RSD, we show that the ordinal welfare factor is asymptotically 1/2, while the linear welfare factor lies in the interval [.526, 2/3]. For PS, we show that the ordinal welfare factor is also 1/2 while the linear welfare factor is roughly 2/3. To our knowledge, these results are the first non-trivial performance guarantees for these natural mechanisms.
Complexity of two-variable Dependence Logic and IF-Logic
Venue: arXiv cs.LO 2011
Year: 2011

We study the two-variable fragments D^2 and IF^2 of dependence logic and independence-friendly logic. We consider the satisfiability and finite satisfiability problems of these logics and show that for D^2, both problems are NEXPTIME-complete, whereas for IF^2, the problems are undecidable. We also show that D^2 is strictly less expressive than IF^2 and that already in D^2, equicardinality of two unary predicates and infinity can be expressed (the latter in the presence of a constant symbol). This is an extended version of a publication in the proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011).
Efficient Seeds Computation Revisited
Venue: arXiv cs.DS 2011
Year: 2011

The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions --- computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in $O(n^2)$ time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an $O(n\log{(n/m)})$ time algorithm checking if the shortest seed has length at least $m$ and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).
Query Expansion Based on Clustered Results
Venue: arXiv cs.IR 2011
Year: 2011

Query expansion is a functionality of search engines that suggests a set of related queries for a user-issued keyword query. Typical corpus-driven keyword query expansion approaches return popular words in the results as expanded queries. Using these approaches, the expanded queries may correspond to a subset of possible query semantics, and thus miss relevant results. To handle ambiguous queries and exploratory queries, whose result relevance is difficult to judge, we propose a new framework for keyword query expansion: we start with clustering the results according to user specified granularity, and then generate expanded queries, such that one expanded query is generated for each cluster whose result set should ideally be the corresponding cluster. We formalize this problem and show its APX-hardness. Then we propose two efficient algorithms named iterative single-keyword refinement and partial elimination based convergence, respectively, which effectively generate a set of expanded queries from clustered results that provide a classification of the original query results. We believe our study of generating an optimal query based on the ground truth of the query results not only has applications in query expansion, but has significance for studying keyword search quality in general.
Metamorphic Virus Detection in Portable Executables Using Opcodes Statistical Feature
Venue: arXiv cs.CR 2011
Year: 2011

Metamorphic viruses engage different mutation techniques to escape from string signature based scanning. They try to change their code in new offspring so that the variants appear non-similar and have no common sequences of string as signature. However, all versions of a metamorphic virus have similar task and performance. This obfuscation process helps to keep them safe from the string based signature detection. In this study, we make use of instructions statistical features to compare the similarity of two hosted files probably occupied by two mutated forms of a specific metamorphic virus. The introduced solution in this paper is relied on static analysis and employs the frequency histogram of machine opcodes in different instances of obfuscated viruses. We use Minkowski-form histogram distance measurements in order to check the likeness of portable executables (PE). The purpose of this research is to present an idea that for a number of special obfuscation approaches the presented solution can be used to identify morphed copies of a file. Thus, it can be applied by antivirus scanner to recognize different versions of a metamorphic virus.
An Effect of Spatial Filtering in Visualization of Coronary Arteries Imaging
Venue: arXiv cs.CV 2011
Year: 2011

At present, coronary angiography is the well known standard for the diagnosis of coronary artery disease. Conventional coronary angiography is an invasive procedure with a small, yet inherent risk of myocardial infarction, stroke, potential arrhythmias, and death. Other noninvasive diagnostic tools, such as electrocardiography, echocardiography, and nuclear imaging are now widely available but are limited by their inability to directly visualize and quantify coronary artery stenoses and predict the stability of plaques. Coronary magnetic resonance angiography (MRA) is a technique that allows visualization of the coronary arteries by noninvasive means; however, it has not yet reached a stage where it can be used in routine clinical practice. Although coronary MRA is a potentially useful diagnostic tool, it has limitations. Further research should focus on improving the diagnostic resolution and accuracy of coronary MRA. This paper will helps to cardiologists to take the clear look of spatial filtered imaging of coronary arteries.
Soft-In Soft-Out DFE and Bi-directional DFE
Venue: arXiv cs.IT 2011
Year: 2011

We design a soft-in soft-out (SISO) decision feedback equalizer (DFE) that performs better than its linear counterpart in turbo equalizer (TE) setting. Unlike previously developed SISO-DFEs, the present DFE scheme relies on extrinsic information formulation that directly takes into account the error propagation effect. With this new approach, both error rate simulation and the extrinsic information transfer (EXIT) chart analysis indicate that the proposed SISO-DFE is superior to the well-known SISO linear equalizer (LE). This result is in contrast with the general understanding today that the error propagation effect of the DFE degrades the overall TE performance below that of the TE based on a LE. We also describe a new extrinsic information combining strategy involving the outputs of two DFEs running in opposite directions, that explores error correlation between the two sets of DFE outputs. When this method is combined with the new DFE extrinsic information formulation, the resulting "bidirectional" turbo-DFE achieves excellent performance-complexity tradeoffs compared to the TE based on the BCJR algorithm or on the LE. Unlike turbo LE or turbo DFE, the turbo BiDFE's performance does not degrade significantly as the feedforward and feedback filter taps are constrained to be time-invariant.
Contracting Graphs to Paths and Trees
Venue: arXiv cs.DS 2011
Year: 2011

Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. Interestingly, the study of edge contraction problems of this type from a parameterized perspective has so far been left largely unexplored. We consider two basic edge contraction problems, which we call Path-Contractibility and Tree-Contractibility. Both problems take an undirected graph $G$ and an integer $k$ as input, and the task is to determine whether we can obtain a path or an acyclic graph, respectively, by contracting at most $k$ edges of $G$. Our main contribution is an algorithm with running time $4^{k+O(\log^2 k)} + n^{O(1)}$ for Path-Contractibility and an algorithm with running time $4.88^k n^{O(1)}$ for Tree-Contractibility, based on a novel application of the color coding technique of Alon, Yuster and Zwick. Furthermore, we show that Path-Contractibility has a kernel with at most $5k+3$ vertices, while Tree-Contractibility does not have a polynomial kernel unless coNP $\subseteq$ NP/poly. We find the latter result surprising, because of the strong connection between Tree-Contractibility and Feedback Vertex Set, which is known to have a vertex kernel with size $O(k^2)$.
Removing bias due to finite measurement of dynamic systems: case study on P2P systems
Venue: arXiv cs.NI 2011
Year: 2011

Mesurer avec précision la dynamique des graphes de terrain est une tâche difficile, car les propriétés observées peuvent être biaisées pour différentes raisons, en particulier le fait que la période de mesure soit finie. Dans ce papier, nous introduisons une méthodologie générale qui nous permet de savoir si la fenêtre d'observation est suffisamment longue pour caractériser une propriété donnée dans n'importe quel système dynamique. Nous appliquons cette méthodologie à l'étude des durées de sessions et des durées de vie des fichiers sur deux jeux de données P2P. Nous montrons que le comportement des propriétés est différent : pour les durées de sessions, notre méthodologie nous permet de caractériser avec précision la forme de leur distribution. Par contre, pour les durées de vie des fichiers, nous montrons que cette propriété ne peut pas être caractérisée, soit parce qu'elle n'est pas stationnaire, soit parce que la durée de notre mesure est trop courte.
How to Play Unique Games against a Semi-Random Adversary
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we study the average case complexity of the Unique Games problem. We propose a natural semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon) satisfiable instance, so then the problem is as hard as in the worst case. In our semi-random model, one of the steps is random, and all other steps are adversarial. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semi-random instances of Unique Games. We present an algorithm that with high probability finds a solution satisfying a (1-delta) fraction of all constraints in semi-random instances (we require that the average degree of the graph is Omega(log k). To this end, we consider a new non-standard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest. Our result holds only for epsilon less than some absolute constant. We prove that if epsilon > 1/2, then the problem is hard in one of the models, the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that with high probability, distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1-delta) satisfiable instance if epsilon > c delta.
Courcelle's Theorem - A Game-Theoretic Approach
Venue: arXiv cs.DS 2011
Year: 2011

Courcelle's Theorem states that every problem definable in Monadic Second-Order logic can be solved in linear time on structures of bounded treewidth, for example, by constructing a tree automaton that recognizes or rejects a tree decomposition of the structure. Existing, optimized software like the MONA tool can be used to build the corresponding tree automata, which for bounded treewidth are of constant size. Unfortunately, the constants involved can become extremely large - every quantifier alternation requires a power set construction for the automaton. Here, the required space can become a problem in practical applications. In this paper, we present a novel, direct approach based on model checking games, which avoids the expensive power set construction. Experiments with an implementation are promising, and we can solve problems on graphs where the automata-theoretic approach fails in practice.
Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO
Venue: arXiv cs.DC 2011
Year: 2011

A self-stabilizing protocol has the capacity to recover a legitimate behavior whatever is its initial state. The majority of works in self-stabilization assume a shared memory model or a communication using reliable and FIFO channels. In this article, we interest in self-stabilizing systems using bounded but non reliable and non FIFO channels. We propose a stabilizing communication protocol with optimal fault resilience. In more details, this protocol simulates a reliable and FIFO channel and ensures a minimal number of looses, duplications, creations, and re-ordering of messages.
Cramér-Rao Bound for Localization with A Priori Knowledge on Biased Range Measurements
Venue: arXiv cs.IT 2011
Year: 2011

This paper derives a general expression for the Cramér-Rao bound (CRB) of wireless localization algorithms using range measurements subject to bias corruption. Specifically, the a priori knowledge about which range measurements are biased, and the probability density functions (PDF) of the biases are assumed to be available. For each range measurement, the error due to estimating the time-of-arrival of the detected signal is modeled as a Gaussian distributed random variable with zero mean and known variance. In general, the derived CRB expression can be evaluated numerically. An approximate CRB expression is also derived when the bias PDF is very informative. Using these CRB expressions, we study the impact of the bias distribution on the mean square error (MSE) bound corresponding to the CRB. The analysis is corroborated by numerical experiments.
A Note on Parallel Algorithmic Speedup Bounds
Venue: arXiv cs.DC 2011
Year: 2011

A parallel program can be represented as a directed acyclic graph. An important performance bound is the time to execute the critical path through the graph. We show how this performance metric is related to Amdahl speedup and the degree of average parallelism. These bounds formally exclude superlinear performance.