@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}, } @inproceedings{3229, abstract = {We construct a stream-cipher S whose implementation is secure even if a bounded amount of arbitrary (adversarially chosen) information on the internal state ofS is leaked during computation. This captures all possible side-channel attacks on S where the amount of information leaked in a given period is bounded, but overall can be arbitrary large. The only other assumption we make on the implementation of S is that only data that is accessed during computation leaks information. The stream-cipher S generates its output in chunks K1, K2, . . . and arbitrary but bounded information leakage is modeled by allowing the adversary to adaptively chose a function fl : {0,1}* rarr {0, 1}lambda before Kl is computed, she then gets fl(taul) where taul is the internal state ofS that is accessed during the computation of Kg. One notion of security we prove for S is that Kg is indistinguishable from random when given K1,..., K1-1,f1(tau1 ),..., fl-1(taul-1) and also the complete internal state of S after Kg has been computed (i.e. S is forward-secure). The construction is based on alternating extraction (used in the intrusion-resilient secret-sharing scheme from FOCS'07). We move this concept to the computational setting by proving a lemma that states that the output of any PRG has high HILLpseudoentropy (i.e. is indistinguishable from some distribution with high min-entropy) even if arbitrary information about the seed is leaked. The amount of leakage lambda that we can tolerate in each step depends on the strength of the underlying PRG, it is at least logarithmic, but can be as large as a constant fraction of the internal state of S if the PRG is exponentially hard.}, author = {Dziembowski, Stefan and Krzysztof Pietrzak}, pages = {293 -- 302}, publisher = {IEEE}, title = {{Leakage resilient cryptography}}, doi = {10.1109/FOCS.2008.56}, year = {2008}, } @article{3291, abstract = {The filamentous fungus Aspergillus fumigatus is responsible for a lethal disease called Invasive Aspergillosis that affects immunocompromised patients. This disease, like other human fungal diseases, is generally treated by compounds targeting the primary fungal cell membrane sterol. Recently, glucan synthesis inhibitors were added to the limited antifungal arsenal and encouraged the search for novel targets in cell wall biosynthesis. Although galactomannan is a major component of the A. fumigatus cell wall and extracellular matrix, the biosynthesis and role of galactomannan are currently unknown. By a targeted gene deletion approach, we demonstrate that UDP-galactopyranose mutase, a key enzyme of galactofuranose metabolism, controls the biosynthesis of galactomannan and galactofuranose containing glycoconjugates. The glfA deletion mutant generated in this study is devoid of galactofuranose and displays attenuated virulence in a low-dose mouse model of invasive aspergillosis that likely reflects the impaired growth of the mutant at mammalian body temperature. Furthermore, the absence of galactofuranose results in a thinner cell wall that correlates with an increased susceptibility to several antifungal agents. The UDP-galactopyranose mutase thus appears to be an appealing adjunct therapeutic target in combination with other drugs against A. fumigatus. Its absence from mammalian cells indeed offers a considerable advantage to achieve therapeutic selectivity. }, author = {Philipp Schmalhorst and Krappmann, Sven and Vervecken, Wouter and Rohde, Manfred and Müller, Meike and Braus, Gerhard H. and Contreras, Roland and Braun, Armin and Bakker, Hans and Routier, Françoise H}, journal = {Eukaryotic Cell}, number = {8}, pages = {1268 -- 1277}, publisher = {American Society for Microbiology}, title = {{Contribution of galactofuranose to the virulence of the opportunistic pathogen Aspergillus fumigatus}}, doi = {10.1128/EC.00065-08}, volume = {7}, year = {2008}, } @article{3307, abstract = {A complete mitochondrial (mt) genome sequence was reconstructed from a 38,000 year-old Neandertal individual with 8341 mtDNA sequences identified among 4.8 Gb of DNA generated from ∼0.3 g of bone. Analysis of the assembled sequence unequivocally establishes that the Neandertal mtDNA falls outside the variation of extant human mtDNAs, and allows an estimate of the divergence date between the two mtDNA lineages of 660,000 ± 140,000 years. Of the 13 proteins encoded in the mtDNA, subunit 2 of cytochrome c oxidase of the mitochondrial electron transport chain has experienced the largest number of amino acid substitutions in human ancestors since the separation from Neandertals. There is evidence that purifying selection in the Neandertal mtDNA was reduced compared with other primate lineages, suggesting that the effective population size of Neandertals was small.}, author = {Green, Richard E and Malaspinas, Anna-Sapfo and Krause, Johannes and Briggs, Adrian W and Johnson, Philip L and Caroline Uhler and Meyer, Matthias and Good, Jeffrey M and Maricic, Tomislav and Stenzel, Udo and Prüfer, Kay and Siebauer, Michael F and Burbano, Hernän A and Ronan, Michael T and Rothberg, Jonathan M and Egholm, Michael and Rudan, Pavao and Brajković, Dejana and Kućan, Željko and Gušić, Ivan and Wikström, Mårten K and Laakkonen, Liisa J and Kelso, Janet F and Slatkin, Montgomery and Pääbo, Svante H}, journal = {Cell}, pages = {416 -- 426}, publisher = {Cell Press}, title = {{A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing}}, doi = {10.1016/j.cell.2008.06.021}, volume = {134}, year = {2008}, } @article{3409, abstract = {With the introduction of single-molecule force spectroscopy (SMFS) it has become possible to directly access the interactions of various molecular systems. A bottleneck in conventional SMFS is collecting the large amount of data required for statistically meaningful analysis. Currently, atomic force microscopy (AFM)-based SMFS requires the user to tediously 'fish' for single molecules. In addition, most experimental and environmental conditions must be manually adjusted. Here, we developed a fully automated single-molecule force spectroscope. The instrument is able to perform SMFS while monitoring and regulating experimental conditions such as buffer composition and temperature. Cantilever alignment and calibration can also be automatically performed during experiments. This, combined with in-line data analysis, enables the instrument, once set up, to perform complete SMFS experiments autonomously.}, author = {Struckmeier, Jens and Wahl, Reiner and Leuschner, Mirko and Nunes, Joao and Harald Janovjak and Geisler, Ulrich and Hofmann, Gerd and Jähnke, Torsten and Mueller, Daniel J}, journal = {Nanotechnology}, number = {38}, publisher = {IOP Publishing Ltd.}, title = {{Fully automated single-molecule force spectroscopy for screening applications}}, doi = {10.1088/0957-4484/19/38/384020}, volume = {19}, year = {2008}, } @misc{3410, abstract = {Membrane proteins are involved in essential biological processes such as energy conversion, signal transduction, solute transport and secretion. All biological processes, also those involving membrane proteins, are steered by molecular interactions. Molecular interactions guide the folding and stability of membrane proteins, determine their assembly, switch their functional states or mediate signal transduction. The sequential steps of molecular interactions driving these processes can be described by dynamic energy landscapes. The conceptual energy landscape allows to follow the complex reaction pathways of membrane proteins while its modifications describe why and how pathways are changed. Single-molecule force spectroscopy (SMFS) detects, quantifies and locates interactions within and between membrane proteins. SMFS helps to determine how these interactions change with temperature, point mutations, oligomerization and the functional states of membrane proteins. Applied in different modes, SMFS explores the co-existence and population of reaction pathways in the energy landscape of the protein and thus reveals detailed insights into local mechanisms, determining its structural and functional relationships. Here we review how SMFS extracts the defining parameters of an energy landscape such as the barrier position, reaction kinetics and roughness with high precision.}, author = {Harald Janovjak and Sapra, Tanuj K and Kedrov, Alexej and Mueller, Daniel J}, booktitle = {ChemPhysChem}, number = {7}, pages = {954 -- 966}, publisher = {Wiley-Blackwell}, title = {{From valleys to ridges: Exploring the energy landscape of single membrane proteins}}, doi = {10.1002/cphc.200700662}, volume = {9}, year = {2008}, } @article{13422, abstract = {Make like a leaf: The synthesis and characterization of a family of “flowerlike” Au/Fe3O4 nanoparticles is described, whereby Fe3O4 “leaves” adhere to a gold core (see image). The size and numbers of iron oxide domains can be adjusted flexibly by changing the proportion of the starting materials and the reaction time.}, author = {Wei, Yanhu and Klajn, Rafal and Pinchuk, Anatoliy O. and Grzybowski, Bartosz A.}, issn = {1613-6829}, journal = {Small}, keywords = {Biomaterials, Biotechnology, General Materials Science, General Chemistry}, number = {10}, pages = {1635--1639}, publisher = {Wiley}, title = {{Synthesis, shape control, and optical properties of hybrid Au/Fe3O4 “nanoflowers”}}, doi = {10.1002/smll.200800511}, volume = {4}, year = {2008}, } @article{13423, abstract = {Supraspheres (SS) composed of hundreds to thousands of metal nanoparticles (NPs) and crosslinked by dithiol linkers are assembled into larger structures, which are subsequently converted into nanoporous metals (NMs). Conversion is achieved by heating which removes organic molecules stabilizing the NPs and allows for NP fusion. Heating of SS solutions leads to NMs of overall macroscopic dimensions; localized radiation using collimated electron beam is used to prepare metallized surface micropatterns. Depending on the composition of supraspherical precursors, nanoporous materials composed of up to three metals can be obtained. Strategies for controlling pore size and nanoscale surface roughness of these materials are discussed.}, author = {Klajn, Rafal and Gray, Timothy P. and Wesson, Paul J. and Myers, Benjamin D. and Dravid, Vinayak P. and Smoukov, Stoyan K. and Grzybowski, Bartosz A.}, issn = {1616-3028}, journal = {Advanced Functional Materials}, keywords = {Electrochemistry, Condensed Matter Physics, Biomaterials, Electronic, Optical and Magnetic Materials}, number = {18}, pages = {2763--2769}, publisher = {Wiley}, title = {{Bulk synthesis and surface patterning of nanoporous metals and alloys from supraspherical nanoparticle aggregates}}, doi = {10.1002/adfm.200800293}, volume = {18}, year = {2008}, } @article{1460, abstract = {We calculate the E-polynomials of certain twisted GL(n,ℂ)-character varieties Mn of Riemann surfaces by counting points over finite fields using the character table of the finite group of Lie-type GL(n, q) and a theorem proved in the appendix by N. Katz. We deduce from this calculation several geometric results, for example, the value of the topological Euler characteristic of the associated PGL(n,ℂ)-character variety. The calculation also leads to several conjectures about the cohomology of Mn: an explicit conjecture for its mixed Hodge polynomial; a conjectured curious hard Lefschetz theorem and a conjecture relating the pure part to absolutely indecomposable representations of a certain quiver. We prove these conjectures for n=2.}, author = {Tamas Hausel and Rodríguez Villegas, Fernando}, journal = {Inventiones Mathematicae}, number = {3}, pages = {555 -- 624}, publisher = {Springer}, title = {{Mixed Hodge polynomials of character varieties: With an appendix by Nicholas M. Katz}}, doi = {10.1007/s00222-008-0142-x}, volume = {174}, year = {2008}, } @article{18032, abstract = {A comprehensive review is presented of single-molecule junction conductance measurements across families of molecules measured while breaking a gold point contact in a solution of molecules with amine end groups. A theoretical framework unifies the picture for the amine–gold link bonding and the tunnel coupling through the junction using density functional theory based calculations. The reproducible electrical characteristics and utility for many molecules is shown to result from the selective binding between the gold electrodes and amine link groups through a donor–acceptor bond to undercoordinated gold atoms. While the bond energy is modest, the maximum force sustained by the junction is comparable to, but less than, that required to break gold point contacts. The calculated tunnel coupling provides conductance trends for all 41 molecule measurements presented here, as well as insight into the variability of conductance due to the conformational changes within molecules with torsional degrees of freedom. The calculated trends agree to within a factor of 2 with the measured values for conductance ranging from 10−7G0 to 10−2G0, where G0 is the quantum of conductance (2e2/h).}, author = {Hybertsen, Mark S and Venkataraman, Latha and Klare, Jennifer E and Whalley, Adam C and Steigerwald, Michael L and Nuckolls, Colin}, issn = {1361-648X}, journal = {Journal of Physics: Condensed Matter}, number = {37}, publisher = {IOP Publishing}, title = {{Amine-linked single-molecule circuits: Systematic trends across molecular families}}, doi = {10.1088/0953-8984/20/37/374115}, volume = {20}, year = {2008}, } @inproceedings{18033, abstract = {We measure the conductance of over 30 amine terminated molecules by breaking Au point-contacts in a molecular solution at room temperature. We find that the variability of the observed conductance for the diamine molecule-Au junctions is much less than the variability for diisonitrile and dithiol-Au junctions. This narrow distribution enables unambiguous conductance measurements of single molecules. For an alkane diamine series with 2-8 carbon atoms in the hydrocarbon chain and for polyphenyl diamine with 1-3 benzene rings, our results show that conductance decreases exponentially with length. For biphenyl diamines with different substituents that alter the phenyl-phenyl dihedral angle, we find that the conductance decreases with increasing twist angle, following a cosine squared dependence. Finally, for a series of substituted benzene diamines, we find that electron donating substituents on the ring, which drive the occupied molecular orbitals up, increase the junction conductance while electron withdrawing substituents have the opposite effect. Thus for this measured series, conductance varies inversely with the calculated ionization potential of the molecules. These results reveal that the occupied states are closest to the gold Fermi energy, indicating that the tunneling transport through these molecules is analogous to hole tunneling through an insulating film.}, author = {Venkataraman, Latha}, booktitle = {2008 International Symposium on VLSI Technology, Systems and Applications}, issn = {1930-885X}, location = {Hsinchu, Taiwan}, pages = {64--65}, publisher = {IEEE}, title = {{Molecule Nanoelectronics}}, doi = {10.1109/vtsa.2008.4530800}, year = {2008}, } @article{18034, abstract = {The ability to perform optical measurements on a single molecule placed between two electrodes while also measuring the current flowing through it could herald a new generation of experiments on molecular junctions.}, author = {Venkataraman, Latha}, issn = {1748-3395}, journal = {Nature Nanotechnology}, number = {4}, pages = {187--188}, publisher = {Springer Nature}, title = {{Seeing is believing}}, doi = {10.1038/nnano.2008.81}, volume = {3}, year = {2008}, } @article{1826, abstract = {Proliferating cell populations at steady-state growth often exhibit broad protein distributions with exponential tails. The sources of this variation and its universality are of much theoretical interest. Here we address the problem by asymptotic analysis of the population balance equation. We show that the steady-state distribution tail is determined by a combination of protein production and cell division and is insensitive to other model details. Under general conditions this tail is exponential with a dependence on parameters consistent with experiment. We discuss the conditions for this effect to be dominant over other sources of variation and the relation to experiments.}, author = {Tamar Friedlander and Brenner, Naama}, journal = {Physical Review Letters}, number = {1}, publisher = {American Physical Society}, title = {{Cellular properties and population asymptotics in the population balance equation}}, doi = {10.1103/PhysRevLett.101.018104}, volume = {101}, year = {2008}, } @inproceedings{18337, abstract = {Matching of rigid shapes is an important problem in numerous applications across the boundary of computer vision, pattern recognition and computer graphics communities. A particularly challenging setting of this problem is partial matching, where the two shapes are dissimilar in general, but have significant similar parts. In this paper, we show a rigorous approach allowing to find matching parts of rigid shapes with controllable size and regularity. The regularity term we use is similar to the spirit of the Mumford-Shah functional, extended to non-Euclidean spaces. Numerical experiments show that the regularized partial matching produces better results compared to the non-regularized one.}, author = {Bronstein, Alexander and Bronstein, Michael M.}, booktitle = {10th European Conference on Computer Vision}, isbn = {9783540886853}, issn = {0302-9743}, location = {Marseille, France}, pages = {143--154}, publisher = {Springer Berlin Heidelberg}, title = {{Regularized partial matching of rigid shapes}}, doi = {10.1007/978-3-540-88688-4_11}, volume = {5303}, year = {2008}, } @article{18355, abstract = {Analysis of deformable two-dimensional shapes is an important problem, encountered in numerous pattern recognition, computer vision and computer graphics applications. In this paper, we address three major problems in the analysis of non-rigid shapes: similarity, partial similarity, and correspondence. We present an axiomatic construction of similarity criteria for deformation-invariant shape comparison, based on intrinsic geometric properties of the shapes, and show that such criteria are related to the Gromov-Hausdorff distance. Next, we extend the problem of similarity computation to shapes which have similar parts but are dissimilar when considered as a whole, and present a construction of set-valued distances, based on the notion of Pareto optimality. Finally, we show that the correspondence between non-rigid shapes can be obtained as a byproduct of the non-rigid similarity problem. As a numerical framework, we use the generalized multidimensional scaling (GMDS) method, which is the numerical core of the three problems addressed in this paper.}, author = {Bronstein, Alexander and Bronstein, Michael M. and Bruckstein, Alfred M. and Kimmel, Ron}, issn = {0920-5691}, journal = {International Journal of Computer Vision}, pages = {67--88}, publisher = {Springer Nature}, title = {{Analysis of two-dimensional non-rigid shapes}}, doi = {10.1007/s11263-007-0078-4}, volume = {78}, year = {2008}, }