@article{3028, abstract = {In plants, cell polarity and tissue patterning are connected by intercellular flow of the phytohormone auxin, whose directional signaling depends on polar subcellular localization of PIN auxin transport proteins. The mechanism of polar targeting of PINs or other cargos in plants is largely unidentified, with the PINOID kinase being the only known molecular component. Here, we identify PP2A phosphatase as an important regulator of PIN apical-basal targeting and auxin distribution. Genetic analysis, localization, and phosphorylation studies demonstrate that PP2A and PINOID both partially colocalize with PINs and act antagonistically on the phosphorylation state of their central hydrophilic loop, hence mediating PIN apical-basal polar targeting. Thus, in plants, polar sorting by the reversible phosphorylation of cargos allows for their conditional delivery to specific intracellular destinations. In the case of PIN proteins, this mechanism enables switches in the direction of intercellular auxin fluxes, which mediate differential growth, tissue patterning, and organogenesis.}, author = {Michniewicz, Marta and Zago, Marcelo K and Abas, Lindy and Weijers, Dolf and Schweighofer, Alois and Meskiene, Irute and Heisler, Marcus G and Ohno, Carolyn and Zhang, Jing and Huang, Fang and Schwab, Rebecca and Weigel, Detlef and Meyerowitz, Elliot M and Luschnig, Christian and Offringa, Remko and Jirí Friml}, journal = {Cell}, number = {6}, pages = {1044 -- 1056}, publisher = {Cell Press}, title = {{Antagonistic regulation of PIN phosphorylation by PP2A and PINOID directs auxin flux}}, doi = {10.1016/j.cell.2007.07.033}, volume = {130}, year = {2007}, } @article{3029, abstract = {In Arabidopsis thaliana, lateral roots are formed from root pericycle cells adjacent to the xylem poles. Lateral root development is regulated antagonistically by the plant hormones auxin and cytokinin. While a great deal is known about how auxin promotes lateral root development, the mechanism of cytokinin repression is still unclear. Elevating cytokinin levels was observed to disrupt lateral root initiation and the regular pattern of divisions that characterizes lateral root development in Arabidopsis. To identify the stage of lateral root development that is sensitive to cytokinins, we targeted the expression of the Agrobacterium tumefaciens cytokinin biosynthesis enzyme isopentenyltransferase to either xylem-pole pericycle cells or young lateral root primordia using GAL4-GFP enhancer trap lines. Transactivation experiments revealed that xylem-pole pericycle cells are sensitive to cytokinins, whereas young lateral root primordia are not. This effect is physiologically significant because transactivation of the Arabidopsis cytokinin degrading enzyme cytokinin oxidase 1 in lateral root founder cells results in increased lateral root formation. We observed that cytokinins perturb the expression of PIN genes in lateral root founder cells and prevent the formation of an auxin gradient that is required to pattern lateral root primordia.}, author = {Laplaze, Laurent and Eva Benková and Casimiro, Ilda and Maes, Lies and Vanneste, Steffen and Swarup, Ranjan and Weijers, Dolf and Calvo, Vanessa and Parizot, Boris and Herrera-Rodriguez, Maria Begoña and Offringa, Remko and Graham, Neil and Doumas, Patrick and Jirí Friml and Bogusz, Didier and Beeckman, Tom and Bennett, Malcolm}, journal = {Plant Cell}, number = {12}, pages = {3889 -- 3900}, publisher = {American Society of Plant Biologists}, title = {{Cytokinins act directly on lateral root founder cells to inhibit root initiation}}, doi = {10.1105/tpc.107.055863}, volume = {19}, year = {2007}, } @article{3144, abstract = {Accumulation of specific proteins at synaptic structures is essential for synapse assembly and function, but mechanisms regulating local protein enrichment remain poorly understood. At the neuromuscular junction (NMJ), subsynaptic nuclei underlie motor axon terminals within extrafusal muscle fibers and are transcriptionally distinct from neighboring nuclei. In this study, we show that expression of the ETS transcription factor Erm is highly concentrated at subsynaptic nuclei, and its mutation in mice leads to severe downregulation of many genes with normally enriched subsynaptic expression. Erm mutant mice display an expansion of the muscle central domain in which acetylcholine receptor (AChR) clusters accumulate, show gradual fragmentation of AChR clusters, and exhibit symptoms of muscle weakness mimicking congenital myasthenic syndrome (CMS). Together, our findings define Erm as an upstream regulator of a transcriptional program selective to subsynaptic nuclei at the NMJ and underscore the importance of transcriptional control of local synaptic protein accumulation.}, author = {Simon Hippenmeyer and Huber, Roland M and Ladle, David R and Murphy, Kenneth and Arber, Silvia}, journal = {Neuron}, number = {5}, pages = {726 -- 740}, publisher = {Elsevier}, title = {{ETS transcription factor Erm controls subsynaptic gene expression in skeletal muscles}}, doi = {10.1016/j.neuron.2007.07.028}, volume = {55}, year = {2007}, } @article{3187, abstract = {Stereo vision has numerous applications in robotics, graphics, inspection and other areas. A prime application, one which has driven work on stereo in our laboratory, is teleconferencing in which the use of a stereo webcam already makes possible various transformations of the video stream. These include digital camera control, insertion of virtual objects, background substitution, and eye-gaze correction [9, 8].}, author = {Blake, Andrew and Criminisi, Antonio and Cross, Geoffrey and Vladimir Kolmogorov and Rother, Carsten}, journal = {Springer Tracts in Advanced Robotics}, pages = {295 -- 304}, publisher = {Springer}, title = {{Fusion of stereo colour and contrast}}, doi = {10.1007/978-3-540-48113-3_27}, volume = {28}, year = {2007}, } @inproceedings{3191, abstract = {The maximum flow algorithm for minimizing energy functions of binary variables has become a standard tool in computer vision. In many cases, unary costs of the energy depend linearly on parameter lambda. In this paper we study vision applications for which it is important to solve the maxflow problem for different lambda's. An example is a weighting between data and regularization terms in image segmentation or stereo: it is desirable to vary it both during training (to learn lambda from ground truth data) and testing (to select best lambda using high-knowledge constraints, e.g. user input). We review algorithmic aspects of this parametric maximum flow problem previously unknown in vision, such as the ability to compute all breakpoints of lambda and corresponding optimal configurations infinite time. These results allow, in particular, to minimize the ratio of some geometric functional, such as flux of a vector field over length (or area). Previously, such functional were tackled with shortest path techniques applicable only in 2D. We give theoretical improvements for "PDE cuts" [5]. We present experimental results for image segmentation, 3D reconstruction, and the cosegmentation problem.}, author = {Vladimir Kolmogorov and Boykov, Yuri and Rother, Carsten}, publisher = {IEEE}, title = {{Applications of parametric maxflow in computer vision}}, doi = {10.1109/ICCV.2007.4408910}, year = {2007}, } @inproceedings{3192, abstract = {Many computer vision applications rely on the efficient optimization of challenging, so-called non-submodular, binary pairwise MRFs. A promising graph cut based approach for optimizing such MRFs known as "roof duality" was recently introduced into computer vision. We study two methods which extend this approach. First, we discuss an efficient implementation of the "probing" technique introduced recently by Boros et al. [5]. It simplifies the MRF while preserving the global optimum. Our code is 400-700 faster on some graphs than the implementation of [5]. Second, we present a new technique which takes an arbitrary input labeling and tries to improve its energy. We give theoretical characterizations of local minima of this procedure. We applied both techniques to many applications, including image segmentation, new view synthesis, superresolution, diagram recognition, parameter learning, texture restoration, and image deconvolution. For several applications we see that we are able to find the global minimum very efficiently, and considerably outperform the original roof duality approach. In comparison to existing techniques, such as graph cut, TRW, BP, ICM, and simulated annealing, we nearly always find a lower energy.}, author = {Rother, Carsten and Vladimir Kolmogorov and Lempitsky, Victor and Szummer, Martin}, publisher = {IEEE}, title = {{Optimizing binary MRFs via extended roof duality}}, doi = {10.1109/CVPR.2007.383203}, year = {2007}, } @article{3193, abstract = {Optimization techniques based on graph cuts have become a standard tool for many vision applications. These techniques allow to minimize efficiently certain energy functions corresponding to pairwise Markov Random Fields (MRFs). Currently, there is an accepted view within the computer vision community that graph cuts can only be used for optimizing a limited class of MRF energies (e.g., submodular functions). In this survey, we review some results that show that graph cuts can be applied to a much larger class of energy functions (in particular, nonsubmodular functions). While these results are well-known in the optimization community, to our knowledge they were not used in the context of computer vision and MRF optimization. We demonstrate the relevance of these results to vision on the problem of binary texture restoration. }, author = {Vladimir Kolmogorov and Rother, Carsten}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {7}, pages = {1274 -- 1279}, publisher = {IEEE}, title = {{Minimizing nonsubmodular functions with graph cuts - A review}}, doi = {10.1109/TPAMI.2007.1031}, volume = {29}, year = {2007}, } @inproceedings{3218, abstract = {A (k, ℓ)-robust combiner for collision-resistant hash-functions is a construction which from ℓ hash-functions constructs a hash-function which is collision-resistant if at least k of the components are collision-resistant. One trivially gets a (k, ℓ)-robust combiner by concatenating the output of any ℓ - k + 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box (k, ℓ)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06). }, author = {Krzysztof Pietrzak}, pages = {23 -- 33}, publisher = {Springer}, title = {{Non-trivial black-box combiners for collision-resistant hash-functions don't exist}}, doi = {10.1007/978-3-540-72540-4_2}, volume = {4515}, year = {2007}, } @inproceedings{3219, abstract = {Many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, assuming upper bounds of certain types for the component systems. For a general type of combination operation of systems, including the XOR of functions or the cascade of permutations, we prove two amplification theorems. The first is a product theorem, in the spirit of XOR-lemmas: The distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. This bound is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers. A key technical tool of the paper is the proof of a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of winning an appropriately defined game. © International Association for Cryptologic Research 2007.}, author = {Maurer, Ueli M and Krzysztof Pietrzak and Renner, Renato}, pages = {130 -- 149}, publisher = {Springer}, title = {{Indistinguishability amplification}}, doi = {10.1007/978-3-540-74143-5_8}, volume = {4622}, year = {2007}, } @inproceedings{3220, abstract = {We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.}, author = {Dziembowski, Stefan and Krzysztof Pietrzak}, pages = {227 -- 237}, publisher = {IEEE}, title = {{Intrusion resilient secret sharing}}, doi = {10.1109/FOCS.2007.63}, year = {2007}, } @inproceedings{3221, abstract = {We investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on m independent functions F 1,...,F m is given by a set of strings over {1,...,m}*, where for example {〈2〉, 〈1,2〉} corresponds to the function X ↦[F 2(X),F 2(F 1(X))]. All efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form. We completely classify such constructions as good, bad or ugly, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose insecurity can be proven via a black-box reduction, and the ugly constructions are those which are neither good nor bad. Our classification shows that the range expansion from [10] is optimal, in the sense that it achieves the best possible expansion (2 m  − 1 when using m keys). Along the way we show that for weak quasirandom functions (i.e. in the information theoretic setting), all constructions which are not bad – in particular all the ugly ones – are secure.}, author = {Krzysztof Pietrzak and Sjödin, Johan}, pages = {517 -- 533}, publisher = {Springer}, title = {{Range extension for weak PRFs the good the bad and the ugly}}, doi = {10.1007/978-3-540-72540-4_30}, volume = {4515}, year = {2007}, } @inproceedings{3222, abstract = {Parallel repetition is well known to reduce the error probability at an exponential rate for single- and multi-prover interactive proofs. Bellare, Impagliazzo and Naor (1997) show that this is also true for protocols where the soundness only holds against computationally bounded provers (e.g. interactive arguments) if the protocol has at most three rounds. On the other hand, for four rounds they give a protocol where this is no longer the case: the error probability does not decrease below some constant even if the protocol is repeated a polynomial number of times. Unfortunately, this protocol is not very convincing as the communication complexity of each instance of the protocol grows linearly with the number of repetitions, and for such protocols the error does not even decrease for some types of interactive proofs. Noticing this, Bellare et al. construct (a quite artificial) oracle relative to which a four round protocol exists whose communication complexity does not depend on the number of parallel repetitions. This shows that there is no “black-box” error reduction theorem for four round protocols. In this paper we give the first computationally sound protocol where k-fold parallel repetition does not decrease the error probability below some constant for any polynomial k (and where the communication complexity does not depend on k). The protocol has eight rounds and uses the universal arguments of Barak and Goldreich (2001). We also give another four round protocol relative to an oracle, unlike the artificial oracle of Bellare et al., we just need a generic group. This group can then potentially be instantiated with some real group satisfying some well defined hardness assumptions (we do not know of any candidate for such a group at the moment).}, author = {Krzysztof Pietrzak and Wikström, Douglas}, pages = {86 -- 102}, publisher = {Springer}, title = {{Parallel repetition of computationally sound protocols revisited}}, doi = {10.1007/978-3-540-70936-7_5}, volume = {4392}, year = {2007}, } @inproceedings{3223, abstract = {“Hash then encrypt” is an approach to message authentication, where first the message is hashed down using an ε-universal hash function, and then the resulting k-bit value is encrypted, say with a block-cipher. The security of this scheme is proportional to εq2, where q is the number of MACs the adversary can request. As ε is at least 2−k, the best one can hope for is O(q2/2k) security. Unfortunately, such small ε is not achieved by simple hash functions used in practice, such as the polynomial evaluation or the Merkle-Damg ̊ard construction, where ε grows with the message length L. The main insight of this work comes from the fact that, by using ran- domized message preprocessing via a short random salt p (which must then be sent as part of the authentication tag), we can use the “hash then encrypt” paradigm with suboptimal “practical” ε-universal hash func- tions, and still improve its exact security to optimal O(q2/2k). Specif- ically, by using at most an O(logL)-bit salt p, one can always regain the optimal exact security O(q2/2k), even in situations where ε grows polynomially with L. We also give very simple preprocessing maps for popular “suboptimal” hash functions, namely polynomial evaluation and the Merkle-Damg ̊ard construction. Our results come from a general extension of the classical Carter- Wegman paradigm, which we believe is of independent interest. On a high level, it shows that public randomization allows one to use the potentially much smaller “average-case” collision probability in place of the “worst-case” collision probability ε.}, author = {Dodis, Yevgeniy and Krzysztof Pietrzak}, pages = {414 -- 433}, publisher = {Springer}, title = {{Improving the security of MACs via randomized message preprocessing}}, doi = {10.1007/978-3-540-74619-5_26}, volume = {4593}, year = {2007}, } @article{3305, abstract = {The accumulation of deleterious mutations plays a major role in evolution, and key to this are the interactions between their fitness effects, known as epistasis. Whether mutations tend to interact synergistically (with multiple mutations being more deleterious than would be expected from their individual fitness effects) or antagonistically is important for a variety of evolutionary questions, particularly the evolution of sex. Unfortunately, the experimental evidence on the prevalence and strength of epistasis is mixed and inconclusive. Here we study theoretically whether synergistic or antagonistic epistasis is likely to be favored by evolution and by how much. We find that in the presence of recombination, evolution favors less synergistic or more antagonistic epistasis whenever mutations that change the epistasis in this direction are possible. This is because evolution favors increased buffering against the effects of deleterious mutations. This suggests that we should not expect synergistic epistasis to be widespread in nature and hence that the mutational deterministic hypothesis for the advantage of sex may not apply widely.}, author = {Desai, Michael M and Daniel Weissman and Feldman, Marcus W}, journal = {Genetics}, number = {2}, pages = {1001 -- 10}, publisher = {Genetics Society of America}, title = {{Evolution can favor antagonistic epistasis}}, doi = {10.1534/genetics.107.075812}, volume = {177}, year = {2007}, } @article{3411, abstract = {Mechanical single-molecule techniques offer exciting possibilities to investigate protein folding and stability in native environments at submolecular resolution. By applying a free-energy reconstruction procedure developed by Hummer and Szabo, which is based on a statistical theorem introduced by Jarzynski, we determined the unfolding free energy of the membrane proteins bacteriorhodopsin (BR), halorhodopsin, and the sodium-proton antiporter NhaA. The calculated energies ranged from 290.5kcal/mol for BR to 485.5kcal/mol for NhaA. For the remarkably stable BR, the equilibrium unfolding free energy was independent of pulling rate and temperature ranging between 18 and 42°C. Our experiments also revealed heterogeneous energetic properties in individual transmembrane helices. In halorhodopsin, the stabilization of a short helical segment yielded a characteristic signature in the energy profile. In NhaA, a pronounced peak was observed at a functionally important site in the protein. Since a large variety of single- and multispan membrane proteins can be tackled in mechanical unfolding experiments, our approach provides a basis for systematically elucidating energetic properties of membrane proteins with the resolution of individual secondary-structure elements.}, author = {Preiner, Johannes and Harald Janovjak and Rankl, Christian and Knaus, Helene and Cisneros, David A and Kedrov, Alexej and Kienberger, Ferry and Mueller, Daniel J and Hinterdorfer, Peter}, journal = {Biophysical Journal}, number = {3}, pages = {930 -- 937}, publisher = {Biophysical Society}, title = {{Free energy of membrane protein unfolding derived from single-molecule force measurements}}, doi = {10.1529/biophysj.106.096982}, volume = {93}, year = {2007}, } @misc{3412, abstract = {Molecular interactions are the basic language of biological processes. They establish the forces interacting between the building blocks of proteins and other macromolecules, thus determining their functional roles. Because molecular interactions trigger virtually every biological process, approaches to decipher their language are needed. Single-molecule force spectroscopy (SMFS) has been used to detect and characterize different types of molecular interactions that occur between and within native membrane proteins. The first experiments detected and localized molecular interactions that stabilized membrane proteins, including how these interactions were established during folding of α-helical secondary structure elements into the native protein and how they changed with oligomerization, temperature, and mutations. SMFS also enables investigators to detect and locate molecular interactions established during ligand and inhibitor binding. These exciting applications provide opportunities for studying the molecular forces of life. Further developments will elucidate the origins of molecular interactions encoded in their lifetimes, interaction ranges, interplay, and dynamics characteristic of biological systems.}, author = {Kedrov, Alexej and Harald Janovjak and Sapra, Tanuj K and Mueller, Daniel J}, booktitle = {Annual Review of Biophysics}, pages = {233 -- 260}, publisher = {Annual Reviews}, title = {{Deciphering molecular interactions of native membrane proteins by single-molecule force spectroscopy}}, doi = {10.1146/annurev.biophys.36.040306.132640}, volume = {36}, year = {2007}, } @article{13424, abstract = {Changing shapes: Metastable spherical aggregates of gold nanoparticles undergo a one-to-one, thermally induced transformation into heterodimers comprising connected plate and spherical domains. By controlling the reaction time, it is possible to isolate a variety of structures differing in the relative sizes of the domains and in the overall optical properties (see picture).}, author = {Klajn, Rafal and Pinchuk, Anatoliy O. and Schatz, George C. and Grzybowski, Bartosz A.}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, keywords = {General Chemistry, Catalysis}, number = {44}, pages = {8363--8367}, publisher = {Wiley}, title = {{Synthesis of heterodimeric sphere–prism nanostructures via metastable gold supraspheres}}, doi = {10.1002/anie.200702570}, volume = {46}, year = {2007}, } @article{13425, abstract = {Nanoparticles (NPs) decorated with ligands combining photoswitchable dipoles and covalent cross-linkers can be assembled by light into organized, three-dimensional suprastructures of various types and sizes. NPs covered with only few photoactive ligands form metastable crystals that can be assembled and disassembled “on demand” by using light of different wavelengths. For higher surface concentrations, self-assembly is irreversible, and the NPs organize into permanently cross-linked structures including robust supracrystals and plastic spherical aggregates.}, author = {Klajn, Rafal and Bishop, Kyle J. M. and Grzybowski, Bartosz A.}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {Multidisciplinary}, number = {25}, pages = {10305--10309}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Light-controlled self-assembly of reversible and irreversible nanoparticle suprastructures}}, doi = {10.1073/pnas.0611371104}, volume = {104}, year = {2007}, } @article{13426, abstract = {Photoswelling of thin films of dichromated gelatin provides a basis for fabrication of multilevel surface reliefs via sequential UV illumination through different photomasks. The remarkable feature of this simple, benchtop technique is that by adjusting irradiation times, film thickness, or its hydration state the heights of the developed features can be varied from few nanometers to tens of microns. After UV exposure, the surface structures can be replicated faithfully into either soft or hard PDMS stamps.}, author = {Paszewski, Maciej and Smoukov, Stoyan K. and Klajn, Rafal and Grzybowski, Bartosz A.}, issn = {1520-5827}, journal = {Langmuir}, keywords = {Electrochemistry, Spectroscopy, Surfaces and Interfaces, Condensed Matter Physics, General Materials Science}, number = {10}, pages = {5419--5422}, publisher = {American Chemical Society}, title = {{Multilevel surface nano- and microstructuring via sequential photoswelling of dichromated gelatin}}, doi = {10.1021/la062982c}, volume = {23}, year = {2007}, } @article{13427, abstract = {Deformable, spherical aggregates of metal nanoparticles connected by long-chain dithiol ligands self-assemble into nanostructured materials of macroscopic dimensions. These materials are plastic and moldable against arbitrarily shaped masters and can be thermally hardened into polycrystalline metal structures of controllable porosity. In addition, in both plastic and hardened states, the assemblies are electrically conductive and exhibit Ohmic characteristics down to ∼20 volts per meter. The self-assembly method leading to such materials is applicable both to pure metals and to bimetallic structures of various elemental compositions.}, author = {Klajn, Rafal and Bishop, Kyle J. M. and Fialkowski, Marcin and Paszewski, Maciej and Campbell, Christopher J. and Gray, Timothy P. and Grzybowski, Bartosz A.}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {5822}, pages = {261--264}, publisher = {American Association for the Advancement of Science}, title = {{Plastic and moldable metals by self-assembly of sticky nanoparticle aggregates}}, doi = {10.1126/science.1139131}, volume = {316}, year = {2007}, }