Author: "Department of Computer Science [Purdue]" / Publisher: hal ccsd - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Department of Computer Science [Purdue]"' showing total 52 results

Start Over Author "Department of Computer Science [Purdue]" Publisher hal ccsd

52 results on '"Department of Computer Science [Purdue]"'

1. Coarse-grained olivine-rich regolith at jezero crater, mars: nature, source and transport

Author: Beyssac, O., Chide, B., Cousin, A., Ayoub, F., Bertrand, T., Forni, O., Mandon, L., Beck, P., Johnson, J. R., Lasue, J., Clavé, E., Sullivan, R., Nataf, C. Quantin, Udry, A., Dehouck, E., Poulet, F., Pilorget, C., Fouchet, T., Meslin, P.Y., Gasnault, O., Maurice, S., Wiens, R.C., Institut de minéralogie, de physique des matériaux et de cosmochimie (IMPMC), Muséum national d'Histoire naturelle (MNHN)-Institut de recherche pour le développement [IRD] : UR206-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Los Alamos National Laboratory (LANL), Institut de recherche en astrophysique et planétologie (IRAP), Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire Midi-Pyrénées (OMP), Institut de Recherche pour le Développement (IRD)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National d'Études Spatiales [Toulouse] (CNES)-Centre National de la Recherche Scientifique (CNRS)-Météo-France -Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National d'Études Spatiales [Toulouse] (CNES)-Centre National de la Recherche Scientifique (CNRS)-Météo-France -Centre National de la Recherche Scientifique (CNRS), Institut de Planétologie et d'Astrophysique de Grenoble (IPAG), Centre National d'Études Spatiales [Toulouse] (CNES)-Observatoire des Sciences de l'Univers de Grenoble (OSUG ), Institut national des sciences de l'Univers (INSU - CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Grenoble Alpes (UGA)-Météo-France -Institut national des sciences de l'Univers (INSU - CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Grenoble Alpes (UGA)-Météo-France, Johns Hopkins University Applied Physics Laboratory [Laurel, MD] (APL), Centre d'Etudes Lasers Intenses et Applications (CELIA), Université de Bordeaux (UB)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Géologie de Lyon - Terre, Planètes, Environnement (LGL-TPE), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut national des sciences de l'Univers (INSU - CNRS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Institut d'astrophysique spatiale (IAS), Institut national des sciences de l'Univers (INSU - CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Centre National d’Études Spatiales [Paris] (CNES), Université Paris-Sud - Paris 11 (UP11)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Centre National d’Études Spatiales [Paris] (CNES), Laboratoire d'études spatiales et d'instrumentation en astrophysique (LESIA), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], and Lunar and Planetary Institute
Subjects: [SDU.STU.PL]Sciences of the Universe [physics]/Earth Sciences/Planetology, [SDU]Sciences of the Universe [physics], [SDU.ASTR.EP]Sciences of the Universe [physics]/Astrophysics [astro-ph]/Earth and Planetary Astrophysics [astro-ph.EP]
Abstract: International audience
Published: 2023

2. Supercam first shots: dust composition and variability

Author: Lasue, J., Meslin, P.Y., Cousin, A., Forni, O., Anderson, R., Beck, P., Beyssac, O., Brown, A., Clegg, S.M., Dehouck, E., Frydenvang, J., Gasda, P., Gasnault, O., Hausrath, E., Pilleri, P., Rapin, W., Wiens, R.C., Team, The Supercam, Institut de recherche en astrophysique et planétologie (IRAP), Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire Midi-Pyrénées (OMP), Institut de Recherche pour le Développement (IRD)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National d'Études Spatiales [Toulouse] (CNES)-Centre National de la Recherche Scientifique (CNRS)-Météo-France -Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National d'Études Spatiales [Toulouse] (CNES)-Centre National de la Recherche Scientifique (CNRS)-Météo-France -Centre National de la Recherche Scientifique (CNRS), United States Geological Survey (USGS), Institut de Planétologie et d'Astrophysique de Grenoble (IPAG), Centre National d'Études Spatiales [Toulouse] (CNES)-Observatoire des Sciences de l'Univers de Grenoble (OSUG ), Institut national des sciences de l'Univers (INSU - CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Grenoble Alpes (UGA)-Météo-France -Institut national des sciences de l'Univers (INSU - CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Grenoble Alpes (UGA)-Météo-France, Bioinformatique et BioPhysique [IMPMC] (IMPMC_BIBIP), Institut de minéralogie, de physique des matériaux et de cosmochimie (IMPMC), Muséum national d'Histoire naturelle (MNHN)-Institut de recherche pour le développement [IRD] : UR206-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Muséum national d'Histoire naturelle (MNHN)-Institut de recherche pour le développement [IRD] : UR206-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Theoretical Division [LANL], Los Alamos National Laboratory (LANL), Laboratoire de Géologie de Lyon - Terre, Planètes, Environnement (LGL-TPE), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut national des sciences de l'Univers (INSU - CNRS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], and Lunar and Planetary Institute
Subjects: [SDU.STU.PL]Sciences of the Universe [physics]/Earth Sciences/Planetology, [SDU]Sciences of the Universe [physics], [SDU.ASTR.EP]Sciences of the Universe [physics]/Astrophysics [astro-ph]/Earth and Planetary Astrophysics [astro-ph.EP]
Abstract: International audience
Published: 2023

3. Surface-based protein domains retrieval methods from a SHREC2021 challenge

Author: Florent Langenfeld, Tunde Aderinwale, Charles Christoffer, Woong-Hee Shin, Genki Terashi, Xiao Wang, Daisuke Kihara, Halim Benhabiles, Karim Hammoudi, Adnane Cabani, Feryal Windal, Mahmoud Melkemi, Ekpo Otu, Reyer Zwiggelaar, David Hunter, Yonghuai Liu, Léa Sirugue, Huu-Nghia H. Nguyen, Tuan-Duy H. Nguyen, Vinh-Thuyen Nguyen-Truong, Danh Le, Hai-Dang Nguyen, Minh-Triet Tran, Matthieu Montès, Laboratoire Génomique, bioinformatique et chimie moléculaire (GBCM), Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Department of Computer Science [Purdue], Purdue University [West Lafayette], Suncheon National University [Suncheon, Corée du Sud], Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-JUNIA (JUNIA), Université catholique de Lille (UCL)-Université catholique de Lille (UCL), Bio-Micro-Electro-Mechanical Systems - IEMN (BIOMEMS - IEMN), Université catholique de Lille (UCL)-Université catholique de Lille (UCL)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-JUNIA (JUNIA), JUNIA (JUNIA), Université catholique de Lille (UCL), Institut de Recherche en Informatique Mathématiques Automatique Signal - IRIMAS - UR 7499 (IRIMAS), Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA)), Université de Strasbourg (UNISTRA), École Supérieure d’Ingénieurs en Génie Électrique (ESIGELEC), Aberystwyth University, Edge Hill University, Vietnam National University - Ho Chi Minh City (VNU-HCM), and Léa Sirugue, Matthieu Montès and Florent Langenfeld are supported by the European Research Council Executive Agency under the research grant number 640,283. Daisuke Kihara acknowledges supports from the National Institutes of Health (R01GM133840, R01GM123055) and the National Science Foundation (DBI2003635, CMMI1825941, and MCB1925643). Charles Christoffer is supported by NIGMS-funded pre–doctoral fellowship (T32 GM132024). Huu-Nghia H. Nguyen, Tuan-Duy H. Nguyen, Vinh-Thuyen Nguyen-Truong, Danh Le, Hai-Dang Nguyen, and Minh-Triet Tran are supported by National University Ho Chi Minh City (VNU-HCM) (DS2020-42-01).
Subjects: Models, Molecular, Static Electricity, Proteins, Ligands, Computer Graphics and Computer-Aided Design, Article, Proteins surface, [SPI]Engineering Sciences [physics], SHREC2021, Protein Domains, Materials Chemistry, Physical and Theoretical Chemistry, Spectroscopy, 2000 MSC: 92-08
Abstract: publication dans une revue suite à la communication hal-03467479 (SHREC 2021: surface-based protein domains retrieval); International audience; Proteins are essential to nearly all cellular mechanism and the effectors of the cells activities. As such, they often interact through their surface with other proteins or other cellular ligands such as ions or organic molecules. The evolution generates plenty of different proteins, with unique abilities, but also proteins with related functions hence similar 3D surface properties (shape, physico-chemical properties, …). The protein surfaces are therefore of primary importance for their activity. In the present work, we assess the ability of different methods to detect such similarities based on the geometry of the protein surfaces (described as 3D meshes), using either their shape only, or their shape and the electrostatic potential (a biologically relevant property of proteins surface). Five different groups participated in this contest using the shape-only dataset, and one group extended its pre-existing method to handle the electrostatic potential. Our comparative study reveals both the ability of the methods to detect related proteins and their difficulties to distinguish between highly related proteins. Our study allows also to analyze the putative influence of electrostatic information in addition to the one of protein shapes alone. Finally, the discussion permits to expose the results with respect to ones obtained in the previous contests for the extended method. The source codes of each presented method have been made available online.
Published: 2022
Full Text: View/download PDF

4. Metastable Kitaev Magnets

Author: Maignan, Antoine, Schmidt, Marcus, Prots, Yurii, Lebedev, Oleg, Daou, Ramzy, Chang, Chun-Fu, Kuo, Chang-Yang, Hu, Zhiwei, Chen, Chien-Te, Weng, Shih-Chang, Altendorf, Simone, Tjeng, Liu-Hao, Grin, Yuri, International Iberian Nanotechnology Laboratory (INL), Ludwig-Maximilians-Universität München (LMU), Laboratoire de cristallographie et sciences des matériaux (CRISMAT), Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche sur les Matériaux Avancés (IRMA), Normandie Université (NU)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université de Rouen Normandie (UNIROUEN), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Institut des Sciences et Techniques de la Réadaptation [Lyon] (ISTR), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Ministry of Science and Technology of the People’s Republic of China, Department of Chemical Sciences, University of Messina, Dipartimento di Fisica e Astronomia 'Galileo Galilei', Università degli Studi di Padova = University of Padua (Unipd), CICNanoGUNE, Universidad Complutense de Madrid = Complutense University of Madrid [Madrid] (UCM), Boston College (BC), Laboratoire Léon Brillouin (LLB - UMR 12), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Max Planck Institute for chemical Physics of Solids, Max Planck Institute for Chemical Physics of Solids (CPfS), and Max-Planck-Gesellschaft
Subjects: Oxygen evolution reaction, Polymers and Plastics, Phthalocyanines, [CHIM.MATE]Chemical Sciences/Material chemistry, Catalysis, Electronic, Optical and Magnetic Materials, Biomaterials, Colloid and Surface Chemistry, Materials Chemistry, Covalent organic frameworks, Phthalocyanines, Earth abundant transition metals, Electrocatalysis, Oxygen evolution reaction, [CHIM]Chemical Sciences, Earth abundant transition metals, Electrocatalysis, Covalent organic frameworks
Abstract: International audience; Nearly two decades ago, Alexei Kitaev proposed a model for spin-1/2 particles with bond-directional interactions on a two-dimensional honeycomb lattice which had the potential to host a quantum spin-liquid ground state. This work initiated numerous investigations to design and synthesize materials that would physically realize the Kitaev Hamiltonian. The first generation of such materials, such as Na2IrO3, α-Li2IrO3, and α-RuCl3, revealed the presence of non-Kitaev interactions such as the Heisenberg and off-diagonal exchange. Both physical pressure and chemical doping were used to tune the relative strength of the Kitaev and competing interactions; however, little progress was made towards achieving a purely Kitaev system. Here, we review the recent breakthrough in modifying Kitaev magnets via topochemical methods that has led to the second generation of Kitaev materials. We show how structural modifications due to the topotactic exchange reactions can alter the magnetic interactions in favor of a quantum spin-liquid phase.
Published: 2022
Full Text: View/download PDF

5. Urban Brush: Intuitive and Controllable Urban Layout Editing

Author: Xiaochen Zhou, Bedrich Benes, Marie-Paule R. Cani, Pascal Chang, Purdue University [West Lafayette], Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Department of Computer Science [Purdue]
Subjects: Engineering drawing, Computer science, 0211 other engineering and technologies, Volume (computing), Brush, 020207 software engineering, 021107 urban & regional planning, 02 engineering and technology, 15. Life on land, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], law.invention, Entertainment, Computer graphics, Set (abstract data type), Block (programming), law, Atomic operations, 0202 electrical engineering, electronic engineering, information engineering, Key (cryptography), [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We present a novel method for authoring landscapes with flora and fauna while considering their mutual interactions. Our algorithm outputs a steady-state ecosystem in the form of density maps for each species, their daily circuits, and a modified terrain with eroded trails from a terrain, climatic conditions, and species with related biological information. We introduce the Resource Access Graph, a new data structure that encodes both interactions between food chain levels and animals traveling between resources over the terrain. A novel competition algorithm operating on this data progressively computes a steady-state solution up the food chain, from plants to carnivores. The user can explore the resulting landscape, where plants and animals are instantiated on the fly, and interactively edit it by over-painting the maps. Our results show that our system enables the authoring of consistent landscapes where the impact of wildlife is visible through animated animals, clearings in the vegetation, and eroded trails. We provide quantitative validation with existing ecosystems and a user-study with expert paleontologist end-users, showing that our system enables them to author and compare different ecosystems illustrating climate changes over the same terrain while enabling relevant visual immersion into consistent landscapes.
Published: 2021
Full Text: View/download PDF

6. Precise Minimax Regret for Logistic Regression

Author: Jacquet, Philippe, Shamir, Gil, Szpankowski, Wojciech, inTeRnet BEyond the usual (TRiBE ), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Google Pittsburgh, Department of Computer Science [Purdue], Purdue University [West Lafayette], and Jacquet, Philippe
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: We study online logistic regression with binary labels and general feature values in which a learner sequentially tries to predict an outcome/ label based on data/ features received in rounds. Our goal is to evaluate precisely the (maximal) minimax regret which we analyze using a unique and novel combination of information-theoretic and analytic combinatoric tools such as Fourier transform, saddle point method, and Mellin transform in the multi-dimensional settings. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all label distributions. For dimension d = o(T 1/3) we show that the maximal minimax regret grows as d 2 log(2T /π) + C d + O(d 3/2 / √ T) where T is the number of rounds of running a training algorithm and C d is explicitly computable constant that depends on dimension d and data. For features uniformly distributed on a d-dimensional sphere or ball we estimate precisely the constant C d showing that C d ∼ −(d/2) log(d/ √ 2π) leading to the minimax regret growing for large d as (d/2) log(T /d) − (d/2) log(√ 8π) + O(1). We also extend these results to non-binary labels. The precise maximal minimax regret presented here is the first result of this kind for any feature values and wide range of d. This provides a precise answer to the challenge posed in McMahan and Streeter (2010).
Published: 2021

7. Precise Minimax Regret for Logistic Regression with Categorical Feature Values

Author: Jacquet, Philippe, Gil I., Shamir, Szpankowski, Wojciech, inTeRnet BEyond the usual (TRiBE ), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Google Inc., Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: [STAT]Statistics [stat], [INFO]Computer Science [cs]
Abstract: We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm (weight vector). In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions. Such a regret still depends on the feature values. For the d = O(1) dimensional logistic regression we show that the maximal minimax regret grows as d 2 log(T /2π) + C + O(1/ √ T) where T is the number of rounds of running a training algorithm and C is explicitly computable constant that depends on the feature values. We also extend these results to non-binary labels. The precise maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.
Published: 2020

8. Semi-Procedural Textures Using Point Process Texture Basis Functions

Author: Guehl, Pascal, Allegre, Rémi, Dischler, Jean-Michel, Benes, Bedrich, Galin, Eric, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA), Department of Computer Science [Purdue], Purdue University [West Lafayette], Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Origami (Origami), ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), univOAK, Archive ouverte, and Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes - - HDWorlds2016 - ANR-16-CE33-0001 - AAPG2016 - VALID
Subjects: noise, [INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR], ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, material synthesis, procedural generation, texture synthesis, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR]
Abstract: International audience; We introduce a novel semi-procedural approach that avoids drawbacks of procedural textures and leverages advantages of data-driven texture synthesis. We split synthesis in two parts: 1) structure synthesis, based on a procedural parametric model and 2) color details synthesis, being data-driven. The procedural model consists of a generic Point Process Texture Basis Function (PPTBF), which extends sparse convolution noises by defining rich convolution kernels. They consist of a window function multiplied with a correlated statistical mixture of Gabor functions, both designed to encapsulate a large span of common spatial stochastic structures, including cells, cracks, grains, scratches, spots, stains, and waves. Parameters can be prescribed automatically by supplying binary structure exemplars. As for noise-based Gaussian textures, the PPTBF is used as stand-alone function, avoiding classification tasks that occur when handling multiple procedural assets. Because the PPTBF is based on a single set of parameters it allows for continuous transitions between different visual structures and an easy control over its visual characteristics. Color is consistently synthesized from the exemplar using a multiscale parallel texture synthesis by numbers, constrained by the PPTBF. The generated textures are parametric, infinite and avoid repetition. The data-driven part is automatic and guarantees strong visual resemblance with inputs. Applications: this work is related to content creation tools for films and video games, especially procedural texture and material synthesis (e.g. Substance Designer), and inverse procedural modeling (e.g inverse shade tree approach).This paper has been published in the CGF journal (Computer Grapics Forum) in July 2020 and presented at the EGSR conference (Eurographics Symposium on Rendering) in July 2020 where it got an award: Honorable Mention from the Best Papers committee.
Published: 2020

