@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{11115, abstract = {The formation of the nuclear envelope (NE) around chromatin is a major membrane-remodelling event that occurs during cell division of metazoa. It is unclear whether the nuclear membrane reforms by the fusion of NE fragments or if it re-emerges from an intact tubular network of the endoplasmic reticulum (ER). Here, we show that NE formation and expansion requires a tubular ER network and occurs efficiently in the presence of the membrane fusion inhibitor GTPγS. Chromatin recruitment of membranes, which is initiated by tubule-end binding, followed by the formation, expansion and sealing of flat membrane sheets, is mediated by DNA-binding proteins residing in the ER. Thus, chromatin plays an active role in reshaping of the ER during NE formation.}, author = {Anderson, Daniel J. and HETZER, Martin W}, issn = {1476-4679}, journal = {Nature Cell Biology}, keywords = {Cell Biology}, number = {10}, pages = {1160--1166}, publisher = {Springer Nature}, title = {{Nuclear envelope formation by chromatin-mediated reorganization of the endoplasmic reticulum}}, doi = {10.1038/ncb1636}, volume = {9}, year = {2007}, } @article{11116, abstract = {The metazoan nuclear envelope (NE) breaks down and re-forms during each cell cycle. Nuclear pore complexes (NPCs), which allow nucleocytoplasmic transport during interphase, assemble into the re-forming NE at the end of mitosis. Using in vitro NE assembly, we show that the vertebrate homologue of MEL-28 (maternal effect lethal), a recently discovered NE component in Caenorhabditis elegans, functions in postmitotic NPC assembly. MEL-28 interacts with the Nup107–160 complex (Nup for nucleoporin), an important building block of the NPC, and is essential for the recruitment of the Nup107–160 complex to chromatin. We suggest that MEL-28 acts as a seeding point for NPC assembly.}, author = {Franz, Cerstin and Walczak, Rudolf and Yavuz, Sevil and Santarella, Rachel and Gentzel, Marc and Askjaer, Peter and Galy, Vincent and HETZER, Martin W and Mattaj, Iain W and Antonin, Wolfram}, issn = {1469-3178}, journal = {EMBO reports}, keywords = {Genetics, Molecular Biology, Biochemistry}, number = {2}, pages = {165--172}, publisher = {EMBO}, title = {{MEL‐28/ELYS is required for the recruitment of nucleoporins to chromatin and postmitotic nuclear pore complex assembly}}, doi = {10.1038/sj.embor.7400889}, volume = {8}, year = {2007}, } @article{7780, abstract = {We used single-channel electrical recordings and Langevin molecular dynamics simulations to explore the electrophoretic translocation of various β-hairpin peptides across the staphylococcal α-hemolysin (αHL) protein pore at single-molecule resolution. The β-hairpin peptides, which varied in their folding properties, corresponded to the C terminal residues of the B1 domain of protein G. The translocation time was strongly dependent on the electric force and was correlated with the folding features of the β-hairpin peptides. Highly unfolded peptides entered the pore in an extended conformation, resulting in fast single-file translocation events. In contrast, the translocation of the folded β-hairpin peptides occurred more slowly. In this case, the β-hairpin peptides traversed the αHL pore in a misfolded or fully folded conformation. This study demonstrates that the interaction between a polypeptide and a β-barrel protein pore is dependent on the folding features of the polypeptide. }, author = {Goodrich, Carl Peter and Kirmizialtin, Serdal and Huyghues-Despointes, Beatrice M. and Zhu, Aiping and Scholtz, J. Martin and Makarov, Dmitrii E. and Movileanu, Liviu}, issn = {1520-6106}, journal = {The Journal of Physical Chemistry B}, number = {13}, pages = {3332--3335}, publisher = {American Chemical Society}, title = {{Single-molecule electrophoresis of β-hairpin peptides by electrical recordings and Langevin dynamics simulations}}, doi = {10.1021/jp071364h}, volume = {111}, year = {2007}, } @article{7781, abstract = {Males are predicted to compete for reproductive opportunities, with sexual selection driving the evolution of large body size and weaponry through the advantage they confer for access to females. Few studies have explored potential trade‐offs of investment in secondary sexual traits between different components of fitness or tested for sexually antagonistic selection pressures. These factors may provide explanations for observed polymorphisms in both form and quality of secondary sexual traits. We report here an analysis of selection on horn phenotype in a feral population of Soay sheep (Ovis aries) on the island of Hirta, St. Kilda, Scotland. Soay sheep display a phenotypic polymorphism for horn type with males growing either normal or reduced (scurred) horns, and females growing either normal, scurred, or no (polled) horns; further variation in size exists within horn morphs. We show that horn phenotype and the size of the trait displayed is subject to different selection pressures in males and females, generating sexually antagonistic selection. Furthermore, there was evidence of a trade‐off between breeding success and longevity in normal‐horned males, with both the normal horn type and larger horn size being associated with greater annual breeding success but reduced longevity. Therefore, selection through lifetime breeding success was not found to act upon horn phenotype in males. In females, a negative association of annual breeding success within the normal‐horned phenotype did not result in a significant difference in lifetime fitness when compared to scurred individuals, as no significant difference in longevity was found. However, increased horn size within this group was negatively associated with breeding success and longevity. Females without horns (polled) suffered reduced longevity and thus reduced lifetime breeding success relative the other horn morphs. Our results therefore suggest that trade‐offs between different components of fitness and antagonistic selection between the sexes may maintain genetic variation for secondary sexual traits within a population.}, author = {Robinson, Matthew Richard and Pilkington, Jill G. and Clutton-Brock, Tim H. and Pemberton, Josephine M. and Kruuk, Loeske E.B.}, issn = {0014-3820}, journal = {Evolution}, number = {10}, pages = {2168--2181}, publisher = {Wiley}, title = {{Live fast, die young: Trade-offs between fitness components and sexually antagonistic selection on weaponry in soay sheep}}, doi = {10.1111/j.0014-3820.2006.tb01854.x}, volume = {60}, year = {2007}, } @article{8027, abstract = {Gating deficits and hallucinatory sensations are prominent symptoms of schizophrenia. Comparing these abnormalities with the failure modes of network models is an interesting way to explore how they arise. We present a network model that can both propagate and gate signals. The model exhibits effects reminiscent of clinically observed pathologies when the balance between excitation and inhibition that it requires is not properly maintained.}, author = {Vogels, Tim P and Abbott, L.}, issn = {0176-3679}, journal = {Pharmacopsychiatry}, number = {S 1}, pages = {S73--S77}, publisher = {Thieme}, title = {{Gating deficits in model networks: A path to schizophrenia?}}, doi = {10.1055/s-2007-992130}, volume = {40}, year = {2007}, } @article{8483, abstract = {Atom-resolved real-time studies of kinetic processes in proteins have been hampered in the past by the lack of experimental techniques that yield sufficient temporal and atomic resolution. Here we present band-selective optimized flip-angle short transient (SOFAST) real-time 2D NMR spectroscopy, a method that allows simultaneous observation of reaction kinetics for a large number of nuclear sites along the polypeptide chain of a protein with an unprecedented time resolution of a few seconds. SOFAST real-time 2D NMR spectroscopy combines fast NMR data acquisition techniques with rapid sample mixing inside the NMR magnet to initiate the kinetic event. We demonstrate the use of SOFAST real-time 2D NMR to monitor the conformational transition of α-lactalbumin from a molten globular to the native state for a large number of amide sites along the polypeptide chain. The kinetic behavior observed for the disappearance of the molten globule and the appearance of the native state is monoexponential and uniform along the polypeptide chain. This observation confirms previous findings that a single transition state ensemble controls folding of α-lactalbumin from the molten globule to the native state. In a second application, the spontaneous unfolding of native ubiquitin under nondenaturing conditions is characterized by amide hydrogen exchange rate constants measured at high pH by using SOFAST real-time 2D NMR. Our data reveal that ubiquitin unfolds in a gradual manner with distinct unfolding regimes.}, author = {Schanda, Paul and Forge, V. and Brutscher, B.}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {Multidisciplinary}, number = {27}, pages = {11257--11262}, publisher = {National Academy of Sciences}, title = {{Protein folding and unfolding studied at atomic resolution by fast two-dimensional NMR spectroscopy}}, doi = {10.1073/pnas.0702069104}, volume = {104}, year = {2007}, } @article{8484, abstract = {A series of sequential, intra-residue, and bi-directional BEST H–N–CA, H–N–CO, and H–N–CB pulse sequences is presented that extends the BEST concept introduced recently for fast multidimensional protein NMR [Schanda et al., J. Am. Chem. Soc. 128 (2006) 9042] to the complete set of experiments required for sequential resonance assignment. We demonstrate for the protein ubiquitin that 3D BEST H–N–C correlation spectra can be recorded on a 600 MHz NMR spectrometer equipped with a cryogenic probe in only a few minutes of acquisition time with sufficient sensitivity to detect all expected cross peaks.}, author = {Lescop, Ewen and Schanda, Paul and Brutscher, Bernhard}, issn = {1090-7807}, journal = {Journal of Magnetic Resonance}, number = {1}, pages = {163--169}, publisher = {Elsevier}, title = {{A set of BEST triple-resonance experiments for time-optimized protein resonance assignment}}, doi = {10.1016/j.jmr.2007.04.002}, volume = {187}, year = {2007}, } @article{8485, abstract = {High signal to noise is a necessity for the quantification of NMR spectral parameters to be translated into accurate and precise restraints on protein structure and dynamics. An important source of long-range structural information is obtained from 1H–1H residual dipolar couplings (RDCs) measured for weakly aligned molecules. For sensitivity reasons, such measurements are generally performed on highly deuterated protein samples. Here we show that high sensitivity is also obtained for protonated protein samples if the pulse schemes are optimized in terms of longitudinal relaxation efficiency and J-mismatch compensated coherence transfer. The new sensitivity-optimized quantitative J-correlation experiment yields important signal gains reaching factors of 1.5 to 8 for individual correlation peaks when compared to previously proposed pulse schemes.}, author = {Schanda, Paul and Lescop, Ewen and Falge, Mirjam and Sounier, Rémy and Boisbouvier, Jérôme and Brutscher, Bernhard}, issn = {0925-2738}, journal = {Journal of Biomolecular NMR}, keywords = {Spectroscopy, Biochemistry}, pages = {47--55}, publisher = {Springer Nature}, title = {{Sensitivity-optimized experiment for the measurement of residual dipolar couplings between amide protons}}, doi = {10.1007/s10858-006-9138-2}, volume = {38}, year = {2007}, } @article{8486, abstract = {A technique is described that allows reducing acquisition times of multidimensional NMR experiments by extensive spectral folding. The method is simple and has many interesting applications for NMR studies of molecular structure, dynamics, and kinetics.}, author = {Lescop, Ewen and Schanda, Paul and Rasia, Rodolfo and Brutscher, Bernhard}, issn = {0002-7863}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {10}, pages = {2756--2757}, publisher = {American Chemical Society}, title = {{Automated spectral compression for fast multidimensional NMR and increased time resolution in real-time NMR spectroscopy}}, doi = {10.1021/ja068949u}, volume = {129}, year = {2007}, } @article{8487, abstract = {Following unidirectional biophysical events such as the folding of proteins or the equilibration of binding interactions, requires experimental methods that yield information at both atomic-level resolution and at high repetition rates. Toward this end a number of different approaches enabling the rapid acquisition of 2D NMR spectra have been recently introduced, including spatially encoded “ultrafast” 2D NMR spectroscopy and SOFAST HMQC NMR. Whereas the former accelerates acquisitions by reducing the number of scans that are necessary for completing arbitrary 2D NMR experiments, the latter operates by reducing the delay between consecutive scans while preserving sensitivity. Given the complementarities between these two approaches it seems natural to combine them into a single tool, enabling the acquisition of full 2D protein NMR spectra at high repetition rates. We demonstrate here this capability with the introduction of “ultraSOFAST” HMQC NMR, a spatially encoded and relaxation-optimized approach that can provide 2D protein correlation spectra at ∼1 s repetition rates for samples in the ∼2 mM concentration range. The principles, relative advantages, and current limitations of this new approach are discussed, and its application is exemplified with a study of the fast hydrogen−deuterium exchange characterizing amide sites in Ubiquitin.}, author = {Gal, Maayan and Schanda, Paul and Brutscher, Bernhard and Frydman, Lucio}, issn = {0002-7863}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {5}, pages = {1372--1377}, publisher = {American Chemical Society}, title = {{UltraSOFAST HMQC NMR and the repetitive acquisition of 2D protein spectra at Hz rates}}, doi = {10.1021/ja066915g}, volume = {129}, year = {2007}, } @article{8511, abstract = {Here we study an amazing phenomenon discovered by Newhouse [S. Newhouse, Non-density of Axiom A(a) on S2, in: Proc. Sympos. Pure Math., vol. 14, Amer. Math. Soc., 1970, pp. 191–202; S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology 13 (1974) 9–18; S. Newhouse, The abundance of wild hyperbolic sets and nonsmooth stable sets of diffeomorphisms, Publ. Math. Inst. Hautes Études Sci. 50 (1979) 101–151]. It turns out that in the space of Cr smooth diffeomorphisms Diffr(M) of a compact surface M there is an open set U such that a Baire generic diffeomorphism f ∈ U has infinitely many coexisting sinks. In this paper we make a step towards understanding “how often does a surface diffeomorphism have infinitely many sinks.” Our main result roughly says that with probability one for any positive D a surface diffeomorphism has only finitely many localized sinks either of cyclicity bounded by D or those whose period is relatively large compared to its cyclicity. It verifies a particular case of Palis’ Conjecture saying that even though diffeomorphisms with infinitely many coexisting sinks are Baire generic, they have probability zero. One of the key points of the proof is an application of Newton Interpolation Polynomials to study the dynamics initiated in [V. Kaloshin, B. Hunt, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms I, Ann. of Math., in press, 92 pp.; V. Kaloshin, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms II, preprint, 85 pp.].}, author = {Gorodetski, A. and Kaloshin, Vadim}, issn = {0001-8708}, journal = {Advances in Mathematics}, keywords = {General Mathematics}, number = {2}, pages = {710--797}, publisher = {Elsevier}, title = {{How often surface diffeomorphisms have infinitely many sinks and hyperbolicity of periodic points near a homoclinic tangency}}, doi = {10.1016/j.aim.2006.03.012}, volume = {208}, year = {2007}, }