@inproceedings{3336,
abstract = {We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.},
author = {Chen, Chao and Freedman, Daniel and Lampert, Christoph},
booktitle = {CVPR: Computer Vision and Pattern Recognition},
location = {Colorado Springs, CO, USA},
pages = {2089 -- 2096},
publisher = {IEEE},
title = {{Enforcing topological constraints in random field image segmentation}},
doi = {10.1109/CVPR.2011.5995503},
year = {2011},
}
@article{3267,
abstract = {We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field.},
author = {Chen, Chao and Freedman, Daniel},
journal = {Discrete & Computational Geometry},
number = {3},
pages = {425 -- 448},
publisher = {Springer},
title = {{Hardness results for homology localization}},
doi = {10.1007/s00454-010-9322-8},
volume = {45},
year = {2011},
}
@inproceedings{3298,
abstract = {We present a new algorithm for enforcing incompressibility for Smoothed Particle Hydrodynamics (SPH) by preserving uniform density across the domain. We propose a hybrid method that uses a Poisson solve on a coarse grid to enforce a divergence free velocity ﬁeld, followed by a local density correction of the particles. This avoids typical grid artifacts and maintains the Lagrangian nature of SPH by directly transferring pressures onto particles. Our method can be easily integrated with existing SPH techniques such as the incompressible PCISPH method as well as weakly compressible SPH by adding an additional force term. We show that this hybrid method accelerates convergence towards uniform density and permits a signiﬁcantly larger time step compared to earlier approaches while producing similar results. We demonstrate our approach in a variety of scenarios with signiﬁcant pressure gradients such as splashing liquids.},
author = {Raveendran, Karthik and Wojtan, Christopher J and Turk, Greg},
editor = {Spencer, Stephen},
location = {Vancouver, Canada},
pages = {33 -- 42},
publisher = {ACM},
title = {{Hybrid smoothed particle hydrodynamics}},
doi = {10.1145/2019406.2019411},
year = {2011},
}
@inproceedings{3301,
abstract = {The chemical master equation is a differential equation describing the time evolution of the probability distribution over the possible “states” of a biochemical system. The solution of this equation is of interest within the systems biology field ever since the importance of the molec- ular noise has been acknowledged. Unfortunately, most of the systems do not have analytical solutions, and numerical solutions suffer from the course of dimensionality and therefore need to be approximated. Here, we introduce the concept of tail approximation, which retrieves an approximation of the probabilities in the tail of a distribution from the total probability of the tail and its conditional expectation. This approximation method can then be used to numerically compute the solution of the chemical master equation on a subset of the state space, thus fighting the explosion of the state space, for which this problem is renowned.},
author = {Henzinger, Thomas A and Mateescu, Maria},
publisher = {Tampere International Center for Signal Processing},
title = {{Tail approximation for the chemical master equation}},
year = {2011},
}
@inproceedings{3313,
abstract = {Interpreting an image as a function on a compact sub- set of the Euclidean plane, we get its scale-space by diffu- sion, spreading the image over the entire plane. This gener- ates a 1-parameter family of functions alternatively defined as convolutions with a progressively wider Gaussian ker- nel. We prove that the corresponding 1-parameter family of persistence diagrams have norms that go rapidly to zero as time goes to infinity. This result rationalizes experimental observations about scale-space. We hope this will lead to targeted improvements of related computer vision methods.},
author = {Chen, Chao and Edelsbrunner, Herbert},
booktitle = {Proceedings of the IEEE International Conference on Computer Vision},
location = {Barcelona, Spain},
publisher = {IEEE},
title = {{Diffusion runs low on persistence fast}},
doi = {10.1109/ICCV.2011.6126271},
year = {2011},
}
@unpublished{3363,
abstract = {We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Tracol, Mathieu},
pages = {19},
publisher = {ArXiv},
title = {{The decidability frontier for probabilistic automata on infinite words}},
year = {2011},
}
@inproceedings{3349,
abstract = {Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena.},
author = {Chatterjee, Krishnendu and Fijalkow, Nathanaël},
location = {Minori, Italy},
pages = {74 -- 86},
publisher = {EPTCS},
title = {{A reduction from parity games to simple stochastic games}},
doi = {10.4204/EPTCS.54.6},
volume = {54},
year = {2011},
}
@inproceedings{3351,
abstract = {In two-player games on graph, the players construct an infinite path through the game graph and get a reward computed by a payoff function over infinite paths. Over weighted graphs, the typical and most studied payoff functions compute the limit-average or the discounted sum of the rewards along the path. Besides their simple definition, these two payoff functions enjoy the property that memoryless optimal strategies always exist. In an attempt to construct other simple payoff functions, we define a class of payoff functions which compute an (infinite) weighted average of the rewards. This new class contains both the limit-average and the discounted sum functions, and we show that they are the only members of this class which induce memoryless optimal strategies, showing that there is essentially no other simple payoff functions.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Singh, Rohit},
editor = {Owe, Olaf and Steffen, Martin and Telle, Jan Arne},
location = {Oslo, Norway},
pages = {148 -- 159},
publisher = {Springer},
title = {{On memoryless quantitative objectives}},
doi = {10.1007/978-3-642-22953-4_13},
volume = {6914},
year = {2011},
}
@article{3318,
abstract = {Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers.},
author = {Eggermann, Emmanuel and Jonas, Peter M},
journal = {Nature Neuroscience},
pages = {20 -- 22},
publisher = {Nature Publishing Group},
title = {{How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses}},
doi = {10.1038/nn.3002},
volume = {15},
year = {2011},
}
@article{3320,
abstract = {Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature.},
author = {Nowozin, Sebastian and Lampert, Christoph},
journal = {Foundations and Trends in Computer Graphics and Vision},
number = {3-4},
pages = {185 -- 365},
publisher = {now},
title = {{Structured learning and prediction in computer vision}},
doi = {10.1561/0600000033},
volume = {6},
year = {2011},
}
@inproceedings{3325,
abstract = {We introduce streaming data string transducers that map input data strings to output data strings in a single left-to-right pass in linear time. Data strings are (unbounded) sequences of data values, tagged with symbols from a finite set, over a potentially infinite data do- main that supports only the operations of equality and ordering. The transducer uses a finite set of states, a finite set of variables ranging over the data domain, and a finite set of variables ranging over data strings. At every step, it can make decisions based on the next in- put symbol, updating its state, remembering the input data value in its data variables, and updating data-string variables by concatenat- ing data-string variables and new symbols formed from data vari- ables, while avoiding duplication. We establish that the problems of checking functional equivalence of two streaming transducers, and of checking whether a streaming transducer satisfies pre/post verification conditions specified by streaming acceptors over in- put/output data-strings, are in PSPACE. We identify a class of imperative and a class of functional pro- grams, manipulating lists of data items, which can be effectively translated to streaming data-string transducers. The imperative pro- grams dynamically modify a singly-linked heap by changing next- pointers of heap-nodes and by adding new nodes. The main re- striction specifies how the next-pointers can be used for traversal. We also identify an expressively equivalent fragment of functional programs that traverse a list using syntactically restricted recursive calls. Our results lead to algorithms for assertion checking and for checking functional equivalence of two programs, written possibly in different programming styles, for commonly used routines such as insert, delete, and reverse.},
author = {Alur, Rajeev and Cerny, Pavol},
location = {Texas, USA},
number = {1},
pages = {599 -- 610},
publisher = {ACM},
title = {{Streaming transducers for algorithmic verification of single pass list processing programs}},
doi = {10.1145/1926385.1926454},
volume = {46},
year = {2011},
}
@inproceedings{3337,
abstract = {Playing table tennis is a difficult task for robots, especially due to their limitations of acceleration. A key bottleneck is the amount of time needed to reach the desired hitting position and velocity of the racket for returning the incoming ball. Here, it often does not suffice to simply extrapolate the ball's trajectory after the opponent returns it but more information is needed. Humans are able to predict the ball's trajectory based on the opponent's moves and, thus, have a considerable advantage. Hence, we propose to incorporate an anticipation system into robot table tennis players, which enables the robot to react earlier while the opponent is performing the striking movement. Based on visual observation of the opponent's racket movement, the robot can predict the aim of the opponent and adjust its movement generation accordingly. The policies for deciding how and when to react are obtained by reinforcement learning. We conduct experiments with an existing robot player to show that the learned reaction policy can significantly improve the performance of the overall system.},
author = {Wang, Zhikun and Lampert, Christoph and Mülling, Katharina and Schölkopf, Bernhard and Peters, Jan},
location = {San Francisco, USA},
pages = {332 -- 337},
publisher = {IEEE},
title = {{Learning anticipation policies for robot table tennis}},
doi = {10.1109/IROS.2011.6094892},
year = {2011},
}
@inproceedings{3344,
abstract = {Games played on graphs provide the mathematical framework to analyze several important problems in computer science as well as mathematics, such as the synthesis problem of Church, model checking of open reactive systems and many others. On the basis of mode of interaction of the players these games can be classified as follows: (a) turn-based (players make moves in turns); and (b) concurrent (players make moves simultaneously). On the basis of the information available to the players these games can be classified as follows: (a) perfect-information (players have perfect view of the game); and (b) partial-information (players have partial view of the game). In this talk we will consider all these classes of games with reachability objectives, where the goal of one player is to reach a set of target vertices of the graph, and the goal of the opponent player is to prevent the player from reaching the target. We will survey the results for various classes of games, and the results range from linear time decision algorithms to EXPTIME-complete problems to undecidable problems.},
author = {Chatterjee, Krishnendu},
editor = {Delzanno, Giorgo and Potapov, Igor},
location = {Genoa, Italy},
pages = {1 -- 1},
publisher = {Springer},
title = {{Graph games with reachability objectives}},
doi = {10.1007/978-3-642-24288-5_1},
volume = {6945},
year = {2011},
}
@article{3332,
abstract = {Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3.},
author = {Kerber, Michael and Sagraloff, Michael},
journal = {Graphs and Combinatorics},
number = {3},
pages = {419 -- 430},
publisher = {Springer},
title = {{A note on the complexity of real algebraic hypersurfaces}},
doi = {10.1007/s00373-011-1020-7},
volume = {27},
year = {2011},
}
@article{3781,
abstract = {We bound the difference in length of two curves in terms of their total curvatures and the Fréchet distance. The bound is independent of the dimension of the ambient Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner, and it generalizes a result by Fáry and Chakerian.},
author = {Fasy, Brittany Terese},
journal = {Acta Sci. Math. (Szeged)},
number = {1-2},
pages = {359 -- 367},
publisher = {Szegedi Tudományegyetem},
title = {{The difference in length of curves in R^n}},
volume = {77},
year = {2011},
}
@article{3382,
abstract = {Dynamic tactile sensing is a fundamental ability to recognize materials and objects. However, while humans are born with partially developed dynamic tactile sensing and quickly master this skill, today's robots remain in their infancy. The development of such a sense requires not only better sensors but the right algorithms to deal with these sensors' data as well. For example, when classifying a material based on touch, the data are noisy, high-dimensional, and contain irrelevant signals as well as essential ones. Few classification methods from machine learning can deal with such problems. In this paper, we propose an efficient approach to infer suitable lower dimensional representations of the tactile data. In order to classify materials based on only the sense of touch, these representations are autonomously discovered using visual information of the surfaces during training. However, accurately pairing vision and tactile samples in real-robot applications is a difficult problem. The proposed approach, therefore, works with weak pairings between the modalities. Experiments show that the resulting approach is very robust and yields significantly higher classification performance based on only dynamic tactile sensing.},
author = {Kroemer, Oliver and Lampert, Christoph and Peters, Jan},
journal = {IEEE Transactions on Robotics},
number = {3},
pages = {545 -- 557},
publisher = {IEEE},
title = {{Learning dynamic tactile sensing with robust vision based training}},
doi = {10.1109/TRO.2011.2121130},
volume = {27},
year = {2011},
}
@article{3387,
abstract = {Background: Supertree methods combine overlapping input trees into a larger supertree. Here, I consider split-based supertree methods that first extract the split information of the input trees and subsequently combine this split information into a phylogeny. Well known split-based supertree methods are matrix representation with parsimony and matrix representation with compatibility. Combining input trees on the same taxon set, as in the consensus setting, is a well-studied task and it is thus desirable to generalize consensus methods to supertree methods. Results: Here, three variants of majority-rule (MR) supertrees that generalize majority-rule consensus trees are investigated. I provide simple formulas for computing the respective score for bifurcating input- and supertrees. These score computations, together with a heuristic tree search minmizing the scores, were implemented in the python program PluMiST (Plus- and Minus SuperTrees) available from http://www.cibiv.at/software/ plumist. The different MR methods were tested by simulation and on real data sets. The search heuristic was successful in combining compatible input trees. When combining incompatible input trees, especially one variant, MR(-) supertrees, performed well. Conclusions: The presented framework allows for an efficient score computation of three majority-rule supertree variants and input trees. I combined the score computation with a heuristic search over the supertree space. The implementation was tested by simulation and on real data sets and showed promising results. Especially the MR(-) variant seems to be a reasonable score for supertree reconstruction. Generalizing these computations to multifurcating trees is an open problem, which may be tackled using this framework.},
author = {Kupczok, Anne},
journal = {BMC Evolutionary Biology},
number = {205},
publisher = {BioMed Central},
title = {{Split based computation of majority rule supertrees}},
doi = {10.1186/1471-2148-11-205},
volume = {11},
year = {2011},
}
@article{3394,
abstract = {Random genetic drift shifts clines in space, alters their width, and distorts their shape. Such random fluctuations complicate inferences from cline width and position. Notably, the effect of genetic drift on the expected shape of the cline is opposite to the naive (but quite common) misinterpretation of classic results on the expected cline. While random drift on average broadens the overall cline in expected allele frequency, it narrows the width of any particular cline. The opposing effects arise because locally, drift drives alleles to fixation—but fluctuations in position widen the expected cline. The effect of genetic drift can be predicted from standardized variance in allele frequencies, averaged across the habitat: 〈F〉. A cline maintained by spatially varying selection (step change) is expected to be narrower by a factor of relative to the cline in the absence of drift. The expected cline is broader by the inverse of this factor. In a tension zone maintained by underdominance, the expected cline width is narrower by about 1 – 〈F〉relative to the width in the absence of drift. Individual clines can differ substantially from the expectation, and we give quantitative predictions for the variance in cline position and width. The predictions apply to clines in almost one-dimensional circumstances such as hybrid zones in rivers, deep valleys, or along a coast line and give a guide to what patterns to expect in two dimensions.},
author = {Polechova, Jitka and Barton, Nicholas H},
journal = {Genetics},
number = {1},
pages = {227 -- 235},
publisher = {Genetics Society of America},
title = {{Genetic drift widens the expected cline but narrows the expected cline width}},
doi = {10.1534/genetics.111.129817},
volume = {189},
year = {2011},
}
@article{3399,
abstract = {Context-dependent adjustment of mating tactics can drastically increase the mating success of behaviourally flexible animals. We used the ant Cardiocondyla obscurior as a model system to study adaptive adjustment of male mating tactics. This species shows a male diphenism of wingless fighter males and peaceful winged males. Whereas the wingless males stay and exclusively mate in the maternal colony, the mating behaviour of winged males is plastic. They copulate with female sexuals in their natal nests early in life but later disperse in search for sexuals outside. In this study, we observed the nest-leaving behaviour of winged males under different conditions and found that they adaptively adjust the timing of their dispersal to the availability of mating partners, as well as the presence, and even the type of competitors in their natal nests. In colonies with virgin female queens winged males stayed longest when they were the only male in the nest. They left earlier when mating partners were not available or when other males were present. In the presence of wingless, locally mating fighter males, winged males dispersed earlier than in the presence of docile, winged competitors. This suggests that C. obscurior males are capable of estimating their local breeding chances and adaptively adjust their dispersal behaviour in both an opportunistic and a risk-sensitive way, thus showing hitherto unknown behavioural plasticity in social insect males.},
author = {Cremer, Sylvia and Schrempf, Alexandra and Heinze, Jürgen},
journal = {PLoS One},
number = {3},
publisher = {Public Library of Science},
title = {{Competition and opportunity shape the reproductive tactics of males in the ant Cardiocondyla obscurior}},
doi = {10.1371/journal.pone.0017323},
volume = {6},
year = {2011},
}
@article{3368,
abstract = {Tissue surface tension (TST) is an important mechanical property influencing cell sorting and tissue envelopment. The study by Manning et al. (1) reported on a mathematical model describing TST on the basis of the balance between adhesive and tensile properties of the constituent cells. The model predicts that, in high-adhesion cell aggregates, surface cells will be stretched to maintain the same area of cell–cell contact as interior bulk cells, resulting in an elongated and flattened cell shape. The authors (1) observed flat and elongated cells at the surface of high-adhesion zebrafish germ-layer explants, which they argue are undifferentiated stretched germ-layer progenitor cells, and they use this observation as a validation of their model.},
author = {Krens, Gabriel and Möllmert, Stephanie and Heisenberg, Carl-Philipp J},
journal = {PNAS},
number = {3},
pages = {E9 -- E10},
publisher = {National Academy of Sciences},
title = {{Enveloping cell layer differentiation at the surface of zebrafish germ layer tissue explants}},
doi = {10.1073/pnas.1010767108},
volume = {108},
year = {2011},
}