9. SHREC 2020: Classification in cryo-electron tomograms

Author: Remco C. Veltkamp, Min Xu, Nguyen P. Nguyen, Xuefeng Cui, Filiz Bunyak, Yu Hao, Xiangrui Zeng, Gijs van der Schot, Tommi A. White, Fa Zhang, Ilja Gubins, Xiao Wang, Daisuke Kihara, Marten L. Chaillet, Friedrich Förster, Xiaohua Wan, Emmanuel Moebel, Department of Information and Computing Sciences [Utrecht], Utrecht University [Utrecht], Department of Chemistry [Utrecht], CAS Institute of Computing Technology (ICT), Chinese Academy of Sciences [Beijing] (CAS), School of Computer Science and Technology [Jinan], Shandong University, Space-timE RePresentation, Imaging and cellular dynamics of molecular COmplexes (SERPICO), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [Purdue], Purdue University [West Lafayette], Computational Biology Department [Pittsburgh], Carnegie Mellon University [Pittsburgh] (CMU), Department of Computer Science Electrical Engineering [Kansas City], University of Missouri [Kansas City] (UMKC), University of Missouri System-University of Missouri System, University of Missouri [St. Louis], and University of Missouri System
Subjects: Artificial neural network, business.industry, Computer science, Template matching, Resolution (electron density), General Engineering, 020207 software engineering, Pattern recognition, Context (language use), 02 engineering and technology, Function (mathematics), Computer Graphics and Computer-Aided Design, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Human-Computer Interaction, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, Benchmark (computing), 020201 artificial intelligence & image processing, Artificial intelligence, Tomography, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Focus (optics), business, [PHYS.PHYS.PHYS-DATA-AN]Physics [physics]/Physics [physics]/Data Analysis, Statistics and Probability [physics.data-an]
Abstract: International audience; Cryo-electron tomography (cryo-ET) is an imaging technique that allows us to three-dimensionally visualize both the structural details of macro-molecular assemblies under near-native conditions and its cellular context. Electrons strongly interact with biological samples, limiting electron dose. The latter limits the signal-to-noise ratio and hence resolution of an individual tomogram to about 50 (5 nm). Biological molecules can be obtained by averaging volumes, each depicting copies of the molecule, allowing for resolutions beyond 4 (0.4 nm). To this end, the ability to localize and classify components is crucial, but challenging due to the low signal-to-noise ratio. Computational innovation is key to mine biological information from cryo-electron tomography.To promote such innovation, we provide a novel simulated dataset to benchmark different methods of localization and classification of biological macromolecules in cryo-electron tomograms. Our publicly available dataset contains ten tomographic reconstructions of simulated cell-like volumes. Each volume contains twelve different types of complexes, varying in size, function and structure.In this paper, we have evaluated seven different methods of finding and classifying proteins. Six research groups present results obtained with learning-based methods and trained on the simulated dataset, as well as a baseline template matching, a traditional method widely used in cryo-ET research. We find that method performance correlates with particle size, especially noticeable for template matching which performance degrades rapidly as the size decreases. We learn that neural networks can achieve significantly better localization and classification performance, in particular convolutional networks with focus on high-resolution details such as those based on U-Net architecture.
Published: 2020
Full Text: View/download PDF

10. Semi‐Procedural Textures Using Point Process Texture Basis Functions

Author: Eric Galin, Jean-Michel Dischler, Rémi Allègre, Pascal Guehl, Bedrich Benes, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA), Department of Computer Science [Purdue], Purdue University [West Lafayette], Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Origami (Origami), ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: noise, Computer science, business.industry, 020207 software engineering, Pattern recognition, Basis function, 02 engineering and technology, material synthesis, procedural generation, Computer Graphics and Computer-Aided Design, Window function, texture synthesis, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Convolution, Rendering (computer graphics), 0202 electrical engineering, electronic engineering, information engineering, Procedural texture, 020201 artificial intelligence & image processing, Artificial intelligence, business, Texture synthesis
Abstract: We introduce a novel semi-procedural approach that avoids drawbacks of procedural textures and leverages advantages of data-driven texture synthesis. We split synthesis in two parts: 1) structure synthesis, based on a procedural parametric model and 2) color details synthesis, being data-driven. The procedural model consists of a generic Point Process Texture Basis Function (PPTBF), which extends sparse convolution noises by defining rich convolution kernels. They consist of a window function multiplied with a correlated statistical mixture of Gabor functions, both designed to encapsulate a large span of common spatial stochastic structures, including cells, cracks, grains, scratches, spots, stains, and waves. Parameters can be prescribed automatically by supplying binary structure exemplars. As for noise-based Gaussian textures, the PPTBF is used as stand-alone function, avoiding classification tasks that occur when handling multiple procedural assets. Because the PPTBF is based on a single set of parameters it allows for continuous transitions between different visual structures and an easy control over its visual characteristics. Color is consistently synthesized from the exemplar using a multiscale parallel texture synthesis by numbers, constrained by the PPTBF. The generated textures are parametric, infinite and avoid repetition. The data-driven part is automatic and guarantees strong visual resemblance with inputs. Applications: this work is related to content creation tools for films and video games, especially procedural texture and material synthesis (e.g. Substance Designer), and inverse procedural modeling (e.g inverse shade tree approach). This paper has been published in the CGF journal (Computer Grapics Forum) in July 2020 and presented at the EGSR conference (Eurographics Symposium on Rendering) in July 2020 where it got an award: Honorable Mention from the Best Papers committee.
Published: 2020
Full Text: View/download PDF

11. Power-Law Degree Distribution in the Connected Component of a Duplication Graph

Author: Jacquet, Philippe, Turowski, Krzysztof, Szpankowski, Wojciech, inTeRnet BEyond the usual (TRiBE ), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Uniwersytet Jagielloński w Krakowie = Jagiellonian University (UJ), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: pure duplication model, tail exponent, analytic combinatorics, [INFO]Computer Science [cs], [MATH]Mathematics [math], degree distribution, random graphs, ComputingMilieux_MISCELLANEOUS
Abstract: We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis., LIPIcs, Vol. 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), pages 16:1-16:14
Published: 2020

12. Dendry: A Procedural Model for Dendritic Patterns

Author: Damien Rohmer, Bedrich Benes, Mathieu Gaillard, Marie-Paule Cani, Eric Galin, Eric Guérin, Guérin, Eric, Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes - - HDWorlds2016 - ANR-16-CE33-0001 - AAPG2016 - VALID, Department of Computer Science [Purdue], Purdue University [West Lafayette], Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Fonds National pour la Societé Numérique - PAPAYA P110720-2659260, ANR HDWorlds, and ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016)
Subjects: Computer science, [INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR], 020207 software engineering, 02 engineering and technology, Function (mathematics), 010502 geochemistry & geophysics, 01 natural sciences, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Maxima and minima, Tree structure, 0202 electrical engineering, electronic engineering, information engineering, Range (statistics), Memory footprint, Geometric modeling, Procedural modeling, Algorithm, Smoothing, ComputingMilieux_MISCELLANEOUS, 0105 earth and related environmental sciences
Abstract: We introduce Dendry, a procedural function that generates dendritic patterns and is locally computable. The function is controlled by parameters such as the level of branching, the degree of local smoothing, random seeding and local disturbance parameters, and the range of the branching angles. It is also controlled by a global control function that defines the overall shape and can be used, for example, to initialize local minima. The algorithm returns the distance to a tree structure which is implicitly constructed on the fly, while requiring a small memory footprint. The evaluation can be performed in parallel for multiple points and scales linearly with the number of cores. We demonstrate an application of our model to the generation of terrain heighfields with consistent river networks. A quad core implementation of our algorithm takes about ten seconds for a 512 × 512 resolution grid on the CPU.
Published: 2019

13. A Review of Digital Terrain Modeling

