224 research outputs found
Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication
No full textWe show that a broad class of (+, diamond) vector products (for binary integer functions diamond) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Our results imply equivalence (up to poly log n factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. As a consequence, Yuster's (SODA'09) algorithm improves not only Matousek's (IPL'91), but also the results of Indyk, Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09). Furthermore, our reductions apply to the pattern matching setting, showing equivalence (up to poly log n factors) between pattern matching under Hamming Distance, l_{2p+1} Distance, Dominance Product and Threshold Product, with current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and Farach (Ann. Math. Artif. Intell.'91), Atallah and Duket (IPL'11), Clifford, Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05). The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are new.
Additionally, we show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n x (n * d) and (n * d) x n, each with (n * d) non-zero entries. This means that the current upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse matrix multiplication algorithm by Yuster and Zwick (ACM TALG'05) and vice versa
Hamming Distance Completeness
No full textWe show, given a binary integer function diamond that is piecewise polynomial, that (+,diamond) vector products are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include the dominance and l_{2p+1} distances for constant p. Our results imply equivalence (up to polylog factors) between the complexity of computing All Pairs Hamming Distance, All Pairs l_{2p+1} Distance and Dominance Matrix Product, and equivalence between Hamming Distance Pattern Matching, l_{2p+1} Pattern Matching and Less-Than Pattern Matching. The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are likely to be optimal, given lack of progress in improving upper bounds for Hamming distance in the past 30 years. While reductions between selected pairs of products were presented in the past, our work is the first to generalize them to a general class of functions, showing that a wide class of "intermediate" complexity problems are in fact equivalent
rum1:A CDK inhibitor regulating G1 progression in fission yeast
No full textIn all eukaryotes, entry into mitosis from G2 phase is initiated by a complex of the cdc2 kinase and a B-type cyclin. It has now been shown that, in fission yeast, B-type cyclins also activate cdc2 in G1, thus governing cell-cycle commitment, as well as the onset of S phase. In this article, Karim Labib and Sergio Moreno review the evidence that rum1 inhibits the kinase activity of cdc2 associated with B-type cyclins and is an important regulator of G1 progression in fission yeast.</p
Peran KH Abdul Karim Ali dalam dakwah dan pendidikan Islam di Kampung Pungangan Rancabango Kab Subang 1950-1993
No full textPeran KH.Abdul Karim Ali Dalam Dakwah Dan Pendidikan Islam Dikampung Pungangan Rancabango Subang 1950-1993. Dakwah merupakan salah satu bagian terpenting untuk menunjang dalam mencapai sukses atau keberhasilan dakwah. Perlu diusahakan usaha-usaha yang tepat dan kongkrit, baik dalam bentuk metode atau alat yang dipakai untuk dakwah.
Dengan menggunakan metode penelitian yaitu Heuristik, kritik, interpretasi, dan histiografi, tulisan ini bertujuan untuk mengetahui bagaimana profil atau sejarah terjadinya perkembangan dakwah dan pendidikan islam di lingkungan Kampung pungangan oleh KH.Abdul Karim Ali kepada masyarakat pada tahun 1950-1993. Pada tahun 1950-1993 telah membawa perubahan besar bagi masyarakat kampung pungangan peranan KH.Abdul karim ali dalam dakwah dan mendidirikan pendidikan dikampung pungangan sebagai basis dakwah islam. Wafatnya KH.Abdul Karim Ali dan putranya KH.Thola’albadar karim sebagai generasi kedua telah menghilangkan pamor itu seakan lenyap dari sejarah dan pengetahuan umum masyarakat setempat. Dengan begitu tulisan ini akan menjadi makalah rujukan bagi mereka yang ingin mengungkap lebih jauh mengenai pengaruh penting Pesantren ALKarimiyah khususnya dan rujukan penting bagi masyarakat pada umumnya
Les sommaires de la revue (1939-1957)
No full textN° 1 - 1939 Sayyid Karim : « Qu’est-ce que l’architecture ? » * Immeuble de Mme Inji Zada : Antoine Selim Nahhas, arch. * Immeuble de la Compagnie des Assurances générales de Trieste : Arnold Zarb, arch. * Villa Husayn bey ’Irfan à Maadi : ’Ali Labib Gabr, arch. * Villa Green : Max Edrei, arch. * Les immeubles Doldertal à Zurich: Roth. Roth. Breuer, arch. * Siège social de Hoffmann - La Roche à Bâle : Otto Salvisberg, arch. Sayyid Karim : « L’éclairage zénithal des salles de lecture des bibli..
Réplication de l’ADN des génomes eucaryotes / DNA replication of eukaryotic genomes
No full textColloque organisé par Marie-Noëlle Prioleau (Institut Jacques Monod, Paris) et Philippe Pasero (IGH-CNRS, Montpellier) du 2 au 7 juillet 2012 Participants Andrés Aguilera, Julian Blow, Karlene Cimprich, Vincenzo Constanzo, John Diffley, Marco Foiani, Susan M. Gasser, David M. Gilbert, Anja Groth, Olivier Hyrien, Dean A. Jackson, Karim Labib, Sarah Lambert, Benoît Le Tallec, Hisao Masukata, Philippe Pasero, Marie-Noëlle Prioleau, Etienne Schwob, Bruce Stillmann -- Résumé The workshop “DNA Repl..
Un Résultat de Complétude pour les Types du Système F
No full textInternational audienceWe presente in this note a completeness result for the types with positive quantifiers of the J.-Y. Girard type system F. This result generalizes a theorem of R. Labib-Sami
Howdo Cdc7 and cyclin-dependent kinases trigger the initiation of chromosome replication in eukaryotic cells?
No full textChromosome replication occurs precisely once during the cell cycle of almost all eukaryotic cells, and is a highly complex process that is still understood relatively poorly. Two conserved kinases called Cdc7 (cell division cycle 7) and cyclin-dependent kinase (CDK) are required to establish replication forks during the initiation of chromosome replication, and a key feature of this process is the activation of the replicative DNA helicase in situ at each origin of DNA replication. A series of recent studies has shed new light on the targets of Cdc7 and CDK, indicating that chromosome replication probably initiates by a fundamentally similar mechanism in all eukaryotes
Résultats de complétude pour des classes de types du système AF2
No full textInternational audienceJ.-L. Krivine introduced the AF2 type system in order to obtain programs (-terms) which calculate functions, by writing demonstrations of their totalities. We present in this paper two results of completness for some types of AF2 and for many notions of reductions. These results generalize a theorem of R. Labib-Sami established in the system F of J.-Y. Girard
- …
