@inproceedings{2978, abstract = {Efficient zero-knowledge proofs of knowledge for group homomorphisms are essential for numerous systems in applied cryptography. Especially, Σ-protocols for proving knowledge of discrete logarithms in known and hidden order groups are of prime importance. Yet, while these proofs can be performed very efficiently within groups of known order, for hidden order groups the respective proofs are far less efficient. This paper shows strong evidence that this efficiency gap cannot be bridged. Namely, while there are efficient protocols allowing a prover to cheat only with negligibly small probability in the case of known order groups, we provide strong evidence that for hidden order groups this probability is bounded below by 1/2 for all efficient Σ-protocols not using common reference strings or the like. We prove our results for a comprehensive class of Σ-protocols in the generic group model, and further strengthen them by investigating certain instantiations in the plain model.}, author = {Bangerter, Endre and Camenisch, Jan and Stephan Krenn}, editor = {Micciancio, Daniele}, pages = {553 -- 571}, publisher = {Springer}, title = {{Efficiency Limitations for Σ-Protocols for Group Homomorphisms}}, doi = {10.1007/978-3-642-11799-2}, volume = {5978}, year = {2010}, } @inproceedings{2979, abstract = {Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have a high potential impact, their real world deployment is typically hindered by their significant complexity compared to other (non-interactive) crypto primitives. Moreover, their design and implementation are time-consuming and error-prone. We contribute to overcoming these challenges as follows: We present a comprehensive specification language and a compiler for ZK-PoK protocols based on Σ-protocols. The compiler allows the fully automatic translation of an abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain, needed for privacy-preserving applications such as DAA. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of the soundness of the compiled protocol for a large class of protocols using the Isabelle/HOL theorem prover. }, author = {Almeida, José Bacelar and Bangerter, Endre and Barbosa, Manuel and Stephan Krenn and Sadeghi, Ahmad-Reza and Schneider, Thomas}, editor = {Gritzalis, Dimitris and Preneel, Bart and Theoharidou, Marianthi}, pages = {151 -- 167}, publisher = {Springer}, title = {{A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols}}, doi = {10.1007/978-3-642-15497-3}, volume = {6345}, year = {2010}, } @inproceedings{2980, abstract = {Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multi-party computation (SMPC). Currently, first applications that essentially rely on ZK-PoKs are being deployed in the real world. The most prominent example is the Direct Anonymous Attestation (DAA) protocol, which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM). Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are significantly more complex than standard crypto primitives (e.g., encryption and signature schemes). As a result, the design-implementation cycles of ZK-PoK are time-consuming and error-prone. To overcome this, we present a compiler with corresponding languages for the automatic generation of sound and efficient ZK-PoK based on Σ-protocols. The protocol designer using our compiler formulates the goal of a ZK-PoK proof in a high-level protocol specification language, which abstracts away unnecessary technicalities from the designer. The compiler then automatically generates the protocol implementation in Java code; alternatively, the compiler can output a description of the protocol in LaTeX which can be used for documentation or verification.}, author = {Bangerter, Endre and Briner, Thomas and Henecka, Wilko and Stephan Krenn and Sadeghi, Ahmad-Reza and Schneider, Thomas}, editor = {Martinelli, Fabio and Preneel, Bart}, pages = {67 -- 82}, publisher = {Springer}, title = {{Automatic Generation of Sigma-Protocols}}, doi = {10.1007/978-3-642-16441-5}, volume = {6391}, year = {2010}, } @article{3072, abstract = {Development of plants and their adaptive capacity towards ever‐changing environmental conditions largely depend on the spatial distribution of the plant hormone auxin. At the cellular level, various internal and external signals are translated into specific changes in the polar, subcellular localization of auxin transporters from the PIN family thereby directing and redirecting the intercellular fluxes of auxin. The current model of polar targeting of PIN proteins towards different plasma membrane domains encompasses apolar secretion of newly synthesized PINs followed by endocytosis and recycling back to the plasma membrane in a polarized manner. In this review, we follow the subcellular march of the PINs and highlight the cellular and molecular mechanisms behind polar foraging and subcellular trafficking pathways. Also, the entry points for different signals and regulations including by auxin itself will be discussed within the context of morphological and developmental consequences of polar targeting and subcellular trafficking.}, author = {Grunewald, Wim and Friml, Jirí}, journal = {EMBO Journal}, number = {16}, pages = {2700 -- 2714}, publisher = {Wiley-Blackwell}, title = {{The march of the PINs: Developmental plasticity by dynamic polar targeting in plant cells}}, doi = {10.1038/emboj.2010.181}, volume = {29}, year = {2010}, } @article{3077, author = {Friml, Jirí and Jones, Angharad}, journal = {Plant Physiology}, number = {2}, pages = {458 -- 462}, publisher = {American Society of Plant Biologists}, title = {{Endoplasmic reticulum: The rising compartment in auxin biology}}, doi = {10.1104/pp.110.161380}, volume = {154}, year = {2010}, } @article{3303, abstract = {Biological traits result in part from interactions between different genetic loci. This can lead to sign epistasis, in which a beneficial adaptation involves a combination of individually deleterious or neutral mutations; in this case, a population must cross a “fitness valley” to adapt. Recombination can assist this process by combining mutations from different individuals or retard it by breaking up the adaptive combination. Here, we analyze the simplest fitness valley, in which an adaptation requires one mutation at each of two loci to provide a fitness benefit. We present a theoretical analysis of the effect of recombination on the valley-crossing process across the full spectrum of possible parameter regimes. We find that low recombination rates can speed up valley crossing relative to the asexual case, while higher recombination rates slow down valley crossing, with the transition between the two regimes occurring when the recombination rate between the loci is approximately equal to the selective advantage provided by the adaptation. In large populations, if the recombination rate is high and selection against single mutants is substantial, the time to cross the valley grows exponentially with population size, effectively meaning that the population cannot acquire the adaptation. Recombination at the optimal (low) rate can reduce the valley-crossing time by up to several orders of magnitude relative to that in an asexual population. }, author = {Weissman, Daniel and Feldman, Marcus and Fisher, Daniel}, journal = {Genetics}, number = {4}, pages = {1389 -- 1410}, publisher = {Genetics Society of America}, title = {{The rate of fitness-valley crossing in sexual populations}}, doi = {10.1534/genetics.110.123240}, volume = {186}, year = {2010}, } @article{3306, abstract = {We use methods from combinatorics and algebraic statistics to study analogues of birth-and-death processes that have as their state space a finite subset of the m-dimensional lattice and for which the m matrices that record the transition probabilities in each of the lattice directions commute pairwise. One reason such processes are of interest is that the transition matrix is straightforward to diagonalize, and hence it is easy to compute n step transition probabilities. The set of commuting birth-and-death processes decomposes as a union of toric varieties, with the main component being the closure of all processes whose nearest neighbor transition probabilities are positive. We exhibit an explicit monomial parametrization for this main component, and we explore the boundary components using primary decomposition.}, author = {Evans, Steven N and Sturmfels, Bernd and Caroline Uhler}, journal = {The Annals of Applied Probability}, pages = {238 -- 266}, publisher = {Institute of Mathematical Statistics}, title = {{Commuting birth and death processes}}, doi = {10.1214/09-AAP615}, volume = {20}, year = {2010}, } @article{3308, abstract = {We study multivariate normal models that are described by linear constraints on the inverse of the covariance matrix. Maximum likelihood estimation for such models leads to the problem of maximizing the determinant function over a spectrahedron, and to the problem of characterizing the image of the positive definite cone under an arbitrary linear projection. These problems at the interface of statistics and optimization are here examined from the perspective of convex algebraic geometry.}, author = {Sturmfels, Bernd and Caroline Uhler}, journal = {Annals of the Institute of Statistical Mathematics}, number = {4}, pages = {603 -- 638}, publisher = {Springer}, title = {{Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry}}, doi = {10.1007/s10463-010-0295-4}, volume = {62}, year = {2010}, } @inproceedings{10908, abstract = {We present ABC, a software tool for automatically computing symbolic upper bounds on the number of iterations of nested program loops. The system combines static analysis of programs with symbolic summation techniques to derive loop invariant relations between program variables. Iteration bounds are obtained from the inferred invariants, by replacing variables with bounds on their greatest values. We have successfully applied ABC to a large number of examples. The derived symbolic bounds express non-trivial polynomial relations over loop variables. We also report on results to automatically infer symbolic expressions over harmonic numbers as upper bounds on loop iteration counts.}, author = {Blanc, Régis and Henzinger, Thomas A and Hottelier, Thibaud and Kovács, Laura}, booktitle = {Logic for Programming, Artificial Intelligence, and Reasoning}, editor = {Clarke, Edmund M and Voronkov, Andrei}, isbn = {9783642175107}, issn = {1611-3349}, location = {Dakar, Senegal}, pages = {103--118}, publisher = {Springer Nature}, title = {{ABC: Algebraic Bound Computation for loops}}, doi = {10.1007/978-3-642-17511-4_7}, volume = {6355}, year = {2010}, } @article{11098, author = {HETZER, Martin W}, issn = {1945-4589}, journal = {Aging}, keywords = {Cell Biology, Aging}, number = {2}, pages = {74--75}, publisher = {Impact Journals}, title = {{The role of the nuclear pore complex in aging of post-mitotic cells}}, doi = {10.18632/aging.100125}, volume = {2}, year = {2010}, } @article{11101, abstract = {In metazoa, nuclear pore complexes (NPCs) assemble from disassembled precursors into a reforming nuclear envelope (NE) at the end of mitosis and into growing intact NEs during interphase. Here, we show via RNAi-mediated knockdown that ELYS, a nucleoporin critical for the recruitment of the essential Nup107/160 complex to chromatin, is required for NPC assembly at the end of mitosis but not during interphase. Conversely, the transmembrane nucleoporin POM121 is critical for the incorporation of the Nup107/160 complex into new assembly sites specifically during interphase. Strikingly, recruitment of the Nup107/160 complex to an intact NE involves a membrane curvature-sensing domain of its constituent Nup133, which is not required for postmitotic NPC formation. Our results suggest that in organisms with open mitosis, NPCs assemble via two distinct mechanisms to accommodate cell cycle-dependent differences in NE topology.}, author = {Doucet, Christine M. and Talamas, Jessica A. and HETZER, Martin W}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {6}, pages = {1030--1041}, publisher = {Elsevier}, title = {{Cell cycle-dependent differences in nuclear pore complex assembly in metazoa}}, doi = {10.1016/j.cell.2010.04.036}, volume = {141}, year = {2010}, } @article{11102, abstract = {Nuclear pore complexes have recently been shown to play roles in gene activation; however their potential involvement in metazoan transcription remains unclear. Here we show that the nucleoporins Sec13, Nup98, and Nup88, as well as a group of FG-repeat nucleoporins, bind to the Drosophila genome at functionally distinct loci that often do not represent nuclear envelope contact sites. Whereas Nup88 localizes to silent loci, Sec13, Nup98, and a subset of FG-repeat nucleoporins bind to developmentally regulated genes undergoing transcription induction. Strikingly, RNAi-mediated knockdown of intranuclear Sec13 and Nup98 specifically inhibits transcription of their target genes and prevents efficient reactivation of transcription after heat shock, suggesting an essential role of NPC components in regulating complex gene expression programs of multicellular organisms.}, author = {Capelson, Maya and Liang, Yun and Schulte, Roberta and Mair, William and Wagner, Ulrich and HETZER, Martin W}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {3}, pages = {372--383}, publisher = {Elsevier}, title = {{Chromatin-bound nuclear pore components regulate gene expression in higher eukaryotes}}, doi = {10.1016/j.cell.2009.12.054}, volume = {140}, year = {2010}, } @inproceedings{11797, abstract = {Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1−1𝑒 for online ad allocation, and log(m) for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.}, author = {Feldman, Jon and Henzinger, Monika H and Korula, Nitish and Mirrokni, Vahab S. and Stein, Cliff}, booktitle = {18th Annual European Symposium on Algorithms}, isbn = {3642157742}, issn = {1611-3349}, location = {Liverpool, United Kingdom}, pages = {182–194}, publisher = {Springer Nature}, title = {{Online stochastic packing applied to display ad allocation}}, doi = {10.1007/978-3-642-15775-2_16}, volume = {6346}, year = {2010}, } @inproceedings{11838, abstract = {Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where $n$ advertisers compete for the assignment of one of $k$ sponsored search results, also known as ``slots'', for certain keywords they are interested in. Here, as in other markets of that kind, market equilibria correspond to stable matchings. In this paper, we show how to modify Kuhn's Hungarian Method (Kuhn, 1955) so that it finds an optimal stable matching between advertisers and advertising slots in settings with generalized linear utilities, per-bidder-item reserve prices, and per-bidder-item maximum prices. The only algorithm for this problem presented so far (Aggarwal et al., 2009) requires the market to be in ''general position''. We do not make this assumption.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, isbn = {978-3-939897-16-3}, issn = {1868-8969}, location = {Nancy, France}, pages = {287--298}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Sponsored search, market equilibria, and the Hungarian Method}}, doi = {10.4230/LIPICS.STACS.2010.2463}, volume = {5}, year = {2010}, } @article{12654, abstract = {We investigate the transferability of an enhanced temperature-index melt model that was developed and tested on Haut Glacier d’Arolla, Switzerland, in the 2001 season. The model’s empirical parameters (temperature factor, TF, and shortwave radiation factor, SRF) are recalibrated for: (1) other locations on Haut Glacier d’Arolla; (2) subperiods of distinct meteorological conditions; (3) different years on Haut Glacier d’Arolla; and (4) other glaciers in different years. The model parameters are optimized against simulations of an energy-balance model validated against ablation observations. Results are compared with those obtained with the original parameters. The model works very well when applied to other sites, seasons and glaciers, with the exception of overcast conditions. Differences are due to underestimation of high melt rates. The parameter values are associated with the prevailing energy-balance conditions, showing that high SRF are obtained on clear-sky days, whereas higher TF are typical of locations where glacier winds prevail and turbulent fluxes are high. We also provide a range of parameters clearly associated with the site’s location and its meteorological characteristics that could help to assign parameter values to sites where few data are available.}, author = {Carenzo, Marco and Pellicciotti, Francesca and Rimkus, Stefan and Burlando, Paolo}, issn = {1727-5652}, journal = {Journal of Glaciology}, number = {190}, pages = {258--274}, publisher = {Cambridge University Press}, title = {{Assessing the transferability and robustness of an enhanced temperature-index glacier-melt model}}, doi = {10.3189/002214309788608804}, volume = {55}, year = {2009}, } @article{12655, abstract = {We discuss the inclusion of the subsurface heat-conduction flux into the calculation of the energy balance and ablation at the glacier–atmosphere interface. Data from automatic weather stations are used to force an energy-balance model at several locations on alpine glaciers and at one site in the dry Andes of central Chile. The heat-conduction flux is computed using a two-layer scheme, assuming that 36% of the net shortwave radiation is absorbed by the surface layer and that the rest penetrates into the snowpack. We compare simulations conducted with and without subsurface heat flux. Results show that assuming a surface temperature of zero degrees leads to a larger overestimation of melt at the sites in the accumulation area (10.4–13.3%) than in the ablation area (0.5–2.8%), due to lower air temperatures and the presence of snow. The difference between simulations with and without heat conduction is also high at the beginning and end of the ablation season (up to 29% for the first 15 days of the season), when air temperatures are lower and snow covers the glacier surface, while they are of little importance during periods of sustained melt at all the locations investigated.}, author = {Pellicciotti, Francesca and Carenzo, Marco and Helbing, Jakob and Rimkus, Stefan and Burlando, Paolo}, issn = {1727-5644}, journal = {Annals of Glaciology}, number = {50}, pages = {16--24}, publisher = {International Glaciological Society}, title = {{On the role of subsurface heat conduction in glacier energy-balance modelling}}, doi = {10.3189/172756409787769555}, volume = {50}, year = {2009}, } @article{88, abstract = {We have developed a tunable source of Mie scale microdroplet aerosols that can be used for the generation of energetic ions. To demonstrate this potential, a terawatt Ti: Al2 O3 laser focused to 2×10 19 W/cm2 was used to irradiate heavy water (D2 O) aerosols composed of micron-scale droplets. Energetic deuterium ions, which were generated in the laser-droplet interaction, produced deuterium-deuterium fusion with approximately 2×10^3 fusion neutrons measured per joule of incident laser energy. }, author = {Higginbotham, Andrew P and Semonin, Octavi and Bruce, S and Chan, C and Maindi, M and Donnelly, Tom and Maurer, M and Bang, Woosuk and Churina, I.V and Osterholz, Jens and Kim, I and Bernstein, Aaron and Ditmire, Todd}, journal = {Review of Scientific Instruments}, number = {6}, publisher = {American Institute of Physics}, title = {{Generation of Mie size microdroplet aerosols with applications in laser-driven fusion experiments}}, doi = {10.1063/1.3155302}, volume = {80}, year = {2009}, } @article{9147, abstract = {As part of an ongoing effort to develop a parameterization of wave-induced abyssal mixing, the authors derive an heuristic model for nonlinear wave breaking and energy dissipation associated with internal tides. Then the saturation and dissipation of internal tides for idealized and observed topography samples are investigated. One of the main results is that the wave-induced mixing could be more intense and more confined to the bottom than previously assumed in numerical models. Furthermore, in this model wave breaking and mixing clearly depend on the small scales of the topography below 10 km or so, which is below the current resolution of global bathymetry. This motivates the use of a statistical approach to represent the unresolved topography when addressing the role of internal tides in mixing the deep ocean.}, author = {Muller, Caroline J and Bühler, Oliver}, issn = {1520-0485}, journal = {Journal of Physical Oceanography}, keywords = {Oceanography}, number = {9}, pages = {2077--2096}, publisher = {American Meteorological Society}, title = {{Saturation of the internal tides and induced mixing in the abyssal ocean}}, doi = {10.1175/2009jpo4141.1}, volume = {39}, year = {2009}, } @article{9148, abstract = {Several observational studies have shown a tight relationship between tropical precipitation and column‐integrated water vapor. We show that the observed relationship in the tropics between column‐integrated water vapor, precipitation, and its variance can be qualitatively reproduced by a simple and physically motivated two‐layer model. It has previously been argued that features of this relationship could be explained by analogy with the theory of continuous phase transitions. Instead, our model explicitly assumes that the onset of precipitation is governed by a stability threshold involving boundary‐layer water vapor. This allows us to explain the precipitation‐humidity relationship over a broader range of water vapor values, and may explain the observed temperature dependence of the relationship.}, author = {Muller, Caroline J and Back, Larissa E. and O'Gorman, Paul A. and Emanuel, Kerry A.}, issn = {0094-8276}, journal = {Geophysical Research Letters}, keywords = {General Earth and Planetary Sciences, Geophysics}, number = {16}, publisher = {American Geophysical Union}, title = {{A model for the relationship between tropical precipitation and column water vapor}}, doi = {10.1029/2009gl039667}, volume = {36}, year = {2009}, } @article{8026, abstract = {Recent theoretical work has provided a basic understanding of signal propagation in networks of spiking neurons, but mechanisms for gating and controlling these signals have not been investigated previously. Here we introduce an idea for the gating of multiple signals in cortical networks that combines principles of signal propagation with aspects of balanced networks. Specifically, we studied networks in which incoming excitatory signals are normally cancelled by locally evoked inhibition, leaving the targeted layer unresponsive. Transmission can be gated 'on' by modulating excitatory and inhibitory gains to upset this detailed balance. We illustrate gating through detailed balance in large networks of integrate-and-fire neurons. We show successful gating of multiple signals and study failure modes that produce effects reminiscent of clinically observed pathologies. Provided that the individual signals are detectable, detailed balance has a large capacity for gating multiple signals.}, author = {Vogels, Tim P and Abbott, L F}, issn = {1097-6256}, journal = {Nature Neuroscience}, number = {4}, pages = {483--491}, publisher = {Springer Nature}, title = {{Gating multiple signals through detailed balance of excitation and inhibition in spiking networks}}, doi = {10.1038/nn.2276}, volume = {12}, year = {2009}, }