Author: Guillaume Cordonnier, James Gain, Eric Galin, Bedrich Benes, Eric Guérin, Marie-Paule Cani, Adrien Peytavie, Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Department of Computer Science [Purdue], Purdue University [West Lafayette], University of Cape Town, ANR HDWorlds, Fonds National pour la Societé Numérique - PAPAYA P110720-2659260, and ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016)
Subjects: geography, geography.geographical_feature_category, Computer science, Landform, 020207 software engineering, Terrain, 02 engineering and technology, 15. Life on land, Computer Graphics and Computer-Aided Design, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Variety (cybernetics), Computer graphics, Human–computer interaction, Component (UML), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Scale (map), Procedural modeling, Mountain range, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; Terrains are a crucial component of three-dimensional scenes and are present in many Computer Graphics applications. Terrain modeling methods focus on capturing landforms in all their intricate detail, including eroded valleys arising from the interplay of varied phenomena, dendritic mountain ranges, and complex river networks. Set against this visual complexity is the need for user control over terrain features, without which designers are unable to adequately express their artistic intent. This article provides an overview of current terrain modeling and authoring techniques, organized according to three categories: procedural modeling, physically-based simulation of erosion and land formation processes, and example-based methods driven by scanned terrain data. We compare and contrast these techniques according to several criteria, specifically: the variety of achievable landforms; realism from both a perceptual and geomorphological perspective; issues of scale in terms of terrain extent and sampling precision; the different interaction metaphors and attendant forms of user-control, and computation and memory performance. We conclude with an in-depth discussion of possible research directions and outstanding technical and scientific challenges.
Published: 2019
Full Text: View/download PDF

14. Verifying a Concurrent Garbage Collector with a Rely-Guarantee Methodology

Author: Jan Vitek, Gustavo Petri, Yannick Zakowski, Delphine Demange, David Cachera, Suresh Jagannathan, David Pichardie, École normale supérieure - Rennes (ENS Rennes), Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Northeastern University [Boston], ANR-14-CE28-0004,DISCOVER,Représentations Intermédiaires et Sémantiques de la Concurrence pour les Compilateurs Vérifiés(2014), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: Soundness, Intermediate language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Computer science, Concurrent data structure, Proof assistant, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Computational Theory and Mathematics, 010201 computation theory & mathematics, Artificial Intelligence, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, Compiler, computer, Software, Program logic, Garbage collection
Abstract: International audience; Concurrent garbage collection algorithms are a challenge for program verification. In this paper, we address this problem by proposing a mechanized proof methodology based on the Rely-Guarantee proof technique. We design a compiler intermediate representation with strong type guarantees, dedicated support for abstract concurrent data structures, and high-level iterators on runtime internals. In addition, we define an Rely-Guarantee program logic supporting an incremental proof methodology where annotations and invariants can be progressively enriched. We formalize the intermediate representation, the proof system, and prove the soundness of the methodology in the Coq proof assistant. Equipped with this, we prove a fully concurrent garbage collector where mutators never have to wait for the collector.
Published: 2018
Full Text: View/download PDF

15. Revisiting random walk based sampling in networks: Evasion of burn-in period and frequent regenerations

Author: Vivek S. Borkar, Arun Kadavankandy, Jithin K. Sreedharan, Konstantin Avrachenkov, Network Engineering and Operations (NEO ), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Electrical Engineering [IIT-Bombay] (EE-IIT), Indian Institute of Technology Kanpur (IIT Kanpur), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: Mean squared error, Respondent-driven sampling, Computer science, Stability (learning theory), 02 engineering and technology, Stochastic approximation, 01 natural sciences, lcsh:QA75.5-76.95, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], 010104 statistics & probability, symbols.namesake, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Reinforcement learning, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Network sampling, Random walks on graph, lcsh:T58.5-58.64, lcsh:Information technology, Research, Sampling (statistics), Estimator, 020206 networking & telecommunications, Markov chain Monte Carlo, Complex network, Random walk, Computer Science Applications, Human-Computer Interaction, Modeling and Simulation, symbols, lcsh:Electronic computers. Computer science, Algorithm, Information Systems
Abstract: International audience; Background: In the framework of network sampling, random walk (RW) based estimation techniques provide many pragmatic solutions while uncovering the unknown network as little as possible. Despite several theoretical advances in this area, RW based sampling techniques usually make a strong assumption that the samples are in stationary regime, and hence are impelled to leave out the samples collected during the burn-in period. Methods: This work proposes two sampling schemes without burn-in time constraint to estimate the average of an arbitrary function defined on the network nodes, for example, the average age of users in a social network. The central idea of the algorithms lies in exploiting regeneration of RWs at revisits to an aggregated super-node or to a set of nodes, and in strategies to enhance the frequency of such regenerations either by contracting the graph or by making the hitting set larger. Our first algorithm, which is based on reinforcement learning (RL), uses stochastic approximation to derive an estimator. This method can be seen as intermediate between purely stochastic Markov chain Monte Carlo iterations and deterministic relative value iterations. The second algorithm, which we call the Ratio with Tours (RT)-estimator, is a modified form of respondent-driven sampling (RDS) that accommodates the idea of regeneration. Results: We study the methods via simulations on real networks. We observe that the trajectories of RL-estimator are much more stable than those of standard random walk based estimation procedures, and its error performance is comparable to that of respondent-driven sampling (RDS) which has a smaller asymptotic variance than many other estimators. Simulation studies also show that the mean squared error of RT-esti-mator decays much faster than that of RDS with time. Conclusion: The newly developed RW based estimators (RL-and RT-estimators) allow to avoid burn-in period, provide better control of stability along the sample path, and overall reduce the estimation time. Our estimators can be applied in social and complex networks.
Published: 2018
Full Text: View/download PDF

16. Verifying a Concurrent Garbage Collector using a Rely-Guarantee Methodology

Author: Gustavo Petri, David Cachera, Delphine Demange, Jan Vitek, David Pichardie, Yannick Zakowski, Suresh Jagannathan, Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Northeastern University [Boston], ANR 14-CE28-0004, NSF CCF- 1318227, CCF-1544542, SHF-1518844, ONR N00014-15-1-2332, ANR-14-CE28-0004,DISCOVER,Représentations Intermédiaires et Sémantiques de la Concurrence pour les Compilateurs Vérifiés(2014), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)
Subjects: Soundness, Intermediate language, Computer science, Programming language, Concurrent data structure, Proof assistant, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, Compiler, computer, Garbage collection, Program logic
Abstract: International audience; Concurrent garbage collection algorithms are an emblematic challenge in the area of concurrent program verification. In this paper, we address this problem by proposing a mechanized proof methodology based on the popular Rely-Guarantee (RG) proof technique. We design a specific compiler intermediate representation (IR) with strong type guarantees, dedicated support for abstract concurrent data structures, and high-level iterators on runtime internals. In addition, we define an RG program logic supporting an incremental proof methodology where annotations and invariants can be progressively enriched.We formalize the IR, the proof system, and prove the soundness of the methodology in the Coq proof assistant. Equipped with this IR, we prove a fully concurrent garbage collector where mutators never have to wait for the collector.
Published: 2017
Full Text: View/download PDF

17. Prediction of homo- and hetero-protein complexes by protein docking and template-based modeling: a CASP-CAPRI experiment

