@article{6148, author = {Kammenga, Jan E. and Phillips, Patrick C. and de Bono, Mario and Doroszuk, Agnieszka}, issn = {0168-9525}, journal = {Trends in Genetics}, number = {4}, pages = {178--185}, publisher = {Elsevier}, title = {{Beyond induced mutants: using worms to study natural variation in genetic pathways}}, doi = {10.1016/j.tig.2008.01.001}, volume = {24}, year = {2008}, } @article{6149, author = {Olofsson, Birgitta and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {5}, pages = {R204--R206}, publisher = {Elsevier}, title = {{Sleep: dozy worms and sleepy flies}}, doi = {10.1016/j.cub.2008.01.002}, volume = {18}, year = {2008}, } @article{1982, abstract = {In the bacterium Escherichia coli, the Min proteins oscillate between the cell poles to select the cell center as division site. This dynamic pattern has been proposed to arise by self-organization of these proteins, and several models have suggested a reaction-diffusion type mechanism. Here, we found that the Min proteins spontaneously formed planar surface waves on a flat membrane in vitro. The formation and maintenance of these patterns, which extended for hundreds of micrometers, required adenosine 5′-triphosphate (ATP), and they persisted for hours. We present a reaction-diffusion model of the MinD and MinE dynamics that accounts for our experimental observations and also captures the in vivo oscillations.}, author = {Martin Loose and Fischer-Friedrich, Elisabeth and Ries, Jonas and Kruse, Karsten and Schwille, Petra }, journal = {Science}, number = {5877}, pages = {789 -- 792}, publisher = {American Association for the Advancement of Science}, title = {{Spatial regulators for bacterial cell division self-organize into surface waves in vitro}}, doi = {10.1126/science.1154413}, volume = {320}, year = {2008}, } @article{2065, abstract = {Population genetics models show that, under certain conditions, the X chromosome is expected to be under more efficient selection than the autosomes. This could lead to 'faster-X evolution', if a large proportion of mutations are fixed by positive selection, as suggested by recent studies in Drosophila. We used a multispecies approach to test this: Muller's element D, an autosomal arm, is fused to the ancestral X chromosome in Drosophila pseudoobscura and its sister species, Drosophila affinis. We tested whether the same set of genes had higher rates of non-synonymous evolution when they were X-linked (in the D. pseudoobscura/D. affinis comparison) than when they were autosomal (in Drosophila melanogaster/Drosophila yakuba). Although not significant, our results suggest this may be the case, but only for genes under particularly strong positive selection/weak purifying selection. They also suggest that genes that have become X-linked have higher levels of codon bias and slower synonymous site evolution, consistent with more effective selection on codon usage at X-linked sites.}, author = {Beatriz Vicoso and Haddrill, Penelope R and Charlesworth, Brian}, journal = {Genetical Research}, number = {5}, pages = {421 -- 431}, publisher = {Cambridge University Press}, title = {{A multispecies approach for comparing sequence evolution of X-linked and autosomal sites in Drosophila}}, doi = {10.1017/S0016672308009804}, volume = {90}, year = {2008}, } @inproceedings{2078, abstract = {This paper presents a novel method for real-time animation of highly-detailed facial expressions based on a multi-scale decomposition of facial geometry into large-scale motion and fine-scale details, such as expression wrinkles. Our hybrid animation is tailored to the specific characteristics of large- and fine-scale facial deformations: Large-scale deformations are computed with a fast linear shell model, which is intuitively and accurately controlled through a sparse set of motion-capture markers or user-defined handle points. Fine-scale facial details are incorporated using a novel pose-space deformation technique, which learns the correspondence of sparse measurements of skin strain to wrinkle formation from a small set of example poses. Our hybrid method features real-time animation of highly-detailed faces with realistic wrinkle formation, and allows both large-scale deformations and fine-scale wrinkles to be edited intuitively. Furthermore, our pose-space representation enables the transfer of facial details to novel expressions or other facial models.}, author = {Bickel, Bernd and Lang, Manuel and Botsch, Mario and Otaduy, Miguel and Gross, Markus}, pages = {57 -- 66}, publisher = {ACM}, title = {{Pose-space animation and transfer of facial details}}, doi = {10.2312/SCA/SCA08/057-066}, year = {2008}, } @article{1036, abstract = {We report on the control of interaction-induced dephasing of Bloch oscillations for an atomic Bose-Einstein condensate in an optical lattice. We quantify the dephasing in terms of the width of the quasimomentum distribution and measure its dependence on time for different interaction strengths which we control by means of a Feshbach resonance. For minimal interaction, the dephasing time is increased from a few to more than 20 thousand Bloch oscillation periods, allowing us to realize a BEC-based atom interferometer in the noninteracting limit.}, author = {Gustavsson, Mattias and Haller, Elmar and Mark, Manfred and Danzl, Johann G and Rojas Kopeinig, Gabriel and Nägerl, Hanns}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Control of interaction-induced dephasing of bloch oscillations}}, doi = {10.1103/PhysRevLett.100.080404}, volume = {100}, year = {2008}, } @article{1037, abstract = {We experimentally demonstrate Cs2 Feshbach molecules well above the dissociation threshold, which are stable against spontaneous decay on the time scale of 1s. An optically trapped sample of ultracold dimers is prepared in a high rotational state and magnetically tuned into a region with a negative binding energy. The metastable character of these molecules arises from the large centrifugal barrier in combination with negligible coupling to states with low rotational angular momentum. A sharp onset of dissociation with increasing magnetic field is mediated by a crossing with a lower rotational dimer state and facilitates dissociation on demand with a well-defined energy.}, author = {Knoop, Steven and Mark, Michael and Ferlaino, Francesca and Danzl, Johann G and Kraemer, Tobias and Nägerl, Hanns and Grimm, Rudolf}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Metastable feshbach molecules in high rotational states}}, doi = {10.1103/PhysRevLett.100.083002}, volume = {100}, year = {2008}, } @article{1039, abstract = {Molecular cooling techniques face the hurdle of dissipating translational as well as internal energy in the presence of a rich electronic, vibrational, and rotational energy spectrum. In our experiment, we create a translationally ultracold, dense quantum gas of molecules bound by more than 1000 wave numbers in the electronic ground state. Specifically, we stimulate with 80% efficiency, a two-photon transfer of molecules associated on a Feshbach resonance from a Bose-Einstein condensate of cesium atoms. In the process, the initial loose, long-range electrostatic bond of the Feshbach molecule is coherently transformed into a tight chemical bond. We demonstrate coherence of the transfer in a Ramsey-type experiment and show that the molecular sample is not heated during the transfer. Our results show that the preparation of a quantum gas of molecules in specific rovibrational states is possible and that the creation of a Bose-Einstein condensate of molecules in their rovibronic ground state is within reach.}, author = {Danzl, Johann G and Haller, Elmar and Gustavsson, Mattias and Mark, Manfred and Hart, Russell and Bouloufa, Nadia and Dulieu, Olivier and Ritsch, Helmut and Nägerl, Hanns}, journal = {Science}, number = {5892}, pages = {1062 -- 1066}, publisher = {American Association for the Advancement of Science}, title = {{Quantum gas of deeply bound ground state molecules}}, doi = {10.1126/science.1159909}, volume = {321}, year = {2008}, } @article{10392, abstract = {Protonated formylmetallocenes [M(C5H5)(C5H4-CHOH)]+ (M = Fe, Ru) and their isomers have been studied at the BP86 and B3LYP levels of density functional theory. Oxygen-protonated isomers are the most stable forms in each case, with a plethora of ring- or metal-protonated species at least ca. 14 and 10 kcal/mol higher in energy for M = Fe and Ru, respectively. The computed rotational barriers around the C−C bond connecting the cyclopentadienyl and protonated formyl moieties, ca. 18 kcal/mol, are indicative of substantial conjugation between these moieties. Some of the ring- and iron-protonated species are models for possible intermediates in Friedel–Crafts acylation of ferrocene, and the computations provide further evidence that exo attack is clearly favored over endo attack of the electrophile in this reaction. The structures of the most stable mono- and diprotonated formylferrocenes are corroborated by the good agreement between GIAO-B3LYP-computed and experimental NMR chemical shifts.}, author = {Šarić, Anđela and Vrček, Valerije and Bühl, Michael}, issn = {1520-6041}, journal = {Organometallics}, keywords = {Inorganic Chemistry, Organic Chemistry, Physical and Theoretical Chemistry}, number = {3}, pages = {394--401}, publisher = {American Chemical Society}, title = {{Density functional study of protonated formylmetallocenes}}, doi = {10.1021/om700916f}, volume = {27}, year = {2008}, } @inproceedings{3170, abstract = {Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry.}, author = {Boykov, Yuri and Kolmogorov, Vladimir}, isbn = {0769519504}, location = {Nice, France}, pages = {26 -- 33}, publisher = {IEEE}, title = {{Computing geodesics and minimal surfaces via graph cuts}}, doi = {10.1109/ICCV.2003.1238310}, volume = {1}, year = {2008}, } @inproceedings{3174, abstract = {We address visual correspondence problems without assuming that scene points have similar intensities in different views. This situation is common, usually due to non-lambertian scenes or to differences between cameras. We use maximization of mutual information, a powerful technique for registering images that requires no a priori model of the relationship between scene intensities in different views. However, it has proven difficult to use mutual information to compute dense visual correspondence. Comparing fixed-size windows via mutual information suffers from the well-known problems of fixed windows, namely poor performance at discontinuities and in low-texture regions. In this paper, we show how to compute visual correspondence using mutual information without suffering from these problems. Using 'a simple approximation, mutual information can be incorporated into the standard energy minimization framework used in early vision. The energy can then be efficiently minimized using graph cuts, which preserve discontinuities and handle low-texture regions. The resulting algorithm combines the accurate disparity maps that come from graph cuts with the tolerance for intensity changes that comes from mutual information.}, author = {Kim, Junhwan and Kolmogorov, Vladimir and Zabih, Ramin}, booktitle = {Proceedings Ninth International Conference on Computer Vision}, isbn = {0769519504}, location = {Nice, France}, pages = {1033 -- 1040}, publisher = {IEEE}, title = {{Visual correspondence using energy minimization and mutual information}}, doi = {10.1109/ICCV.2003.1238463}, volume = {2}, year = {2008}, } @inproceedings{3194, abstract = {We consider the problem of optimizing multilabel MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer linear programming and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. The resulting relaxation can be efficiently solved using a maximum flow algorithm. Its solution provides us with a partially optimal labelling of the binary variables. This partial labelling is then easily transferred to the multi-label problem. We study the theoretical properties of the new relaxation and compare it with the standard one. Specifically, we compare tightness, and characterize a subclass of problems where the two relaxations coincide. We propose several combined algorithms based on the technique and demonstrate their performance on challenging computer vision problems.}, author = {Kohli, Pushmeet and Shekhovtsov, Alexander and Rother, Carsten and Vladimir Kolmogorov and Torr, Philip H}, pages = {480 -- 487}, publisher = {Omnipress}, title = {{On partial optimality in multi label MRFs}}, doi = {10.1145/1390156.1390217}, year = {2008}, } @inproceedings{3195, abstract = {Graph cut is a popular technique for interactive image segmentation. However, it has certain shortcomings. In particular, graph cut has problems with segmenting thin elongated objects due to the ldquoshrinking biasrdquo. To overcome this problem, we propose to impose an additional connectivity prior, which is a very natural assumption about objects. We formulate several versions of the connectivity constraint and show that the corresponding optimization problems are all NP-hard. For some of these versions we propose two optimization algorithms: (i) a practical heuristic technique which we call DijkstraGC, and (ii) a slow method based on problem decomposition which provides a lower bound on the problem. We use the second technique to verify that for some practical examples DijkstraGC is able to find the global minimum.}, author = {Vicente, Sara and Vladimir Kolmogorov and Rother, Carsten}, publisher = {IEEE}, title = {{Graph cut based image segmentation with connectivity priors}}, doi = {10.1109/CVPR.2008.4587440}, year = {2008}, } @article{3196, abstract = {Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. Algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: For example, such methods form the basis for almost all the top-performing stereo methods. However, the trade-offs among different energy minimization algorithms are still not well understood. In this paper, we describe a set of energy minimization benchmarks and use them to compare the solution quality and runtime of several common energy minimization algorithms. We investigate three promising methods-graph cuts, LBP, and tree-reweighted message passing-in addition to the well-known older iterated conditional mode (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. The benchmarks, code, images, and results are available at http://vision.middlebury.edu/MRF/.}, author = {Szeliski, Richard S and Zabih, Ramin and Scharstein, Daniel and Veksler, Olga and Vladimir Kolmogorov and Agarwala, Aseem and Tappen, Marshall F and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {6}, pages = {1068 -- 1080}, publisher = {IEEE}, title = {{A comparative study of energy minimization methods for Markov random fields with smoothness-based priors}}, doi = {10.1109/TPAMI.2007.70844}, volume = {30}, year = {2008}, } @inproceedings{3198, abstract = {In this paper we present a new approach for establishing correspondences between sparse image features related by an unknown non-rigid mapping and corrupted by clutter and occlusion, such as points extracted from a pair of images containing a human figure in distinct poses. We formulate this matching task as an energy minimization problem by defining a complex objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general a NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods. }, author = {Torresani, Lorenzo and Vladimir Kolmogorov and Rother, Carsten}, pages = {596 -- 609}, publisher = {Springer}, title = {{Feature correspondence via graph matching: Models and global optimization}}, doi = {10.1007/978-3-540-88688-4_44}, volume = {5303}, year = {2008}, } @inproceedings{3224, abstract = {We propose a new mode of operation, enciphered CBC, for domain extension of length-preserving functions (like block ciphers), which is a variation on the popular CBC mode of operation. Our new mode is twice slower than CBC, but has many (property-preserving) properties not enjoyed by CBC and other known modes. Most notably, it yields the first constant-rate Variable Input Length (VIL) MAC from any length preserving Fixed Input Length (FIL) MAC. This answers the question of Dodis and Puniya from Eurocrypt 2007. Further, our mode is a secure domain extender for PRFs (with basically the same security as encrypted CBC). This provides a hedge against the security of the block cipher: if the block cipher is pseudorandom, one gets a VIL-PRF, while if it is "only" unpredictable, one "at least" gets a VIL-MAC. Additionally, our mode yields a VIL random oracle (and, hence, a collision-resistant hash function) when instantiated with length-preserving random functions, or even random permutations (which can be queried from both sides). This means that one does not have to re-key the block cipher during the computation, which was critically used in most previous constructions (analyzed in the ideal cipher model). }, author = {Dodis, Yevgeniy and Krzysztof Pietrzak and Puniya, Prashant}, pages = {198 -- 219}, publisher = {Springer}, title = {{A new mode of operation for block ciphers and length preserving MACs}}, doi = {10.1007/978-3-540-78967-3_12}, volume = {4965}, year = {2008}, } @inproceedings{3225, abstract = {A robust multi-property combiner for a set of security properties merges two hash functions such that the resulting function satisfies each of the properties which at least one of the two starting functions has. Fischlin and Lehmann (TCC 2008) recently constructed a combiner which simultaneously preserves collision-resistance, target collision-resistance, message authentication, pseudorandomness and indifferentiability from a random oracle (IRO). Their combiner produces outputs of 5n bits, where n denotes the output length of the underlying hash functions. In this paper we propose improved combiners with shorter outputs. By sacrificing the indifferentiability from random oracles we obtain a combiner which preserves all of the other aforementioned properties but with output length 2n only. This matches a lower bound for black-box combiners for collision-resistance as the only property, showing that the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the IRO property, slightly increasing the output length to 2n + ω(logn). Finally, we show that a twist on our combiners also makes them robust for one-wayness (but at the price of a fixed input length). }, author = {Fischlin, Marc and Lehmann, Anja and Krzysztof Pietrzak}, number = {PART 2}, pages = {655 -- 666}, publisher = {Springer}, title = {{Robust multi property combiners for hash functions revisited}}, doi = {10.1007/978-3-540-70583-3_53}, volume = {5126}, year = {2008}, } @inproceedings{3226, abstract = {A family of functions is weakly pseudorandom if a random member of the family is indistinguishable from a uniform random function when queried on random inputs. We point out a subtle ambiguity in the definition of weak PRFs: there are natural weak PRFs whose security breaks down if the randomness used to sample the inputs is revealed. To capture this ambiguity we distinguish between public-coin and secret-coin weak PRFs. We show that the existence of a secret-coin weak PRF which is not also a public-coin weak PRF implies the existence of two pass key-agreement (i.e. public-key encryption). So in Minicrypt, i.e. under the assumption that one-way functions exist but public-key cryptography does not, the notion of public- and secret-coin weak PRFs coincide. Previous to this paper all positive cryptographic statements known to hold exclusively in Minicrypt concerned the adaptive security of constructions using non-adaptively secure components. Weak PRFs give rise to a new set of statements having this property. As another example we consider the problem of range extension for weak PRFs. We show that in Minicrypt one can beat the best possible range expansion factor (using a fixed number of distinct keys) for a very general class of constructions (in particular, this class contains all constructions that are known today). }, author = {Krzysztof Pietrzak and Sjödin, Johan}, number = {PART 2}, pages = {423 -- 436}, publisher = {Springer}, title = {{Weak pseudorandom functions in minicrypt}}, doi = {10.1007/978-3-540-70583-3_35}, volume = {5126}, year = {2008}, } @article{3227, abstract = {Large amount of data management can cause a lot of troubles which can be solved by dedicated computer system. To facilitate management of measurement data which are gathered in Institute of Power Engineering - Insulation Department a special system called Elektrowiz® was developed. It allows storing measurement results which concern partial discharges in insulation of turbo- and hydrogenerators in power stations. Multilayer architecture of the system allows reaching gathered data independently on user localization. There are possible different access methods to the system and dependency on current requirements data exploration can be realized with read-only or edit rights.}, author = {Zubielik, Piotr and Nadaczny, Jerzy and Krzysztof Pietrzak and Lawenda, Marcin}, journal = {Przeglad Elektrotechniczny}, number = {10}, pages = {239 -- 242}, publisher = {SIGMA-NOT}, title = {{Elektrowiz – system of measurement data management}}, volume = {84}, year = {2008}, } @inproceedings{3228, abstract = { A black-box combiner for collision resistant hash functions (CRHF) is a construction which given black-box access to two hash functions is collision resistant if at least one of the components is collision resistant. In this paper we prove a lower bound on the output length of black-box combiners for CRHFs. The bound we prove is basically tight as it is achieved by a recent construction of Canetti et al [Crypto'07]. The best previously known lower bounds only ruled out a very restricted class of combiners having a very strong security reduction: the reduction was required to output collisions for both underlying candidate hash-functions given a single collision for the combiner (Canetti et al [Crypto'07] building on Boneh and Boyen [Crypto'06] and Pietrzak [Eurocrypt'07]). Our proof uses a lemma similar to the elegant "reconstruction lemma" of Gennaro and Trevisan [FOCS'00], which states that any function which is not one-way is compressible (and thus uniformly random function must be one-way). In a similar vein we show that a function which is not collision resistant is compressible. We also borrow ideas from recent work by Haitner et al. [FOCS'07], who show that one can prove the reconstruction lemma even relative to some very powerful oracles (in our case this will be an exponential time collision-finding oracle). © 2008 Springer-Verlag Berlin Heidelberg.}, author = {Krzysztof Pietrzak}, pages = {413 -- 432}, publisher = {Springer}, title = {{Compression from collisions or why CRHF combiners have a long output}}, doi = {10.1007/978-3-540-85174-5_23}, volume = {5157}, year = {2008}, }