@inproceedings{3175, abstract = {This paper addresses the novel problem of automatically synthesizing an output image from a large collection of different input images. The synthesized image, called a digital tapestry, can be viewed as a visual summary or a virtual 'thumbnail' of all the images in the input collection. The problem of creating the tapestry is cast as a multi-class labeling problem such that each region in the tapestry is constructed from input image blocks that are salient and such that neighboring blocks satisfy spatial compatibility. This is formulated using a Markov Random Field and optimized via the graph cut based expansion move algorithm. The standard expansion move algorithm can only handle energies with metric terms, while our energy contains non-metric (soft and hard) constraints. Therefore we propose two novel contributions. First, we extend the expansion move algorithm for energy functions with non-metric hard constraints. Secondly, we modify it for functions with "almost" metric soft terms, and show that it gives good results in practice. The proposed framework was tested on several consumer photograph collections, and the results are presented.}, author = {Rother, Carsten and Kumar, Sanjiv and Vladimir Kolmogorov and Blake, Andrew}, pages = {589 -- 596}, publisher = {IEEE}, title = {{Digital tapestry}}, doi = {10.1109/CVPR.2005.130}, volume = {1}, year = {2005}, } @inproceedings{3176, abstract = {This paper demonstrates the high quality, real-time segmentation techniques. We achieve real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, layered dynamic programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, layered graph cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output. }, author = {Vladimir Kolmogorov and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Rother, Carsten}, pages = {1186 -- 1186}, publisher = {IEEE}, title = {{Bi-layer segmentation of binocular stereo video}}, doi = {10.1109/CVPR.2005.90}, year = {2005}, } @inproceedings{3181, abstract = {Tree-reweighted max-product (TRW) message passing [9] is a modified form of the ordinary max-product algorithm for attempting to find minimal energy configurations in Markov random field with cycles. For a TRW fixed point satisfying the strong tree agreement condition, the algorithm outputs a configuration that is provably optimal. In this paper, we focus on the case of binary variables with pairwise couplings, and establish stronger properties of TRW fixed points that satisfy only the milder condition of weak tree agreement (WTA). First, we demonstrate how it is possible to identify part of the optimal solution - i.e., a provably optimal solution for a subset of nodes - without knowing a complete solution. Second, we show that for submodular functions, a WTA fixed point always yields a globally optimal solution. We establish that for binary variables, any WTA fixed point always achieves the global maximum of the linear programming relaxation underlying the TRW method.}, author = {Vladimir Kolmogorov and Wainwright, Martin J}, pages = {316 -- 323}, publisher = {AUAI Press}, title = {{On the optimality of tree reweighted max product message passing}}, year = {2005}, } @inproceedings{3182, abstract = {In the work of the authors (2003), we showed that graph cuts can find hypersurfaces of globally minimal length (or area) under any Riemannian metric. Here we show that graph cuts on directed regular grids can approximate a significantly more general class of continuous non-symmetric metrics. Using submodularity condition (Boros and Hammer, 2002 and Kolmogorov and Zabih, 2004), we obtain a tight characterization of graph-representable metrics. Such "submodular" metrics have an elegant geometric interpretation via hypersurface functionals combining length/area and flux. Practically speaking, we attend 'geo-cuts' algorithm to a wider class of geometrically motivated hypersurface functionals and show how to globally optimize any combination of length/area and flux of a given vector field. The concept of flux was recently introduced into computer vision by Vasilevskiy and Siddiqi (2002) but it was mainly studied within variational framework so far. We are first to show that flux can be integrated into graph cuts as well. Combining geometric concepts of flux and length/area within the global optimization framework of graph cuts allows principled discrete segmentation models and advances the slate of the art for the graph cuts methods in vision. In particular we address the "shrinking" problem of graph cuts, improve segmentation of long thin objects, and introduce useful shape constraints.}, author = {Vladimir Kolmogorov and Boykov, Yuri}, pages = {564 -- 571}, publisher = {IEEE}, title = {{What metrics can be approximated by geo cuts or global optimization of length area and flux}}, doi = {10.1109/ICCV.2005.252}, volume = {1}, year = {2005}, } @inproceedings{3183, abstract = {This paper describes two algorithms capable of real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar perfomance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.}, author = {Vladimir Kolmogorov and Criminisi, Antonio and Blake, Andrew and Cross, Geoffrey and Rother, Carsten}, pages = {407 -- 414}, publisher = {IEEE}, title = {{Bi-layer segmentation of binocular stereo video}}, doi = {10.1109/CVPR.2005.91}, volume = {2}, year = {2005}, } @inproceedings{3211, abstract = {We present an improved bound on the advantage of any q-query adversary at distinguishing between the CBC MAC over a random n-bit permutation and a random function outputting n bits. The result assumes that no message queried is a prefix of any other, as is the case when all messages to be MACed have the same length. We go on to give an improved analysis of the encrypted CBC MAC, where there is no restriction on queried messages. Letting m be the block length of the longest query, our bounds are about mq2/2n for the basic CBC MAC and mo(1)q2/2n for the encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate into improved guarantees on the probability of forging these MACs.}, author = {Bellare, Mihir and Krzysztof Pietrzak and Rogaway, Phillip}, pages = {527 -- 545}, publisher = {Springer}, title = {{Improved security analyses for CBC MACs}}, doi = {10.1007/11535218_32}, volume = {3621}, year = {2005}, } @inproceedings{3212, abstract = {The Full-Domain Hash (FDH) signature scheme [3] forms one the most basic usages of random oracles. It works with a family F of trapdoor permutations (TDP), where the signature of m is computed as f−1(h(m)) (here f ∈R F and h is modelled as a random oracle). It is known to be existentially unforgeable for any TDP family F [3], although a much tighter security reduction is known for a restrictive class of TDP’s [10,14] — namely, those induced by a family of claw-free permutations (CFP) pairs. The latter result was shown [11] to match the best possible “black-box” security reduction in the random oracle model, irrespective of the TDP family F (e.g., RSA) one might use. In this work we investigate the question if it is possible to instantiate the random oracle h with a “real” family of hash functions H such that the corresponding schemes can be proven secure in the standard model, under some natural assumption on the family F. Our main result rules out the existence of such instantiations for any assumption on F which (1) is satisfied by a family of random permutations; and (2) does not allow the attacker to invert f ∈R F on an a-priori unbounded number of points. Moreover, this holds even if the choice of H can arbitrarily depend on f. As an immediate corollary, we rule out instantiating FDH based on general claw-free permutations, which shows that in order to prove the security of FDH in the standard model one must utilize significantly more structure on F than what is sufficient for the best proof of security in the random oracle model.}, author = {Dodis, Yevgeniy and Oliveira, Roberto and Krzysztof Pietrzak}, pages = {449 -- 466}, publisher = {Springer}, title = {{On the generic insecurity of the full domain hash}}, doi = {10.1007/11535218_27}, volume = {3621}, year = {2005}, } @inproceedings{3213, abstract = {We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F and G is the function G(F()), the parallel composition is F G where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case. In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.}, author = {Krzysztof Pietrzak}, pages = {55 -- 65}, publisher = {Springer}, title = {{Composition does not imply adaptive security}}, doi = {10.1007/11535218_4}, volume = {3621}, year = {2005}, } @article{11120, abstract = {The nuclear envelope (NE) is a highly specialized membrane that delineates the eukaryotic cell nucleus. It is composed of the inner and outer nuclear membranes, nuclear pore complexes (NPCs) and, in metazoa, the lamina. The NE not only regulates the trafficking of macromolecules between nucleoplasm and cytosol but also provides anchoring sites for chromatin and the cytoskeleton. Through these interactions, the NE helps position the nucleus within the cell and chromosomes within the nucleus, thereby regulating the expression of certain genes. The NE is not static, rather it is continuously remodeled during cell division. The most dramatic example of NE reorganization occurs during mitosis in metazoa when the NE undergoes a complete cycle of disassembly and reformation. Despite the importance of the NE for eukaryotic cell life, relatively little is known about its biogenesis or many of its functions. We thus are far from understanding the molecular etiology of a diverse group of NE-associated diseases.}, author = {HETZER, Martin W and Walther, Tobias C. and Mattaj, Iain W.}, issn = {1530-8995}, journal = {Annual Review of Cell and Developmental Biology}, keywords = {Cell Biology, Developmental Biology}, pages = {347--380}, publisher = {Annual Reviews}, title = {{Pushing the envelope: Structure, function, and dynamics of the nuclear periphery}}, doi = {10.1146/annurev.cellbio.21.090704.151152}, volume = {21}, year = {2005}, } @inproceedings{11698, abstract = {We give a short survey of the use of hyperlink analysis in web search engine ranking and sketch other applications of hyperlink analysis in the web space.}, author = {Henzinger, Monika H}, booktitle = {Proceedings of the 16th ACM conference on Hypertext and hypermedia}, isbn = {9781595931689}, keywords = {Hyperlink Analysis, World Wide Web}, location = {Salzburg, Austria}, pages = {1--3}, publisher = {Association for Computing Machinery}, title = {{Hyperlink analysis on the world wide web}}, doi = {10.1145/1083356.1083357}, year = {2005}, } @article{11763, abstract = {We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is O((log n + log log M)(log n + log M) log n), where M is the number of multicast groups and n is the number of nodes in the graph. We show that this is close to optimum by presenting an Ω(log n log M) lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when M is much larger than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary. As in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.}, author = {Goel, Ashish and Henzinger, Monika H and Plotkin, Serge}, issn = {0196-6774}, journal = {Journal of Algorithms}, number = {1}, pages = {1--20}, publisher = {Elsevier}, title = {{An online throughput-competitive algorithm for multicast routing and admission control}}, doi = {10.1016/j.jalgor.2004.11.001}, volume = {55}, year = {2005}, } @article{8028, abstract = {Transmission of signals within the brain is essential for cognitive function, but it is not clear how neural circuits support reliable and accurate signal propagation over a sufficiently large dynamic range. Two modes of propagation have been studied: synfire chains, in which synchronous activity travels through feedforward layers of a neuronal network, and the propagation of fluctuations in firing rate across these layers. In both cases, a sufficient amount of noise, which was added to previous models from an external source, had to be included to support stable propagation. Sparse, randomly connected networks of spiking model neurons can generate chaotic patterns of activity. We investigate whether this activity, which is a more realistic noise source, is sufficient to allow for signal transmission. We find that, for rate-coded signals but not for synfire chains, such networks support robust and accurate signal reproduction through up to six layers if appropriate adjustments are made in synaptic strengths. We investigate the factors affecting transmission and show that multiple signals can propagate simultaneously along different pathways. Using this feature, we show how different types of logic gates can arise within the architecture of the random network through the strengthening of specific synapses.}, author = {Vogels, Tim P and Abbott, L. F.}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {46}, pages = {10786--10795}, publisher = {Society for Neuroscience}, title = {{Signal propagation and logic gating in networks of integrate-and-fire neurons}}, doi = {10.1523/jneurosci.3508-05.2005}, volume = {25}, year = {2005}, } @article{8029, abstract = {Neural network modeling is often concerned with stimulus-driven responses, but most of the activity in the brain is internally generated. Here, we review network models of internally generated activity, focusing on three types of network dynamics: (a) sustained responses to transient stimuli, which provide a model of working memory; (b) oscillatory network activity; and (c) chaotic activity, which models complex patterns of background spiking in cortical and other circuits. We also review propagation of stimulus-driven activity through spontaneously active networks. Exploring these aspects of neural network dynamics is critical for understanding how neural circuits produce cognitive function.}, author = {Vogels, Tim P and Rajan, Kanaka and Abbott, L.F.}, issn = {0147-006X}, journal = {Annual Review of Neuroscience}, number = {1}, pages = {357--376}, publisher = {Annual Reviews}, title = {{Neural network dynamics}}, doi = {10.1146/annurev.neuro.28.061604.135637}, volume = {28}, year = {2005}, } @article{843, abstract = {The impact of an amino acid replacement on the organism's fitness can vary from lethal to selectively neutral and even, in rare cases, beneficial. Substantial data are available on either pathogenic or acceptable replacements. However, the whole distribution of coefficients of selection against individual replacements is not known for any organism. To ascertain this distribution for human proteins, we combined data on pathogenic missense mutations, on human non-synonymous SNPs and on human-chimpanzee divergence of orthologous proteins. Fractions of amino acid replacements which reduce fitness by >10-2, 10-2-10-4, 10-4-10-5 and <10-5 are 25, 49, 14 and 12%, respectively. On average, the strength of selection against a replacement is substantially higher when chemically dissimilar amino acids are involved, and the Grantham's index of a replacement explains 35% of variance in the average logarithm of selection coefficients associated with different replacements. Still, the impact of a replacement depends on its context within the protein more than on its own nature. Reciprocal replacements are often associated with rather different selection coefficients, in particular, replacements of non-polar amino acids with polar ones are typically much more deleterious than replacements in the opposite direction. However, differences between evolutionary fluxes of reciprocal replacements are only weakly correlated with the differences between the corresponding selection coefficients.}, author = {Yampolsky, Lev Y and Fyodor Kondrashov and Kondrashov, Alexey S}, journal = {Human Molecular Genetics}, number = {21}, pages = {3191 -- 3201}, publisher = {Oxford University Press}, title = {{Distribution of the strength of selection against amino acid replacements in human proteins}}, doi = {10.1093/hmg/ddi350}, volume = {14}, year = {2005}, } @article{8491, abstract = {Fast multidimensional NMR with a time resolution of a few seconds provides a new tool for high throughput screening and site-resolved real-time studies of kinetic molecular processes by NMR. Recently we have demonstrated the feasibility to record protein 1H–15N correlation spectra in a few seconds of acquisition time using a new SOFAST-HMQC experiment (Schanda and Brutscher (2005) J. Am. Chem. Soc. 127, 8014). Here, we investigate in detail the performance of SOFAST-HMQC to record 1H–15N and 1H−13C correlation spectra of proteins of different size and at different magnetic field strengths. Compared to standard 1H–15N correlation experiments SOFAST-HMQC provides a significant gain in sensitivity, especially for fast repetition rates. Guidelines are provided on how to set up SOFAST-HMQC experiments for a given protein sample. In addition, an alternative pulse scheme, IPAP-SOFAST-HMQC is presented that allows application on NMR spectrometers equipped with cryogenic probes, and fast measurement of one-bond 1H–13C and 1H–15N scalar and residual dipolar coupling constants.}, author = {Schanda, Paul and Kupče, Ēriks and Brutscher, Bernhard}, issn = {0925-2738}, journal = {Journal of Biomolecular NMR}, keywords = {Spectroscopy, Biochemistry}, number = {4}, pages = {199--211}, publisher = {Springer Nature}, title = {{SOFAST-HMQC experiments for recording two-dimensional deteronuclear correlation spectra of proteins within a few seconds}}, doi = {10.1007/s10858-005-4425-x}, volume = {33}, year = {2005}, } @article{8492, abstract = {We demonstrate for different protein samples that 2D 1H−15N correlation NMR spectra can be recorded in a few seconds of acquisition time using a new band-selective optimized flip-angle short-transient heteronuclear multiple quantum coherence experiment. This has enabled us to measure fast hydrogen−deuterium exchange rate constants along the backbone of a small globular protein fragment by real-time 2D NMR.}, author = {Schanda, Paul and Brutscher, Bernhard}, issn = {0002-7863}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {22}, pages = {8014--8015}, publisher = {American Chemical Society}, title = {{Very fast two-dimensional NMR spectroscopy for real-time investigation of dynamic events in proteins on the time scale of seconds}}, doi = {10.1021/ja051306e}, volume = {127}, year = {2005}, } @article{8516, abstract = {The purpose of this paper is to construct examples of diffusion for E-Hamiltonian perturbations of completely integrable Hamiltonian systems in 2d-dimensional phase space, with d large. In the first part of the paper, simple and explicit examples are constructed illustrating absence of ‘long-time’ stability for size E Hamiltonian perturbations of quasi-convex integrable systems already when the dimension 2d of phase space becomes as large as log 1/E . We first produce the example in Gevrey class and then a real analytic one, with some additional work. In the second part, we consider again E-Hamiltonian perturbations of completely integrable Hamiltonian system in 2d-dimensional space with E-small but not too small, |E| > exp(−d), with d the number of degrees of freedom assumed large. It is shown that for a class of analytic time-periodic perturbations, there exist linearly diffusing trajectories. The underlying idea for both examples is similar and consists in coupling a fixed degree of freedom with a large number of them. The procedure and analytical details are however significantly different. As mentioned, the construction in Part I is totally elementary while Part II is more involved, relying in particular on the theory of normally hyperbolic invariant manifolds, methods of generating functions, Aubry–Mather theory, and Mather’s variational methods.}, author = {Bourgain, Jean and Kaloshin, Vadim}, issn = {0022-1236}, journal = {Journal of Functional Analysis}, keywords = {Analysis}, number = {1}, pages = {1--61}, publisher = {Elsevier}, title = {{On diffusion in high-dimensional Hamiltonian systems}}, doi = {10.1016/j.jfa.2004.09.006}, volume = {229}, year = {2005}, } @article{877, abstract = {Sequence analysis of protein and mitochondrially encoded tRNA genes shows that substitutions producing pathogenic effects in humans are often found in normal, healthy individuals from other species. Analysis of stability of protein and tRNA structures shows that the disease-causing effects of pathogenic mutations can be neutralized by other, compensatory substitutions that restore the structural stability of the molecule. Further study of such substitutions will, hopefully, lead to new methods for curing genetic dis- eases that may be based on the correction of molecule stability as a whole instead of reversing an individual pathogenic mutation.}, author = {Kondrashov, Fyodor}, journal = {Biofizika}, number = {3}, pages = {389 -- 395}, publisher = {Pleiades Publishing}, title = {{The analysis of monomer sequences in protein and tRNA and the manifestation of the compensation of pathogenic deviations in their evolution}}, volume = {50}, year = {2005}, } @article{878, abstract = {Negative trade-offs are thought to be a pervasive phenomenon and to inhibit evolution at all levels. New evidence shows that at the molecular level, there may be no trade-offs preventing the emergence of an enzyme with multiple functions. }, author = {Fyodor Kondrashov}, journal = {Nature Genetics}, number = {1}, pages = {9 -- 10}, publisher = {Nature Publishing Group}, title = {{In search of the limits of evolution}}, doi = {10.1038/ng0105-9}, volume = {37}, year = {2005}, } @article{880, abstract = {Here, I describe a case of loss of the D-arm by mitochondrial cysteine tRNA in the nine-banded armadillo (Dasypus novemcinctus) convergent with mt tRNASer(AGY). Such evolution sheds light on the relationship between structure and function of tRNA molecules and its impact on the patterns of molecular evolution.}, author = {Kondrashov, Fyodor}, journal = {Biofizika}, number = {3}, pages = {396 -- 403}, publisher = {Pleiades Publishing}, title = {{The convergent evolution of the secondary structure of mitochondrial cysteine tRNA in the nine-banded armadillo Dasypus novemcinctus}}, volume = {50}, year = {2005}, }