Author: Eichiro Ichiishi, Dmitri Beglov, Bernard Maigret, Gyu Rie Lee, Artem B. Mamonov, Shoshana J. Wodak, Jonathan C. Fuller, Dima Kozakov, Jong Young Joung, Petr Popov, Xiaofeng Yu, Keehyoung Joo, João P. G. L. M. Rodrigues, Anna Vangone, Koen M. Visscher, Xiaoqin Zou, Paul A. Bates, Andriy Kryshtafovych, Shourya S. Roy Burman, Daisuke Kihara, Romina Oliva, Efrat Ben-Zeev, Jeffrey J. Gray, Yang Shen, Li C. Xue, Sameer Velankar, Emilie Neveu, Shruthi Viswanath, Dina Schneidman-Duhovny, Juan Esquivel-Rodríguez, Mieczyslaw Torchala, Amit Roy, Alexandre M. J. J. Bonvin, David R. Hall, Tanggis Bohnuud, Xusi Han, David W. Ritchie, Ron Elber, Daisuke Kuroda, Zhiwei Ma, Joan Segura, Carlos A. Del Carpio, Nicholas A. Marze, Jong Yun Kim, Andrej Sali, Petras J. Kundrotas, Ezgi Karaca, Neil J. Bruce, Chaok Seok, Panagiotis L. Kastritis, Shen You Huang, Ilya A. Vakser, Lim Heo, Sanbo Qin, Raphael A. G. Chaleil, Adrien S. J. Melquiond, Miguel Romero-Durana, Anisah W. Ghoorah, Surendra S. Negi, Andrey Tovchigrechko, Françoise Ochsenbein, Narcis Fernandez-Fuentes, Liming Qiu, Miriam Eisenstein, Mehdi Nellen, Marie-Dominique Devignes, Lenna X. Peterson, Jinchao Yu, Minkyung Baek, Brian G. Pierce, Hasup Lee, Toshiyuki Oda, Rebecca C. Wade, Raphael Guerois, Juan Fernández-Recio, Iain H. Moal, Edrisse Chermak, Sergei Grudinin, Sangwoo Park, Ivan Anishchenko, Chengfei Yan, Thom Vreven, Kentaro Tomii, Bing Xia, Hyung Rae Kim, Chiara Pallara, Jooyoung Lee, Kazunori D. Yamada, Xianjin Xu, Kenichiro Imai, Zhiping Weng, Luigi Cavallo, Tyler M. Borrman, Jianlin Cheng, Marc F. Lensink, Huan-Xiang Zhou, Jilong Li, Gydo C. P. van Zundert, Brian Jiménez-García, Tsukasa Nakamura, Scott E. Mottarella, Sandor Vajda, Institut de Recherche Interdisciplinaire [Villeneuve d'Ascq] ( IRI ), Université de Lille, Sciences et Technologies-Université de Lille, Droit et Santé-Centre National de la Recherche Scientifique ( CNRS ), European Molecular Biology Laboratory, European Bioinformatics Institute, Genome Center [UC Davis], University of California at Davis, Research Support Computing [Columbia], University of Missouri-Columbia, Bioinformatics Consortium and Department of Computer Science [Columbia], Department of Bioengineering and Therapeutic Sciences, University of California [San Francisco] ( UCSF ), Department of Pharmaceutical Chemistry, Department of Bioengineering and Therapeutic Sciences, Department of Pharmaceutical Chemistry, University of California [San Francisco] ( UCSF ) -California Institute for Quantitative Biosciences, GN7 of the National Institute for Bioinformatics (INB) and Biocomputing Unit, Centro Nacional de Biotecnología (CSIC), Institute of Biological, Environmental and Rural Sciences ( IBERS ), Institute for Computational Engineering and Sciences [Austin] ( ICES ), University of Texas at Austin [Austin], Department of Computer Science, Department of Chemistry, Algorithms for Modeling and Simulation of Nanosystems ( NANO-D ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Laboratoire Jean Kuntzmann ( LJK ), Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Université Pierre Mendès France - Grenoble 2 ( UPMF ) -Université Joseph Fourier - Grenoble 1 ( UJF ) -Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ) -Institut National Polytechnique de Grenoble ( INPG ), Moscow Institute of Physics and Technology [Moscow] ( MIPT ), Seoul National University [Seoul], Florida State University [Tallahassee] ( FSU ), Computational Algorithms for Protein Structures and Interactions ( CAPSID ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Department of Complex Systems, Artificial Intelligence & Robotics ( LORIA - AIS ), Laboratoire Lorrain de Recherche en Informatique et ses Applications ( LORIA ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université de Lorraine ( UL ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université de Lorraine ( UL ) -Centre National de la Recherche Scientifique ( CNRS ) -Laboratoire Lorrain de Recherche en Informatique et ses Applications ( LORIA ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université de Lorraine ( UL ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Lorraine ( UL ) -Centre National de la Recherche Scientifique ( CNRS ), University of Mauritius, Biomolecular Modelling Laboratory, The Francis Crick Institute, Lincoln's Inn Fields Laboratory, G-INCPM, Weizmann Institute of Science, Chemical Research Support [Rehovot], Sealy Center for Structural Biology and Molecular Biophysics, The University of Texas Medical Branch ( UTMB ), Program in Bioinformatics and Integrative Biology [Worcester], University of Massachusetts Medical School [Worcester] ( UMASS ), Institut de Biologie Intégrative de la Cellule ( I2BC ), Université Paris-Saclay-Centre National de la Recherche Scientifique ( CNRS ) -Commissariat à l'énergie atomique et aux énergies alternatives ( CEA ) -Université Paris-Sud - Paris 11 ( UP11 ), Bijvoet Center for Biomolecular Research [Utrecht], Utrecht University [Utrecht], Dalton Cardiovascular Research Center [Columbia], Department of Computer Science [Columbia], Informatics Intitute, Department of Biochemistry, University of Missouri, UNIVERSITY OF MISSOURI, Toyota Technological Institute at Chicago [Chicago] ( TTIC ), Department of Biological Sciences, Purdue University, Purdue University [West Lafayette], Department of Computer Science [Purdue], Bioinformatics and Computational Biosciences Branch, Rocky Mountain Laboratories, Molecular and Cellular Modeling Group, Heidelberg Institute of Theoretical Studies, Center for Molecular Biology ( ZMBH ), Universität Heidelberg [Heidelberg], Interdisciplinary Center for Scientiﬁc Computing ( IWR ), Department of Molecular Biosciences [Lawrence], University of Kansas [Lawrence] ( KU ), Computational Biology Research Center ( CBRC ), National Institute of Advanced Industrial Science and Technology ( AIST ), Graduate School of Frontier Sciences, The University of Tokyo, Joint BSC-CRG-IRB Research Program in Computational Biology, Barcelona Supercomputing Center - Centro Nacional de Supercomputacion ( BSC - CNS ), Center for In-Silico Protein Science, Korea Institute for Advanced Study ( KIAS ), Center for Advanced Computation, Department of Biomedical Engineering [Boston], Boston University [Boston] ( BU ), Institute of Biological Diversity, International Pacific Institute of Indiana, Drosophila Genetic Resource Center, Kyoto Institute of Technology, International University of Health and Welfare Hospital ( IUHW Hospital ), International University of Health and Welfare Hospital, Department of Chemical and Biomolecular Engineering [Baltimore], Johns Hopkins University ( JHU ), Program in Molecular Biophysics [Baltimore], King Abdullah University of Science and Technology ( KAUST ), University of Naples, J Craig Venter Institute, Structural Biology Research Center, VIB, 1050 Brussels, Belgium, Institut de Recherche Interdisciplinaire [Villeneuve d'Ascq] (IRI), Université de Lille, Sciences et Technologies-Université de Lille, Droit et Santé-Centre National de la Recherche Scientifique (CNRS), European Bioinformatics Institute [Hinxton] (EMBL-EBI), EMBL Heidelberg, University of California [Davis] (UC Davis), University of California (UC)-University of California (UC), University of Missouri [Columbia] (Mizzou), University of Missouri System, University of California [San Francisco] (UC San Francisco), Centro Nacional de Biotecnología [Madrid] (CNB-CSIC), Consejo Superior de Investigaciones Científicas [Madrid] (CSIC)-Consejo Superior de Investigaciones Científicas [Madrid] (CSIC), Institute of Biological, Environmental and Rural Sciences (IBERS), Institute for Computational Engineering and Sciences [Austin] (ICES), Algorithms for Modeling and Simulation of Nanosystems (NANO-D), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Moscow Institute of Physics and Technology [Moscow] (MIPT), Seoul National University [Seoul] (SNU), Florida State University [Tallahassee] (FSU), Computational Algorithms for Protein Structures and Interactions (CAPSID), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Complex Systems, Artificial Intelligence & Robotics (LORIA - AIS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Biomolecular Modelling Laboratory [London], The Francis Crick Institute [London], Weizmann Institute of Science [Rehovot, Israël], The University of Texas Medical Branch (UTMB), University of Massachusetts Medical School [Worcester] (UMASS), University of Massachusetts System (UMASS)-University of Massachusetts System (UMASS), Institut de Biologie Intégrative de la Cellule (I2BC), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Assemblage moléculaire et intégrité du génome (AMIG), Département Biochimie, Biophysique et Biologie Structurale (B3S), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut de Biologie Intégrative de la Cellule (I2BC), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), University of Missouri System-University of Missouri System, Toyota Technological Institute at Chicago [Chicago] (TTIC), Department of Biological Sciences [Lafayette IN], Heidelberg Institute for Theoretical Studies (HITS ), Center for Molecular Biology (ZMBH), Universität Heidelberg [Heidelberg] = Heidelberg University, Interdisciplinary Center for Scientiﬁc Computing (IWR), University of Kansas [Lawrence] (KU), Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), The University of Tokyo (UTokyo), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), Korea Institute for Advanced Study (KIAS), Boston University [Boston] (BU), International University of Health and Welfare Hospital (IUHW Hospital), Johns Hopkins University (JHU), King Abdullah University of Science and Technology (KAUST), University of Naples Federico II = Università degli studi di Napoli Federico II, J. Craig Venter Institute, VIB-VUB Center for Structural Biology [Bruxelles], VIB [Belgium], Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Droit et Santé-Université de Lille, Sciences et Technologies, University of California-University of California, University of California [San Francisco] (UCSF), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), University of Naples Federico II, Barcelona Supercomputing Center, NMR Spectroscopy, and Sub NMR Spectroscopy
Subjects: 0301 basic medicine, Protein Conformation, alpha-Helical, Protein Folding, Computer science, International Cooperation, Amino Acid Motifs, Oligomer state, Homoprotein, DATA-BANK, computer.software_genre, Molecular Docking Simulation, Biochemistry, CAPRI Round 30, DESIGN, Structural Biology, ALIGN, Blind prediction, AFFINITY, Protein interaction, Enginyeria biomèdica [Àrees temàtiques de la UPC], ZDOCK, Oligomer State, computer.file_format, Articles, Protein structure prediction, Proteïnes--Investigació, 3. Good health, WEB SERVER, CASP, Thermodynamics, Data mining, CAPRI, Protein docking, Molecular Biology, Algorithms, INTERFACES, Protein Binding, [ INFO.INFO-MO ] Computer Science [cs]/Modeling and Simulation, Bioinformatics, STRUCTURAL BIOLOGY, Computational biology, Molecular Dynamics Simulation, Article, 03 medical and health sciences, [ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM], Heteroprotein, Humans, Protein binding, Macromolecular docking, Protein Interaction Domains and Motifs, Homology modeling, ALGORITHM, Protein-protein docking, Internet, Binding Sites, Models, Statistical, 030102 biochemistry & molecular biology, Bacteria, Sequence Homology, Amino Acid, Computational Biology, Proteins, Protein Data Bank, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Protein Structure, Tertiary, 030104 developmental biology, Structural biology, Docking (molecular), Protein structure, Protein Conformation, beta-Strand, Protein Multimerization, oligomer state, blind prediction, protein interaction, protein docking, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], computer, Software
Abstract: We present the results for CAPRI Round 30, the first joint CASP-CAPRI experiment, which brought together experts from the protein structure prediction and protein–protein docking communities. The Round comprised 25 targets from amongst those submitted for the CASP11 prediction experiment of 2014. The targets included mostly homodimers, a few homotetramers, and two heterodimers, and comprised protein chains that could readily be modeled using templates from the Protein Data Bank. On average 24 CAPRI groups and 7 CASP groups submitted docking predictions for each target, and 12 CAPRI groups per target participated in the CAPRI scoring experiment. In total more than 9500 models were assessed against the 3D structures of the corresponding target complexes. Results show that the prediction of homodimer assemblies by homology modeling techniques and docking calculations is quite successful for targets featuring large enough subunit interfaces to represent stable associations. Targets with ambiguous or inaccurate oligomeric state assignments, often featuring crystal contact-sized interfaces, represented a confounding factor. For those, a much poorer prediction performance was achieved, while nonetheless often providing helpful clues on the correct oligomeric state of the protein. The prediction performance was very poor for genuine tetrameric targets, where the inaccuracy of the homology-built subunit models and the smaller pair-wise interfaces severely limited the ability to derive the correct assembly mode. Our analysis also shows that docking procedures tend to perform better than standard homology modeling techniques and that highly accurate models of the protein components are not always required to identify their association modes with acceptable accuracy. We are most grateful to the PDBe at the European Bioinformatics Institute in Hinxton, UK, for hosting the CAPRI website. Our deepest thanks go to all the structural biologists and to the following structural genomics initiatives: Northeast Structural Genomics Consortium, Joint Center for Structural Genomics, NatPro PSI:Biology, New York Structural Genomics Research Center, Midwest Center for Structural Genomics, Structural Genomics Consortium, for contributing the targets for this joint CASP-CAPRI experiment. MFL acknowledges support from the FRABio FR3688 Research Federation “Structural & Functional Biochemistry of Biomolecular Assemblies.”
Published: 2016
Full Text: View/download PDF

18. Consistency in 3D

Author: Shapiro, Marc, Saeida Ardekani, Masoud, Petri, Gustavo, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Samsung Research America [San José], Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche en Informatique et Automatique (Inria)
Subjects: D.1.3 Concurrent programming, Structural invariants, D.2.4 Vérification de programme et de logiciel, Correctness of distributed systems, E.1 Structures de données réparties, Invariants de structurels, C.2.4 Distributed databases, Caractère correct de système réparti, Données répliquées, Modèles de cohérence, Replicated data, E.1 Distributed data structures, [INFO]Computer Science [cs], Consistency models, D.2.4 Software/Program Verification, C.2.4 Bases de données réparties, D.1.3 Programmation parallèle
Abstract: Comparisons of different consistency models often try to place them in a linear strong-to-weak order. However this view is clearly inadequate, since it is well known, for instance, that Snapshot Isolation and Serialisability are incomparable. In the interest of a better understanding, we propose a new classification, along three dimensions, related to: a total order of writes, a causal order of reads, and transactional composition of multiple operations. A model may be stronger than another on one dimension and weaker on another. We believe that this new classification scheme is both scientifically sound and has good explicative value. The current paper presents the three-dimensional design space intuitively.; Les comparaisons entre modèles de la cohérence tentent souvent de les classer dans un ordre linéaire, de faible à forte. Cette vue est clairement inadéquate, puisque il est bien connu que, par exemple, les modèles Snapshot Isolation et Serialisability sont incomparables. Dans l'intérêt d'une meilleure compréhension du domaine, nous proposons une nouvelle classification, en trois dimensions~: les garanties liées à un ordre total des écritures~; celles liées à un ordre causal des lectures~; et celles liées à la composition transactionelle d'opérations multiples. Un modèle peut être plus fort qu'un autre dans une dimension, et moins dans une autre. Nous pensons que ce nouveau schéma de classification, à la fois est scientifiquement valide, et a une bonne valeur explicative. Le présent rapport présente l'espace de conception en trois dimensions de façon intuitive.
Published: 2016

19. Consistency in 3D

Author: Shapiro, Marc, Saeida Ardekani, Masoud, Petri, Gustavo, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Samsung Research America [San José], Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche en Informatique et Automatique (Inria)
Subjects: D.1.3 Concurrent programming, Structural invariants, D.2.4 Vérification de programme et de logiciel, Correctness of distributed systems, E.1 Structures de données réparties, Invariants de structurels, C.2.4 Distributed databases, Caractère correct de système réparti, Données répliquées, Modèles de cohérence, Replicated data, E.1 Distributed data structures, [INFO]Computer Science [cs], Consistency models, D.2.4 Software/Program Verification, C.2.4 Bases de données réparties, D.1.3 Programmation parallèle
Abstract: Comparisons of different consistency models often try to place them in a linear strong-to-weak order. However this view is clearly inadequate, since it is well known, for instance, that Snapshot Isolation and Serialisability are incomparable. In the interest of a better understanding, we propose a new classification, along three dimensions, related to: a total order of writes, a causal order of reads, and transactional composition of multiple operations. A model may be stronger than another on one dimension and weaker on another. We believe that this new classification scheme is both scientifically sound and has good explicative value. The current paper presents the three-dimensional design space intuitively.; Les comparaisons entre modèles de la cohérence tentent souvent de les classer dans un ordre linéaire, de faible à forte. Cette vue est clairement inadéquate, puisque il est bien connu que, par exemple, les modèles Snapshot Isolation et Serialisability sont incomparables. Dans l'intérêt d'une meilleure compréhension du domaine, nous proposons une nouvelle classification, en trois dimensions~: les garanties liées à un ordre total des écritures~; celles liées à un ordre causal des lectures~; et celles liées à la composition transactionelle d'opérations multiples. Un modèle peut être plus fort qu'un autre dans une dimension, et moins dans une autre. Nous pensons que ce nouveau schéma de classification, à la fois est scientifiquement valide, et a une bonne valeur explicative. Le présent rapport présente l'espace de conception en trois dimensions de façon intuitive.
Published: 2016

20. Consistency in 3D

Author: Shapiro, Marc, Saeida Ardekani, Masoud, Petri, Gustavo, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Samsung Research America [San José], Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche en Informatique et Automatique (Inria)
Subjects: D.1.3 Concurrent programming, Structural invariants, D.2.4 Vérification de programme et de logiciel, Correctness of distributed systems, E.1 Structures de données réparties, Invariants de structurels, C.2.4 Distributed databases, Caractère correct de système réparti, Données répliquées, Modèles de cohérence, Replicated data, E.1 Distributed data structures, [INFO]Computer Science [cs], Consistency models, D.2.4 Software/Program Verification, C.2.4 Bases de données réparties, D.1.3 Programmation parallèle
Abstract: Comparisons of different consistency models often try to place them in a linear strong-to-weak order. However this view is clearly inadequate, since it is well known, for instance, that Snapshot Isolation and Serialisability are incomparable. In the interest of a better understanding, we propose a new classification, along three dimensions, related to: a total order of writes, a causal order of reads, and transactional composition of multiple operations. A model may be stronger than another on one dimension and weaker on another. We believe that this new classification scheme is both scientifically sound and has good explicative value. The current paper presents the three-dimensional design space intuitively.; Les comparaisons entre modèles de la cohérence tentent souvent de les classer dans un ordre linéaire, de faible à forte. Cette vue est clairement inadéquate, puisque il est bien connu que, par exemple, les modèles Snapshot Isolation et Serialisability sont incomparables. Dans l'intérêt d'une meilleure compréhension du domaine, nous proposons une nouvelle classification, en trois dimensions~: les garanties liées à un ordre total des écritures~; celles liées à un ordre causal des lectures~; et celles liées à la composition transactionelle d'opérations multiples. Un modèle peut être plus fort qu'un autre dans une dimension, et moins dans une autre. Nous pensons que ce nouveau schéma de classification, à la fois est scientifiquement valide, et a une bonne valeur explicative. Le présent rapport présente l'espace de conception en trois dimensions de façon intuitive.
Published: 2016

