@inproceedings{3236, abstract = {If a cryptographic primitive remains secure even if ℓ bits about the secret key are leaked to the adversary, one would expect that at least one of n independent instantiations of the scheme remains secure given n·ℓ bits of leakage. This intuition has been proven true for schemes satisfying some special information-theoretic properties by Alwen et al. [Eurocrypt'10]. On the negative side, Lewko and Waters [FOCS'10] construct a CPA secure public-key encryption scheme for which this intuition fails. The counterexample of Lewko and Waters leaves open the interesting possibility that for any scheme there exists a constant c>0, such that n fold repetition remains secure against c·n·ℓ bits of leakage. Furthermore, their counterexample requires the n copies of the encryption scheme to share a common reference parameter, leaving open the possibility that the intuition is true for all schemes without common setup. In this work we give a stronger counterexample ruling out these possibilities. We construct a signature scheme such that: 1. a single instantiation remains secure given ℓ = log(k) bits of leakage where k is a security parameter. 2. any polynomial number of independent instantiations can be broken (in the strongest sense of key-recovery) given ℓ′ = poly(k) bits of leakage. Note that ℓ does not depend on the number of instances. The computational assumption underlying our counterexample is that non-interactive computationally sound proofs exist. Moreover, under a stronger (non-standard) assumption about such proofs, our counterexample does not require a common reference parameter. The underlying idea of our counterexample is rather generic and can be applied to other primitives like encryption schemes. © 2011 International Association for Cryptologic Research.}, author = {Jain, Abhishek and Krzysztof Pietrzak}, pages = {58 -- 69}, publisher = {Springer}, title = {{Parallel repetition for leakage resilience amplification revisited}}, doi = {10.1007/978-3-642-19571-6_5}, volume = {6597 }, year = {2011}, } @article{3276, abstract = {We present an algorithm to identify individual neural spikes observed on high-density multi-electrode arrays (MEAs). Our method can distinguish large numbers of distinct neural units, even when spikes overlap, and accounts for intrinsic variability of spikes from each unit. As MEAs grow larger, it is important to find spike-identification methods that are scalable, that is, the computational cost of spike fitting should scale well with the number of units observed. Our algorithm accomplishes this goal, and is fast, because it exploits the spatial locality of each unit and the basic biophysics of extracellular signal propagation. Human interaction plays a key role in our method; but effort is minimized and streamlined via a graphical interface. We illustrate our method on data from guinea pig retinal ganglion cells and document its performance on simulated data consisting of spikes added to experimentally measured background noise. We present several tests demonstrating that the algorithm is highly accurate: it exhibits low error rates on fits to synthetic data, low refractory violation rates, good receptive field coverage, and consistency across users.}, author = {Prentice, Jason S and Homann, Jan and Simmons, Kristina D and Gasper Tkacik and Balasubramanian, Vijay and Nelson, Philip C}, journal = {PLoS One}, number = {7}, publisher = {Public Library of Science}, title = {{Fast, scalable, Bayesian spike identification for multi-electrode arrays}}, doi = {10.1371/journal.pone.0019884}, volume = {6}, year = {2011}, } @inbook{3271, abstract = {In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets.}, author = {Wagner, Hubert and Chen, Chao and Vuçini, Erald}, booktitle = {Topological Methods in Data Analysis and Visualization II}, editor = {Peikert, Ronald and Hauser, Helwig and Carr, Hamish and Fuchs, Raphael}, pages = {91 -- 106}, publisher = {Springer}, title = {{Efficient computation of persistent homology for cubical data}}, doi = {10.1007/978-3-642-23175-9_7}, year = {2011}, } @article{3278, abstract = {Despite much research on the socially parasitic large blue butterflies (genus Maculinea) in the past 40 years, their relationship to their closest relatives, Phengaris, is controversial and the relationships among the remaining genera in the Glaucopsyche section are largely unresolved. The evolutionary history of this butterfly section is particularly important to understand the evolution of life history diversity con- nected to food-plant and host-ant associations in the larval stage. In the present study, we use a combi- nation of four nuclear and two mitochondrial genes to reconstruct the phylogeny of the Glaucopsyche section, and in particular, to study the relationships among and within the Phengaris–Maculinea species. We find a clear pattern between the clades recovered in the Glaucopsyche section phylogeny and their food-plant associations, with only the Phengaris–Maculinea clade utilising more than one plant family. Maculinea is, for the first time, recovered with strong support as a monophyletic group nested within Phengaris, with the closest relative being the rare genus Caerulea. The genus Glaucopsyche is polyphyletic, including the genera Sinia and Iolana. Interestingly, we find evidence for additional potential cryptic spe- cies within the highly endangered Maculinea, which has long been suspected from morphological, ecolog- ical and molecular studies.}, author = {Vila, Roger and Pierce, Naomi E and Nash, David R and Line Ugelvig}, journal = {Molecular Phylogenetics and Evolution}, number = {1}, pages = {237 -- 243}, publisher = {Elsevier}, title = {{A phylogenetic revision of the Glaucopsyche section (Lepidoptera: Lycaenidae), with special focus on the Phengaris-Maculinea clade}}, doi = {10.1016/j.ympev.2011.05.016}, volume = {61}, year = {2011}, } @inproceedings{3270, abstract = {The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.}, author = {Chen, Chao and Kerber, Michael}, location = {Morschach, Switzerland}, pages = {197 -- 200}, publisher = {TU Dortmund}, title = {{Persistent homology computation with a twist}}, 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 field, 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 significantly larger time step compared to earlier approaches while producing similar results. We demonstrate our approach in a variety of scenarios with significant 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{3297, abstract = {Animating detailed liquid surfaces has always been a challenge for computer graphics researchers and visual effects artists. Over the past few years, researchers in this field have focused on mesh-based surface tracking to synthesize extremely detailed liquid surfaces as efficiently as possible. This course provides a solid understanding of the steps required to create a fluid simulator with a mesh-based liquid surface. The course begins with an overview of several existing liquid-surface-tracking techniques and the pros and cons of each method. Then it explains how to embed a triangle mesh into a finite-difference-based fluid simulator and describes several methods for allowing the liquid surface to merge together or break apart. The final section showcases the benefits and further applications of a mesh-based liquid surface, highlighting state-of-the-art methods for tracking colors and textures, maintaining liquid volume, preserving small surface features, and simulating realistic surface-tension waves.}, author = {Wojtan, Christopher J and Müller Fischer, Matthias and Brochu, Tyson}, location = {Vancouver, BC, Canada}, publisher = {ACM}, title = {{Liquid simulation with mesh-based surface tracking}}, doi = {10.1145/2037636.2037644}, year = {2011}, } @article{3290, abstract = {Analysis of genomic data requires an efficient way to calculate likelihoods across very large numbers of loci. We describe a general method for finding the distribution of genealogies: we allow migration between demes, splitting of demes [as in the isolation-with-migration (IM) model], and recombination between linked loci. These processes are described by a set of linear recursions for the generating function of branch lengths. Under the infinite-sites model, the probability of any configuration of mutations can be found by differentiating this generating function. Such calculations are feasible for small numbers of sampled genomes: as an example, we show how the generating function can be derived explicitly for three genes under the two-deme IM model. This derivation is done automatically, using Mathematica. Given data from a large number of unlinked and nonrecombining blocks of sequence, these results can be used to find maximum-likelihood estimates of model parameters by tabulating the probabilities of all relevant mutational configurations and then multiplying across loci. The feasibility of the method is demonstrated by applying it to simulated data and to a data set previously analyzed by Wang and Hey (2010) consisting of 26,141 loci sampled from Drosophila simulans and D. melanogaster. Our results suggest that such likelihood calculations are scalable to genomic data as long as the numbers of sampled individuals and mutations per sequence block are small.}, author = {Lohse, Konrad and Harrison, Richard and Barton, Nicholas H}, journal = {Genetics}, number = {3}, pages = {977 -- 987}, publisher = {Genetics Society of America}, title = {{A general method for calculating likelihoods under the coalescent process}}, doi = {10.1534/genetics.111.129569}, volume = {189}, year = {2011}, } @misc{3312, abstract = {We study the 3D reconstruction of plant roots from multiple 2D images. To meet the challenge caused by the delicate nature of thin branches, we make three innovations to cope with the sensitivity to image quality and calibration. First, we model the background as a harmonic function to improve the segmentation of the root in each 2D image. Second, we develop the concept of the regularized visual hull which reduces the effect of jittering and refraction by ensuring consistency with one 2D image. Third, we guarantee connectedness through adjustments to the 3D reconstruction that minimize global error. Our software is part of a biological phenotype/genotype study of agricultural root systems. It has been tested on more than 40 plant roots and results are promising in terms of reconstruction quality and efficiency.}, author = {Zheng, Ying and Gu, Steve and Edelsbrunner, Herbert and Tomasi, Carlo and Benfey, Philip}, booktitle = {Proceedings of the IEEE International Conference on Computer Vision}, location = {Barcelona, Spain}, publisher = {IEEE}, title = {{Detailed reconstruction of 3D plant root shape}}, doi = {10.1109/ICCV.2011.6126475}, 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}, }