21. Consistency in 3D

Author: Shapiro, Marc, Saeida Ardekani, Masoud, Petri, Gustavo, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Samsung Research America [San José], Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche en Informatique et Automatique (Inria)
Subjects: D.1.3 Concurrent programming, Structural invariants, D.2.4 Vérification de programme et de logiciel, Correctness of distributed systems, E.1 Structures de données réparties, Invariants de structurels, C.2.4 Distributed databases, Caractère correct de système réparti, Données répliquées, Modèles de cohérence, Replicated data, E.1 Distributed data structures, [INFO]Computer Science [cs], Consistency models, D.2.4 Software/Program Verification, C.2.4 Bases de données réparties, D.1.3 Programmation parallèle
Abstract: Comparisons of different consistency models often try to place them in a linear strong-to-weak order. However this view is clearly inadequate, since it is well known, for instance, that Snapshot Isolation and Serialisability are incomparable. In the interest of a better understanding, we propose a new classification, along three dimensions, related to: a total order of writes, a causal order of reads, and transactional composition of multiple operations. A model may be stronger than another on one dimension and weaker on another. We believe that this new classification scheme is both scientifically sound and has good explicative value. The current paper presents the three-dimensional design space intuitively.; Les comparaisons entre modèles de la cohérence tentent souvent de les classer dans un ordre linéaire, de faible à forte. Cette vue est clairement inadéquate, puisque il est bien connu que, par exemple, les modèles Snapshot Isolation et Serialisability sont incomparables. Dans l'intérêt d'une meilleure compréhension du domaine, nous proposons une nouvelle classification, en trois dimensions~: les garanties liées à un ordre total des écritures~; celles liées à un ordre causal des lectures~; et celles liées à la composition transactionelle d'opérations multiples. Un modèle peut être plus fort qu'un autre dans une dimension, et moins dans une autre. Nous pensons que ce nouveau schéma de classification, à la fois est scientifiquement valide, et a une bonne valeur explicative. Le présent rapport présente l'espace de conception en trois dimensions de façon intuitive.
Published: 2016

22. Consistency in 3D

Author: Shapiro, Marc, Saeida Ardekani, Masoud, Petri, Gustavo, Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Samsung Research America [San José], Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Institut National de la Recherche en Informatique et Automatique (Inria)
Subjects: D.1.3 Concurrent programming, Structural invariants, D.2.4 Vérification de programme et de logiciel, Correctness of distributed systems, E.1 Structures de données réparties, Invariants de structurels, C.2.4 Distributed databases, Caractère correct de système réparti, Données répliquées, Modèles de cohérence, Replicated data, E.1 Distributed data structures, [INFO]Computer Science [cs], Consistency models, D.2.4 Software/Program Verification, C.2.4 Bases de données réparties, D.1.3 Programmation parallèle
Abstract: Comparisons of different consistency models often try to place them in a linear strong-to-weak order. However this view is clearly inadequate, since it is well known, for instance, that Snapshot Isolation and Serialisability are incomparable. In the interest of a better understanding, we propose a new classification, along three dimensions, related to: a total order of writes, a causal order of reads, and transactional composition of multiple operations. A model may be stronger than another on one dimension and weaker on another. We believe that this new classification scheme is both scientifically sound and has good explicative value. The current paper presents the three-dimensional design space intuitively.; Les comparaisons entre modèles de la cohérence tentent souvent de les classer dans un ordre linéaire, de faible à forte. Cette vue est clairement inadéquate, puisque il est bien connu que, par exemple, les modèles Snapshot Isolation et Serialisability sont incomparables. Dans l'intérêt d'une meilleure compréhension du domaine, nous proposons une nouvelle classification, en trois dimensions~: les garanties liées à un ordre total des écritures~; celles liées à un ordre causal des lectures~; et celles liées à la composition transactionelle d'opérations multiples. Un modèle peut être plus fort qu'un autre dans une dimension, et moins dans une autre. Nous pensons que ce nouveau schéma de classification, à la fois est scientifiquement valide, et a une bonne valeur explicative. Le présent rapport présente l'espace de conception en trois dimensions de façon intuitive.
Published: 2016

23. Inference in OSNs via Lightweight Partial Crawls

Author: Bruno Ribeiro, Jithin K. Sreedharan, Konstantin Avrachenkov, Models for the performance analysis and the control of networks (MAESTRO), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [Purdue], Purdue University [West Lafayette], Bell Labs Inria Joint Lab, and ADR Network Science
Subjects: Theoretical computer science, Computer science, Computer Networks and Communications, Bayesian inference, Context (language use), 02 engineering and technology, Crawling, computer.software_genre, 01 natural sciences, Social network analysis, 010104 statistics & probability, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Graph sampling, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Random walk on graphs, 0101 mathematics, Random graph, Application programming interface, Social network, business.industry, Node (networking), Social network analysis (criminology), 020206 networking & telecommunications, Distributed algorithm, Hardware and Architecture, Data mining, Web crawler, business, computer, Software
Abstract: International audience; Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (SNA) but often crawling an OSN network via its Application Programming Interface (API) is the only way to gather data from a third party. To date, these partial API crawls are the majority of public datasets and the synonym of lack of statistical guarantees in incomplete-data comparisons, severely limiting SNA research progress. Using regenerative properties of the random walks, we propose estimation techniques based on short crawls that have proven statistical guarantees. Moreover, our short crawls can be implemented in massively distributed algorithms. We also provide an adaptive crawler that makes our method parameter-free, significantly improving our statistical guarantees. We then derive the Bayesian approximation of the posterior of the estimates, and in addition, obtain an estima-tor for the expected value of node and edge statistics in an equivalent configuration model or Chung-Lu random graph model of the given network (where nodes are connected randomly) and use it as a basis for testing null hypotheses. The theoretical results are supported with simulations on a variety of real-world networks.
Published: 2016
Full Text: View/download PDF

24. Large Scale Terrain Generation from Tectonic Uplift and Fluvial Erosion

Author: Adrien Peytavie, Marie-Paule Cani, Jean Braun, Eric Galin, Eric Guérin, Guillaume Cordonnier, Bedrich Benes, Intuitive Modeling and Animation for Interactive Graphics & Narrative Environments (IMAGINE ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institut des Sciences de la Terre (ISTerre), Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Institut national des sciences de l'Univers (INSU - CNRS)-Institut de recherche pour le développement [IRD] : UR219-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Department of Computer Science [Purdue], Purdue University [West Lafayette], Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), European Project: 291184,EC:FP7:ERC,ERC-2011-ADG_20110209,EXPRESSIVE(2012), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)
Subjects: geography, river incision model, geography.geographical_feature_category, Landform, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Fluvial, 020207 software engineering, Terrain, equation, 02 engineering and technology, 15. Life on land, Computer Graphics and Computer-Aided Design, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Tectonics, Tectonic uplift, parallel, evolution, 0202 electrical engineering, electronic engineering, information engineering, Erosion, 020201 artificial intelligence & image processing, Digital elevation model, Geomorphology, Stream power, Geology, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; At large scale, landscapes result from the combination of two major processes: tectonics which generate the main relief through crust uplift, and weather which accounts for erosion. This paper presents the first method in computer graphics that combines uplift and hydraulic erosion to generate visually plausible terrains. Given a user-painted uplift map, we generate a stream graph over the entire domain embedding elevation information and stream flow. Our approach relies on the stream power equation introduced in geology for hydraulic erosion. By combining crust uplift and stream power erosion we generate large realistic terrains at a low computational cost. Finally, we convert this graph into a digital elevation model by blending landform feature kernels whose parameters are derived from the information in the graph. Our method gives high-level control over the large scale dendritic structures of the resulting river networks, watersheds, and mountains ridges.
Published: 2016
Full Text: View/download PDF

25. Environmental Objects for Authoring Procedural Scenes

Author: Grosbellet, François, Peytavie, Adrien, Guérin, Eric, Galin, Eric, Mérillou, Stéphane, Benes, Bedrich, DMI (XLIM-DMI), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: Procedural modeling, aging and weathering, Modélisation procédurale, changement d'apparence, [INFO]Computer Science [cs], génération procédurale, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We propose a novel approach for authoring large scenes with automatic enhancement of objects to create geometric decoration details such as snow cover, icicles, fallen leaves, grass tufts or even trash. We introduce environmental objects that extend an input object geometry with a set of procedural effects that defines how the object reacts to the environment, and by a set of scalar fields that defines the influence of the object over of the environment. The user controls the scene by modifying environmental variables, such as temperature or humidity fields. The scene definition is hierarchical: objects can be grouped and their behaviours can be set at each level of the hierarchy. Our per object definition allows us to optimize and accelerate the effects computation, which also enables us to generate large scenes with many geometric details at a very high level of detail. In our implementation, a complex urban scene of 10 000 m², represented with details of less than 1 cm, can be locally modified and entirely regenerated in a few seconds.
Published: 2016
Full Text: View/download PDF

26. Parallelism in Matrix Computations

Author: Ahmed H. Sameh, Efstratios Gallopoulos, Bernard Philippe, Simulations and Algorithms on Grids for Environment (SAGE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Department of Computer Engineering and Informatics [Patras], University of Patras, CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), University of Patras [Patras], Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: Analysis of parallel algorithms, Numerical linear algebra, Matrix-free methods, Computer science, MathematicsofComputing_NUMERICALANALYSIS, 020206 networking & telecommunications, 010103 numerical & computational mathematics, 02 engineering and technology, computer.software_genre, 01 natural sciences, Toeplitz matrix, Algebra, Matrix (mathematics), Fundamental matrix (linear differential equation), Matrix function, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, computer, ComputingMilieux_MISCELLANEOUS, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Sparse matrix
Abstract: This book is primarily intended as a research monograph that could also be used in graduate courses for the design of parallel algorithms in matrix computations. It assumes general but not extensive knowledge of numerical linear algebra, parallel architectures, and parallel programming paradigms. The book consists of four parts: (I) Basics; (II) Dense and Special Matrix Computations; (III) Sparse Matrix Computations; and (IV) Matrix functions and characteristics. Part I deals with parallel programming paradigms and fundamental kernels, including reordering schemes for sparse matrices. Part II is devoted to dense matrix computations such as parallel algorithms for solving linear systems, linear least squares, the symmetric algebraic eigenvalue problem, and the singular-value decomposition. It also deals with the development of parallel algorithms for special linear systems such as banded, Vandermonde, Toeplitz, and block Toeplitz systems. Part III addresses sparse matrix computations: (a) the development of parallel iterative linear system solvers with emphasis on scalable preconditioners, (b) parallel schemes for obtaining a few of the extreme eigenpairs or those contained in a given interval in the spectrum of a standard or generalized symmetric eigenvalue problem, and (c) parallel methods for computing a few of the extreme singular triplets. Part IV focuses on the development of parallel algorithms for matrix functions and special characteristics such as the matrix pseudospectrum and the determinant. The book also reviews the theoretical and practical background necessary when designing these algorithms and includes an extensive bibliography that will be useful to researchers and students alike. The book brings together many existing algorithms for the fundamental matrix computations that have a proven track record of efficient implementation in terms of data locality and data transfer on state-of-the-art systems, as well as several algorithms that are presented for the first time, focusing on the opportunities for parallelism and algorithm robustness.
Published: 2016
Full Text: View/download PDF

27. Forty Years of Suffix Trees

Author: Apostolico, Alberto, Crochemore, Maxime, Farach-Colton, Martín, Galil, Zvi, Muthukrishnan, S., Department of Computer Science [Purdue], Purdue University [West Lafayette], Informatics, King‘s College London, Rutgers, The State University of New Jersey [New Brunswick] (RU), Rutgers University System (Rutgers), College of Computing (GATECH), Georgia Institute of Technology [Atlanta], and Google Inc.
Subjects: factor automaton, wavelet tree, fix tree, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], suffix tree, bi-tree, array, suffix, suffix automaton, pattern matching, dawg, suf, string searching, FM-index
Abstract: International audience; This paper reviews the first 40 years in the life of suffix trees, their many incarnations, and their applications. The paper is non-technical but assumes some familiarity with the structures and constructions discussed. It is not meant to be exhaustive. It is meant to be a tribute to a ubiquitous tool of string matching — the suffix tree and its variants — and one of the most persistent subjects of study in the theory of algorithms.
Published: 2016
Full Text: View/download PDF

28. Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls

Author: Avrachenkov, Konstantin, Ribeiro, Bruno, Sreedharan, Jithin K., Models for the performance analysis and the control of networks (MAESTRO), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [Purdue], Purdue University [West Lafayette], Inria Sophia Antipolis, and Purdue University
Subjects: Social network analysis, Graph sampling, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [PHYS.PHYS.PHYS-SOC-PH]Physics [physics]/Physics [physics]/Physics and Society [physics.soc-ph], Bayesian inference, Random walk on graphs, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
Abstract: Online social networks (OSN) contain extensive amount of information about the underlying society that is yet to be explored. One of the most feasible technique to fetch information from OSN, crawling through Application Programming Interface (API) requests, poses serious concerns over the the guarantees of the estimates. In this work, we focus on making reliable statistical inference with limited API crawls. Based on regenerative properties of the random walks, we propose an unbiased estimator for the aggregated sum of functions over edges and proved the connection between variance of the estimator and spectral gap. In order to facilitate Bayesian inference on the true value of the estimator, we derive the approximate posterior distribution of the estimate. Later the proposed ideas are validated with numerical experiments on inference problems in real-world networks.
Published: 2015

29. Tuning of Pectin Methylesterification : PECTIN METHYLESTERASE INHIBITOR 7 modulates the processive activity of co-expressed PECTIN METHYLESTERASE 3 in a pH-dependent manner

Author: Senechal, Fabien, L’Enfant, Mélanie, Domon, Jean-Marc, Rosiau, Emeline, CREPEAU, Marie-Jeanne, Surcouf, Ogier, Esquivel-Rodríguez, Juan, Marcelo, Paulo, Mareck, Alain, Guerineau, Francois, Kim, Hyung-Rae, MRAVEC, Jozef, Bonnin, Estelle, Jamet, Elisabeth, Kihara, Daisuke, Lerouge, Patrice, Ralet, Marie-Christine, Pelloux, Jérome, Rayon, Catherine, Biologie des Plantes et Innovation - UR UPJV 3900 (BIOPI), Université de Picardie Jules Verne (UPJV), Unité de recherche sur les Biopolymères, Interactions Assemblages (BIA), Institut National de la Recherche Agronomique (INRA), Laboratoire de Glycobiologie et Matrice Extracellulaire Végétale (Glyco-MEV), Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Normandie Université (NU), Department of Computer Science [Purdue], Purdue University [West Lafayette], Spectrométrie de Masse Biologique et Protéomique (USR3149 / FRE2032) (SMBP), Ecole Superieure de Physique et de Chimie Industrielles de la Ville de Paris (ESPCI Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Toyota Technological Institute at Chicago [Chicago] (TTIC), University of Copenhagen = Københavns Universitet (KU), Dynamique et Evolution des Parois cellulaires végétales, Laboratoire de Recherche en Sciences Végétales (LRSV), Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: pectin methylesterase inhibitor (PMEI), [SDV.BIO]Life Sciences [q-bio]/Biotechnology, homology modeling, food and beverages, [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], [SDV.BC.BC]Life Sciences [q-bio]/Cellular Biology/Subcellular Processes [q-bio.SC], microscale thermophoresis, [SDV.BV.PEP]Life Sciences [q-bio]/Vegetal Biology/Phytopathology and phytopharmacy, degree of blockiness, protein-protein interaction, [SDV.BV.AP]Life Sciences [q-bio]/Vegetal Biology/Plant breeding, [CHIM.POLY]Chemical Sciences/Polymers, gel diffusion assay, plant biochemistry, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], [SDV.BC.IC]Life Sciences [q-bio]/Cellular Biology/Cell Behavior [q-bio.CB], plant cell wall, pectin methylesterase (PME), [SDV.BBM.BC]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biochemistry [q-bio.BM], protein expression, [SDV.BDD.GAM]Life Sciences [q-bio]/Development Biology/Gametogenesis
Abstract: International audience; Background: PME and PMEI isoforms are co-expressed in Arabidopsis. Their biochemical interaction is yet to be characterized. Results: The processive activity of AtPME3 is regulated by AtPMEI7 in a pH-dependent manner in vitro. Conclusion: AtPMEI7 is a key component of the regulation of AtPME3 activity in planta. Significance: The tuning of AtPME3 activity by AtPMEI7 brings insights into the control of homogalacturonan methylesteri-fication in plant cell walls.
Published: 2015
Full Text: View/download PDF

30. Tuning of Pectin Methylesterification

Author: Senechal, Fabien, L 'enfant, Mélanie, Domon, Jean-Marc, Rosiau, Emeline, CREPEAU, Marie-Jeanne, Surcouf, Ogier, Esquivel-Rodríguez, Juan, Marcelo, Paulo, Mareck, Alain, Guerineau, Francois, Kim, Hyung-Rae, MRAVEC, Jozef, Bonnin, Estelle, Jamet, Elisabeth, Kihara, Daisuke, Lerouge, Patrice, Ralet, Marie-Christine, Pelloux, Jérome, Rayon, Catherine, Biologie des Plantes et Innovation - UR UPJV 3900 (BIOPI), Université de Picardie Jules Verne (UPJV)-Transfrontalière BioEcoAgro - UMR 1158 (BioEcoAgro), Université d'Artois (UA)-Université de Liège-Université de Picardie Jules Verne (UPJV)-Université du Littoral Côte d'Opale (ULCO)-Université de Lille-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-JUNIA (JUNIA), Université catholique de Lille (UCL)-Université catholique de Lille (UCL)-Université d'Artois (UA)-Université de Liège-Université du Littoral Côte d'Opale (ULCO)-Université de Lille-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-JUNIA (JUNIA), Université catholique de Lille (UCL)-Université catholique de Lille (UCL), Unité de recherche sur les Biopolymères, Interactions Assemblages (BIA), Institut National de la Recherche Agronomique (INRA), Laboratoire de Glycobiologie et Matrice Extracellulaire Végétale (Glyco-MEV), Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Normandie Université (NU), Department of Computer Science [Purdue], Purdue University [West Lafayette], Plateforme d’Ingénierie Cellulaire et Analyses des Protéines (ICAP) (ICAP), Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS), University of Copenhagen = Københavns Universitet (UCPH), Dynamique et Evolution des Parois cellulaires végétales, Laboratoire de Recherche en Sciences Végétales (LRSV), Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), NIGMS NIH HHS Grant ID : R01GM097528, ANR-09-BLAN-0007,GROWPEC(2009), ANR-12-BSV5-0001,GALAPAGOS,Production d'oligogalacturonides spécifiques par action des pectine méthylestérases. Une alternative en phytoprotection.(2012), Biologie des Plantes et Innovation (BIOPI), Université de Picardie Jules Verne (UPJV), Unité de Spectrométrie de Masse Biologique et Protéomique, ESPCI ParisTech-Centre National de la Recherche Scientifique (CNRS), Toyota Technological Institute at Chicago [Chicago] (TTIC), University of Copenhagen = Københavns Universitet (KU), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées
Subjects: [SDV.BIO]Life Sciences [q-bio]/Biotechnology, homology modeling, Arabidopsis, Plant Biology, [SDV.BC.BC]Life Sciences [q-bio]/Cellular Biology/Subcellular Processes [q-bio.SC], Substrate Specificity, protein-protein interaction, degree of blockiness, [SDV.BBM.GTP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN], parasitic diseases, [SDV.BC.IC]Life Sciences [q-bio]/Cellular Biology/Cell Behavior [q-bio.CB], plant cell wall, pectin methylesterase (PME), Enzyme Inhibitors, [SDV.BBM.BC]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biochemistry [q-bio.BM], protein expression, [SDV.BDD.GAM]Life Sciences [q-bio]/Development Biology/Gametogenesis, pectin methylesterase inhibitor (PMEI), Binding Sites, urogenital system, Arabidopsis Proteins, food and beverages, [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, [SDV.BBM.MN]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular Networks [q-bio.MN], Hydrogen-Ion Concentration, microscale thermophoresis, Hypocotyl, Recombinant Proteins, [SDV.BBM.BC]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM], [SDV.BV.PEP]Life Sciences [q-bio]/Vegetal Biology/Phytopathology and phytopharmacy, carbohydrates (lipids), Molecular Docking Simulation, [SDV.BV.AP]Life Sciences [q-bio]/Vegetal Biology/Plant breeding, [CHIM.POLY]Chemical Sciences/Polymers, gel diffusion assay, Multiprotein Complexes, plant biochemistry, Pectins, lipids (amino acids, peptides, and proteins), Carboxylic Ester Hydrolases
Abstract: International audience; Pectin methylesterases (PMEs) catalyze the demethylesterification of homogalacturonan domains of pectin in plant cell walls and are regulated by endogenous pectin methylesterase inhibitors (PMEIs). In Arabidopsis dark-grown hypocotyls, one PME (AtPME3) and one PMEI (AtPMEI7) were identified as potential interacting proteins. Using RT-quantitative PCR analysis and gene promoter::GUS fusions, we first showed that AtPME3 and AtPMEI7 genes had overlapping patterns of expression in etiolated hypocotyls. The two proteins were identified in hypocotyl cell wall extracts by proteomics. To investigate the potential interaction between AtPME3 and AtPMEI7, both proteins were expressed in a heterologous system and purified by affinity chromatography. The activity of recombinant AtPME3 was characterized on homogalacturonans (HGs) with distinct degrees/patterns of methylesterification. AtPME3 showed the highest activity at pH 7.5 on HG substrates with a degree of methylesterification between 60 and 80% and a random distribution of methyl esters. On the best HG substrate, AtPME3 generates long non-methylesterified stretches and leaves short highly methylesterified zones, indicating that it acts as a processive enzyme. The recombinant AtPMEI7 and AtPME3 interaction reduces the level of demethylesterification of the HG substrate but does not inhibit the processivity of the enzyme. These data suggest that the AtPME3·AtPMEI7 complex is not covalently linked and could, depending on the pH, be alternately formed and dissociated. Docking analysis indicated that the inhibition of AtPME3 could occur via the interaction of AtPMEI7 with a PME ligand-binding cleft structure. All of these data indicate that AtPME3 and AtPMEI7 could be partners involved in the fine tuning of HG methylesterification during plant development.
Published: 2015
Full Text: View/download PDF

31. Security-Aware Business Process as a Service by hiding provenance

Author: Salima Benbernou, Mehdi Bentounsi, Mikhail J. Atallah, Laboratoire d'Informatique Paris Descartes (LIPADE - EA 2517), Université Paris Descartes - Paris 5 (UPD5), Department of Computer Science [Purdue], Purdue University [West Lafayette], and CIFRE 1169-2010
Subjects: [INFO.INFO-WB] Computer Science [cs]/Web, Computer science, Business process, Cloud computing, 02 engineering and technology, BPaaS, Computer security, computer.software_genre, Outsourcing, Business process management, Business process discovery, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Process composition, business.industry, Artifact-centric business process model, Security by design, [INFO.INFO-WB]Computer Science [cs]/Web, Business process modeling, Secure by design, Hardware and Architecture, 020201 artificial intelligence & image processing, Process reuse, business, Law, computer, Software
Abstract: We adress in this paper the security issues that arise when outsourcing business processes in the BPaaS (Business Process as a Service). In particular when sharing and reusing process fragments coming from different organizations for faster and easier development of process-based applications (PBA). The goal is twofold, to preserve the process fragment provenance, i.e., the companies's business activities which provide the reused fragments in order to avoid the competition, and to guarantee the end-to-end availability of PBA to fragment's consumers. We formally define the problem, and offer an efficient anonymization-based protocol. Experiments have been conducted to show the effectiveness of the proposed solution. We address the security issues that arise when outsourcing business processes in the cloud as BPaaS (Business Process as a Service).We formally define the concept of sharing and reusing process fragments for faster and easier development of process-based applications.We provide an efficient anonymization-based protocol to preserve the process fragment provenance, and to guarantee the end-to-end availability of process-based applications.We evaluate the performance of the proposed approach on real datasets.
Published: 2015
Full Text: View/download PDF

32. Terrain Modeling from Feature Primitives

Author: Génevaux, Jean-David, Galin, Eric, Peytavie, Adrien, Guérin, Eric, Briquet, Cyril, Grosbellet, François, Benes, Bedrich, Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.6: Methodology and Techniques/I.3.6.2: Graphics data structures and data types, geometric modeling, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.6: Methodology and Techniques/I.3.6.3: Interaction techniques, natural phenomena, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling/I.3.5.2: Curve, surface, solid, and object representations, terrain modeling, procedural modeling, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We introduce a compact hierarchical procedural model that combines feature-based primitives to describe complex terrains with varying level of detail. Our model is inspired by skeletal implicit surfaces and defines the terrain elevation function by using a construction tree. Leaves represent terrain features and they are generic parameter-ized skeletal primitives such as mountains, ridges, valleys, rivers, lakes, or roads. Inner nodes combine the leaves and subtrees by carving, blending, or warping operators. The elevation of the terrain at a given point is evaluated by traversing the tree and by combining the contributions of the primitives. The definition of the tree leaves and operators guarantees that the resulting elevation function is Lipschitz which speeds up the sphere tracing used to render the terrain. Our model is compact and allows for the creation of large terrains with a high level of detail using a reduced set of primitives. We show the creation of different kinds of landscapes and demonstrate that our model allows to efficiently control the shape and distribution of landform features.
Published: 2015
Full Text: View/download PDF

33. Modélisation de terrains par primitives

Author: Génevaux, Jean-David, Grosbellet, François, Galin, Eric, Peytavie, Adrien, Guérin, Eric, Briquet, Cyril, Beneš, Bedřich, Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Synthèse et analyse d'images (XLIM-ASALI), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], and Génevaux, Jean-David
Subjects: [INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR], natural phenomena, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, procedural modelling, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, terrain modelling, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], implicit surface
Abstract: National audience; Nous proposons un modèle de terrain hiérarchique et compact permettant de représenter des scènes complexes. Ce modèle de représentation s'inspire des surfaces implicites à squelettes et définit une fonction d'élévation sous la forme d'un arbre de construction. Les feuilles sont des primitives décrivant des morceaux de terrains à différentes échelles (montagnes, fleuves, ...) et les noeuds internes sont des opérateurs de combinaison. L'élévation d'un point est calculée en traversant la structure d'arbre et en combinant les contributions de chaque primitive. La définition des feuilles et des opérateurs garantit que la fonction d'élévation résultante est Lipschitzienne, ce qui permet d'accélérer les calculs de visualisation en utilisant un algorithme de sphere tracing. Mots Clés : modélisation de terrains, phénomènes naturels, modélisation procédurale, surface implicite We propose a compact hierarchical procedural model that combines feature-based primitives to create complex continuous terrains. Our model is inspired by skeletal implicit surfaces and defines the terrain elevation by using a construction tree whose leaves are primitives describing terrain fragments, and whose inner nodes include operations that combine its sub-trees. The elevation of a point is evaluated by traversing the tree and by combining the contributions of each primitive. The definition of both leaves and operators guarantees that the resulting elevation function is Lipschitz which enables us to speed up sphere tracing and surface adaptive tesselation algorithms.
Published: 2014

34. Atomicity Refinement for Verified Compilation

Author: Jan Vitek, Vincent Laporte, Gustavo Petri, David Pichardie, Suresh Jagannathan, Department of Computer Science [Purdue], Purdue University [West Lafayette], Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)
Subjects: Mechanized proof assistant (Coq), Correctness, Java, Computer science, Concurrency, Compiler, Thread (computing), 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, Abstraction (linguistics), computer.programming_language, Atomicity, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Computer Graphics and Computer-Aided Design, Memory management, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Memory model, computer, Software, Garbage collection, Memory semantics
Abstract: International audience; We consider the verified compilation of high-level managed languages like Java or C# whose intermediate representations provide support for shared-memory synchronization and automatic memory management. Our development is framed in the context of the Total Store Order relaxed memory model. Ensuring com-plier correctness is challenging because high-level actions are translated into sequences of non-atomic ac-tions with compiler-injected snippets of racy code; the behavior of this code depends not only on the actions of other threads, but also on out-of-order executions performed by the processor. A naïve proof of correctness would require reasoning over all possible thread interleavings. In this paper we propose a refinement-based proof methodology that precisely relates concurrent code expressed at different abstraction levels, cognizant throughout of the relaxed memory semantics of the underlying processor. Our technique allows the compiler writer to reason compositionally about the atomicity of low-level concurrent code used to implement man-aged services. We illustrate our approach with examples taken from the verification of a concurrent garbage collector.
Published: 2014

35. Changements d’apparences au cours des saisons

Author: Grosbellet, François, Peytavie, Adrien, Guérin, Eric, Galin, Eric, Mérillou, Stéphane, Benes, Bedrich, DMI (XLIM-DMI), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Department of Computer Science [Purdue], Purdue University [West Lafayette], and Merillou, Stephane
Subjects: [INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR], [INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR]
Abstract: National audience
Published: 2013

36. CANS 2013

Author: Abdalla, Michel, Nita-Rotaru, Cristina, Dahab, Ricardo, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Institute of Computing [Campinas] (IC), Universidade Estadual de Campinas = University of Campinas (UNICAMP), Michel Abdalla and Cristina Nita-Rotaru and Ricardo Dahab, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Institute of Computing [Campinas] (UNICAMP), Universidade Estadual de Campinas (UNICAMP), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; This book constitutes the refereed proceedings of the 12th International Conference on Cryptology and Network Security, CANS 2013, held in Paraty, Brazil, in November 2013. The 18 revised full papers presented together with four invited talks were carefully reviewed and selected from 57 submissions. The papers are organized in topical sections on cryptanalysis, zero-knowledge protocols, distributed protocols, network security and applications, advanced cryptographic primitives, and verifiable computation.
Published: 2013
Full Text: View/download PDF

37. Community-wide evaluation of methods for predicting the effect of mutations on protein-protein interactions

Author: Moretti, Rocco, Fleishman, Sarel J, Agius, Rudi, Torchala, Mieczyslaw, Bates, Paul A., Kastritis, Panagiotis L, Rodrigues, João P. G. L. M., Trellet, Mikael, Bonvin, Alexandre M. J. J., Cui, Meng, Rooman, Marianne, Gillis, Dimitri, Dehouck, Yves, Moal, Iain, Romero-Durana, Miguel, Pérez-Cano, Laura, Pallara, Chiara, Jimenez, Brian, Fernández-Recio, Juan, Flores, Samuel C, Pacella, Michael, Praneeth Kilambi, Krishna, Gray, Jeffrey J, Popov, Petr, Grudinin, Sergei, Esquivel-Rodríguez, Juan, Kihara, Daisuke, Zhao, Nan, Korkin, Dmitry, Zhu, Xiaolei, Demerdash, Omar N A, Mitchell, Julie, Kanamori, Eiji, Tsuchiya, Yuko, Nakamura, Haruki, Lee, Hasup, Park, Hahnbeom, Seok, Chaok, Sarmiento, Jamica, Liang, Shide, Teraguchi, Shusuke, Standley, Daron M, Shimoyama, Hiromitsu, Terashi, Genki, Takeda-Shitaka, Mayuko, Iwadate, Mitsuo, Umeyama, Hideaki, Beglov, Dmitri, Hall, David R, Kozakov, Dima, Vajda, Sandor, Pierce, Brian G, Hwang, Howook, Vreven, Thom, Weng, Zhiping, Huang, Yangyu, Li, Haotian, Yang, Xiufeng, Ji, Xiaofeng, Liu, Shiyong, Xiao, Yi, Zacharias, Martin, Qin, Sanbo, Zhou, Huan-Xiang, Huang, Sheng-You, Zou, Xiaoqin, Velankar, Sameer, Janin, Joel, Wodak, Shoshana J, Baker, David, Department of Biochemistry [Washington ], University of Washington [Seattle], Molecular Carcinogenesis [Sutton], Institute of cancer research, Weizmann Institute of Science [Rehovot, Israël], Biomolecular Modelling laboratory [London], Cancer Research UK London Research Institute, Bijvoet Center of Biomolecular Research [Utrecht], Utrecht University [Utrecht], Virginia Commonwealth University (VCU), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Université libre de Bruxelles (ULB), Unite de Bioinformatique genomique et structurale (3BIO-BIO-INFO), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), Department of Cell and Molecular Biology [Uppsala], Uppsala University, Johns Hopkins University (JHU), Algorithms for Modeling and Simulation of Nanosystems (NANO-D), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann (LJK), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], University of Missouri [Columbia] (Mizzou), University of Missouri System, Department of Mathematics [Madison], University of Wisconsin-Madison, Japan Biological Informatics Consortium [Tokyo], Ochanomizu University, Osaka University [Osaka], Seoul National University [Seoul] (SNU), Kitasato University, Chuo University (Chuo University), Department of Biomedical Engineering [Boston], Boston University [Boston] (BU), University of Massachusetts Medical School [Worcester] (UMASS), University of Massachusetts System (UMASS), Huazhong University of Science and Technology [Wuhan] (HUST), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Florida State University [Tallahassee] (FSU), European Bioinformatics Institute [Hinxton] (EMBL-EBI), EMBL Heidelberg, Institut de biochimie et biophysique moléculaire et cellulaire (IBBMC), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), University of Toronto, and The Hospital for sick children [Toronto] (SickKids)
Subjects: binding, deep mutational scanning, Mutation, Protein Interaction Mapping, yeast display, hemagglutinin, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Databases, Protein, CAPRI, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Algorithms, Article, Protein Binding
Abstract: International audience; Community-wide blind prediction experiments such as CAPRI and CASP provide an objective measure of the current state of predictive methodology. Here we describe a community-wide assessment of methods to predict the effects of mutations on protein-protein interactions. Twenty-two groups predicted the effects of comprehensive saturation mutagenesis for two designed influenza hemagglutinin binders and the results were compared with experimental yeast display enrichment data obtained using deep sequencing. The most successful methods explicitly considered the effects of mutation on monomer stability in addition to binding affinity, carried out explicit side-chain sampling and backbone relaxation, evaluated packing, electrostatic, and solvation effects, and correctly identified around a third of the beneficial mutations. Much room for improvement remains for even the best techniques, and large-scale fitness landscapes should continue to provide an excellent test bed for continued evaluation of both existing and new prediction methodologies.
Published: 2013
Full Text: View/download PDF

38. Classification of Markov Sources Through Joint String Complexity: Theory and Experiments

Author: Dimitris Milioris, Wojciech Szpankowski, Philippe Jacquet, Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, High performance communication (HIPERCOM), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), École polytechnique (X), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: Discrete mathematics, Average-case complexity, TheoryofComputation_MISCELLANEOUS, String (computer science), 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Descriptive complexity theory, 01 natural sciences, symbols.namesake, High Energy Physics::Theory, 010201 computation theory & mathematics, Markov algorithm, 0202 electrical engineering, electronic engineering, information engineering, symbols, Worst-case complexity, Communication complexity, Time complexity, Algorithm, Quantum complexity theory, Mathematics
Abstract: International audience; We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.
Published: 2013

39. Plan B: A Buffered Memory Model for Java

Author: Lei Zhao, Delphine Demange, Suresh Jagannathan, Jan Vitek, Vincent Laporte, David Pichardie, Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Department of Computer Science [Purdue], Purdue University [West Lafayette], Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: Java, Computer science, Java Memory Model, Programming language, strictfp, Concurrency, [SCCO.COMP]Cognitive science/Computer science, Generics in Java, computer.software_genre, Java concurrency, Computer Graphics and Computer-Aided Design, Bytecode, Real time Java, Virtual machine, Compiler, Memory model, computer, Java annotation, Implementation, Software, Java Modeling Language, computer.programming_language
Abstract: International audience; Recent advances in verification have made it possible to envision trusted implementations of real-world languages. Java with its type-safety and fully specified semantics would appear to be an ideal candidate; yet, the complexity of the translation steps used in production virtual machines have made it a challenging target for verifying compiler technology. One of Java's key innovations, its memory model, poses significant obstacles to such an endeavor. The Java Memory Model is an ambitious attempt at specifying the behavior of multithreaded programs in a portable, hardware agnostic, way. While experts have an intuitive grasp of the properties that the model should enjoy, the specification is complex and not well-suited for integration within a verifying compiler infrastructure. Moreover, the specification is given in an axiomatic style that is distant from the intuitive reordering-based reasonings traditionally used to justify or rule out behaviors, and ill suited to the kind of operational reasoning one would expect to employ in a compiler. This paper takes a step back, and introduces a Buffered Memory Model (BMM) for Java. We choose a pragmatic point in the design space sacrificing generality in favor of a model that is fully characterized in terms of the reorderings it allows, amenable to formal reasoning, and which can be efficiently applied to a specific hardware family, namely x86 multiprocessors. Although the BMM restricts the reorderings compilers are allowed to perform, it serves as the key enabling device to achieving a verification pathway from bytecode to machine instructions. Despite its restrictions, we show that it is backwards compatible with the Java Memory Model and that it does not cripple performance on TSO architectures.
Published: 2013

40. Privacy-Preserving Business Process Outsourcing

Author: Mikhail J. Atallah, Mehdi Bentounsi, Salima Benbernou, Laboratoire d'Informatique Paris Descartes (LIPADE - EA 2517), Université Paris Descartes - Paris 5 (UPD5), Department of Computer Science [Purdue], Purdue University [West Lafayette], and CIFRE 2010/1169
Subjects: Information privacy, Process management, Privacy-Preserving, [INFO.INFO-WB] Computer Science [cs]/Web, Computer science, business.industry, Process (engineering), Data_MISCELLANEOUS, [INFO.INFO-WB]Computer Science [cs]/Web, Cloud computing, BPaaS, Computer security, computer.software_genre, Outsourcing, Privacy preserving, Business process discovery, Cost reduction, Web service, business, computer
Abstract: International audience; Many cloud providers offer on demand applications as Business Process as a Service (BPaaS), allowing companies to outsource their processes. For cost saving, some process fragments can be reused on the cloud regardless of privacy risks. In this paper, we propose an anonymization-based approach to preserve client business activity while sharing process fragments between organizations on the cloud.
Published: 2012
Full Text: View/download PDF

41. Component-Oriented Development for Real-Time Java

Author: Ales Plsek, Michal Malohlava, Frédéric Loiret, Department of Computer Science [Purdue], Purdue University [West Lafayette], Adaptive Distributed Applications and Middleware (ADAM), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), Distributed Systems Research Group (DSRG), Charles University [Prague] (CU), Higuera-Toledano, M. Teresa, Wellings, and Andy J.
Subjects: Architecture description language, Java, Computer science, Process (engineering), Programming language, media_common.quotation_subject, 020206 networking & telecommunications, 020207 software engineering, 02 engineering and technology, Systems modeling, computer.software_genre, Programming style, Real time Java, 0202 electrical engineering, electronic engineering, information engineering, Programming paradigm, computer, Java annotation, computer.programming_language, media_common
Abstract: International audience; The Real-Time Specification for Java (RTSJ) offers developers an attractive platform for development of software that is composed of variously stringent real-time and non real-time tasks. However, the RTSJ introduces a programming model involving several non-intuitive rules and restrictions which make systems modeling and development a complex and error-prone task. In this chapter we introduce an advanced software engineering technology that allows developers to address these challenges - component-oriented development. In the first part, we present the general concepts and identify the key benefits of this technology. We further show one of the possible approaches on how to embrace this technology when mitigating the complexities of RTSJ development - the Hulotte framework. The framework provides a continuum between the component-oriented design and implementation process of RTSJ systems. The RTSJ concepts are treated as first-class entities which enables the modeling and automatized preparation of their implementation by em- ploying code-generation techniques. We conclude this chapter with an extensive case study comparing object-oriented and component-oriented implementation of the Collision Detector Benchmark. Our empirical evaluation shows that the performance overhead of the framework is minimal in comparison to manually written object-oriented applications without imposing any restrictions on the programming style.
Published: 2012

42. A New Binomial Recurrence Arising in a Graphical Compression Algorithm

Author: Wojciech Szpankowski, Charles Knessl, Yongwook Choi, J. Craig Venter Institute, Department of Mathematics, Statistics and Computer Science [Chicago] (UIC), University of Illinois [Chicago] (UIC), University of Illinois System-University of Illinois System, Department of Computer Science [Purdue], Purdue University [West Lafayette], Broutin, Nicolas and Devroye, and Luc
Subjects: General Computer Science, Binomial (polynomial), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Theoretical Computer Science, Combinatorics, Integer, Algorithmics, Trie, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, graph compression, poissonization, Mellin transform, Mathematics, Discrete mathematics, 16. Peace & justice, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Digital trees, Tree (data structure), [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], Ball (bearing), Node (circuits)
Abstract: In a recently proposed graphical compression algorithm by Choi and Szpankowski (2009), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability $p$) or the right subtree (with probability 1-$p$). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer $d$ is given, and at level $d$ or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after $n+d$ steps). Observe that when $d=∞$ the above tree can be modeled as a $\textit{trie}$ that stores $n$ independent sequences generated by a memoryless source with parameter $p$. Therefore, we coin the name $(n,d)$-tries for the tree just described, and to which we often refer simply as $d$-tries. Parameters of such a tree (e.g., path length, depth, size) are described by an interesting two-dimensional recurrence (in terms of $n$ and $d$) that – to the best of our knowledge – was not analyzed before. We study it, and show how much parameters of such a $(n,d)$-trie differ from the corresponding parameters of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.
Published: 2012

43. New analysis of the asymptotic behavior of the Lempel-Ziv compression algorithm

Author: Jacquet, Philippe, Wojciech, Szpankowski, High performance communication (HIPERCOM), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: digital search tree, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], renewal processes, generating functions, depoissonization, data compression
Abstract: We give a new analysis and proof of the Normal limiting distribution of the number of phrases in the 1978 Lempel-Ziv compression algorithm on random sequences built from a memoriless source. This work is a follow-up of our last paper on this subject in 1995. The analysis stands on the asymptotic behavior of a DST obtained by the insertion of random sequences. Our proofs are augmented of new results on moment convergence, moderate and large deviations, redundancy analysis.
Published: 2010

44. Counting Markov Types

Author: Jacquet, Philippe, Knessl, Charles, Szpankowski, Wojciech, High performance communication (HIPERCOM), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics, Statistics and Computer Science [Chicago] (UIC), University of Illinois [Chicago] (UIC), University of Illinois System-University of Illinois System, Department of Computer Science [Purdue], Purdue University [West Lafayette], Drmota, Michael and Gittenberger, and Bernhard
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Theoretical Computer Science, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], saddle point method, linear diophantine equations, Discrete Mathematics and Combinatorics, Markov types, integer matrices, multidimensional generating functions
Abstract: The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so called $\textit{balanced frequency matrix}$ that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length $n$ over an alphabet of size $m$. This turns out to coincide with the number of the balanced frequency matrices as well as with the number of special $\textit{linear diophantine equations}$, and also balanced directed multigraphs. For fixed $m$ we prove that the number of Markov types is asymptotically equal to $d(m) \frac{n^{m^{2-m}}}{(m^2-m)!}$, where $d(m)$ is a constant for which we give an integral representation. For $m \to \infty$ we conclude that asymptotically the number of types is equivalent to $\frac{\sqrt{2}m^{3m/2} e^{m^2}}{m^{2m^2} 2^m \pi^{m/2}} n^{m^2-m}$ provided that $m=o(n^{1/4})$ (however, our techniques work for $m=o(\sqrt{n})$). These findings are derived by analytical techniques ranging from multidimensional generating functions to the saddle point method.
Published: 2010
Full Text: View/download PDF

45. Dagstuhl Seminar 13142 on Programming Models for Ubiquitous Parallelism

Author: Wong, David Chi-Leung, Cohen, Albert, Garzarán, María J., Lengauer, Christian, Midkiff, Samuel P., Parallélisme de Kahn Synchrone (Parkas ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [UIUC] (UIUC), University of Illinois at Urbana-Champaign [Urbana], University of Illinois System-University of Illinois System, Department of Informatics and Mathematics, Programming Group (FIM), University of Passau, Department of Computer Science [Purdue], Purdue University [West Lafayette], David Chi-Leung Wong and Albert Cohen and Mar\'ıa J. Garzarán and Christian Lengauer and Samuel P. Midkiff, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract: International audience; no abstract
Published: 2007

46. On the Ehrenfeucht-Mycielski Balance Conjecture

Author: John C. Kieffer, Wojciech Szpankowski, Department of Electrical and Computer Engineering [Minneapolis] (ECE), University of Minnesota [Twin Cities] (UMN), University of Minnesota System-University of Minnesota System, Department of Computer Science [Purdue], Purdue University [West Lafayette], and Jacquet, Philippe
Subjects: Balance (metaphysics), Sequence, Conjecture, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Pseudorandom binary sequence, Substring, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, Limit point, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Ehrenfeucht-Mycielski sequence, Discrete Mathematics and Combinatorics, Interval (graph theory), Tree (set theory), Mathematics
Abstract: In 1992, A. Ehrenfeucht and J. Mycielski defined a seemingly pseudorandom binary sequence which has since been termed the EM-sequence. The balance conjecture for the EM-sequence, still open, is the conjecture that the sequence of EM-sequence initial segment averages converges to $1/2$. In this paper, we do not prove the balance conjecture but we do make some progress concerning it, namely, we prove that every limit point of the aforementioned sequence of averages lies in the interval $[1/4,3/4]$, improving the best previous result that every such limit point belongs to the interval $[0.11,0.89]$. Our approach is novel and exploits an analysis of the growth behavior as $n \to \infty$ of the rooted tree formed by the binary strings appearing at least twice as substrings of the length $n$ initial segment of the EM-sequence.
Published: 2007

47. The 'Art' of Programming Gossip-based Systems

Author: Pascal Felber, Patrick Eugster, Fabrice Le Fessant, Department of Computer Science [Purdue], Purdue University [West Lafayette], Institut d'Informatique [Neuchâtel] (IIUN), Université de Neuchâtel (UNINE), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), Université de Rennes (UR)-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Theoretical computer science, Computer science, Interface (Java), business.industry, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, Probabilistic logic, Intrinsics, Gossip, Programming paradigm, General Earth and Planetary Sciences, Gossip protocol, Imperfect, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Completeness (statistics), business, General Environmental Science
Abstract: International audience; How does one best go about building actual gossip-based protocols? Trying to answer this question has brought us to address two preliminary questions, namely (1) what the in- trinsics of such systems or protocols are, and (2) what kind of applications would in the end be built on top of such protocols. We address the first question by arguing that gossip-based protocols are all built following one and the same pattern, and describing three building blocks which we claim are used to support this recurrent pattern—most notably a source of randomness. We validate these claims by devising simplified versions of well-known protocols, in a layered fashion, on top of a conceptual interface describing these basic services. The second question is addressed by ar- guing that gossip-based protocols exhibit some probabilistic or imperfect flavor (e.g., probabilistic or partial completion), and by proposing to take such probabilistic behavior into ac- count when devising interfaces for applications building on top of gossip-based protocols. We argue for inherent support for these probabilities in the programming model.
Published: 2007

48. Multicast tree structure and the power law

Author: Leonidas Georgiadis, Cedric Adjih, Philippe Jacquet, Wojciech Szpankowski, High performance communication (HIPERCOM), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Department of Electrical & Computer Engineering [Thessaloniki], Aristotle University of Thessaloniki, Laboratoire de Physique Corpusculaire - Clermont-Ferrand (LPC), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], and Purdue University [West Lafayette]
Subjects: Discrete mathematics, Spanning tree, Theoretical computer science, Degree (graph theory), Multicast, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, Library and Information Sciences, Network topology, 01 natural sciences, Computer Science Applications, Tree (data structure), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Tree structure, 010201 computation theory & mathematics, Reachability, Metric (mathematics), Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Information Theory, Information Systems, Mathematics
Abstract: In this paper, we investigate structural properties of multicast trees that give rise to the so-called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satisfies asymptotically R(n)/spl ap/cn/sup /spl phi//, 0
Published: 2006
Full Text: View/download PDF

49. Parallel computation of the singular value decomposition

Author: Berry, Michael, Mezher, Dany, Philippe, Bernard, Sameh, Ahmed, Department of Computer Science. University of Tennessee, Tennessee State University, Ecole supérieure d'ingénieurs de Beyrouth (ESIB), Université Saint-Joseph de Beyrouth (USJ), Algorithms Adapted to Intensive Numerical Computing (ALADIN), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-INRIA Rennes, Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [Purdue], Purdue University [West Lafayette], INRIA, Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-INRIA Rennes
Subjects: SUBSPACE ITERATION, JACOBI, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, SINGULAR VALUE DECOMPOSITION, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], MathematicsofComputing_NUMERICALANALYSIS, TRACE MINIMIZATION, LANCZOS, JACOBI-DAVIDSON, DAVIDSON, SVD, PARALLEL ALGORITHMS, PSEUDOSPECTRUM
Abstract: The goal of this survey is to give a view of the state-of-the-art of computing the Singular Value Decomposition (SVD) of dense and sparse matrices, with some emphasis on those schemes that are suitable for parallel computing platforms. For dense matrices, we survey those schemes that yield the complete decomposition, whereas for sparse matrices we survey schemes that yield only the extremal singular triplets. Special attention is devoted to the computation of the smallest singular values which are normally the most difficult to evaluate but which provide a measure of the distance to singularity of the matrix under consideration. Also, a parallel method for computing pseudospectra, which depends on computing the smallest singular values, is presented at the conclusion of the survey.
Published: 2003

50. Fast parallel Lyndon factorization and applications

Author: Apostolico, Alberto, Crochemore, Maxime, Crochemore, Maxime, Department of Computer Science [Purdue], Purdue University [West Lafayette], Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila] (DISIM), Università degli Studi dell'Aquila (UNIVAQ), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Information Engineering, Computer Science and Mathematics = Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila] (DISIM), Università degli Studi dell'Aquila = University of L'Aquila (UNIVAQ), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
Subjects: string matching, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], combinatorics on words, Lyndon words, parallel computation
Abstract: International audience; It is shown that the Lyndon decomposition of a word of n symbols can be computed by an n-processors CRCW PRAM in O(log n) time. Extensions of the basic algorithm convey, within the same time and processors bounds, efficient parallel solutions to problems such as finding the lexicographically minimum or maximum suffix for all prefixes of the input string, and finding the lexicographically least rotation of all prefixes of the input.
Published: 1995

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Database

52 results on '"Department of Computer Science [Purdue]"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources