Search

Showing total 16 results
Start Over Topic applied mathematics Publisher hal ccsd
16 results

1. Computing Riemann-Roch spaces via Puiseux expansions

Author

Simon Abelard, Elena Berardini, Alain Couvreur, Grégoire Lecerf, Thales SIX GTS France, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-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), This paper is part of a project of École polytechnique, that has received funding from the French 'Agence de l'innovation de défense'. Simon Abelard was partially funded by this grant, when he was hosted at École polytechnique, Institut Polytechnique de Paris (91120 Palaiseau, France), from October 2019 to the end of December 2020., École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and This paper is part of a project of École polytechnique, that has received funding from the French 'Agence de l'innovation de défense'. Simon Abelard was partially funded by this grant, when he was hosted at École polytechnique, Institut Polytechnique de Paris (91120 Palaiseau, France), from October 2019 to the end of December 2020. Elena Berardini has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.

Subjects
Statistics and Probability, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Numerical Analysis, Control and Optimization, Algebra and Number Theory, Applied Mathematics, General Mathematics, Algebraic curves, Complexity, Riemann-Roch spaces, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Puiseux expansions, Algorithms
Abstract

International audience; Computing large Riemann-Roch spaces for plane projective curves still constitutes a major algorithmic and practical challenge. Seminal applications concern the construction of arbitrarily large algebraic geometry error correcting codes over alphabets with bounded cardinality. Nowadays such codes are increasingly involved in new areas of computer science such as cryptographic protocols and "interactive oracle proofs". In this paper, we design a new probabilistic algorithm of Las Vegas type for computing Riemann-Roch spaces of smooth divisors, in characteristic zero, and with expected complexity exponent 2.373 (a feasible exponent for linear algebra) in terms of the input size.

Published
2021

2. CTET+: A Beyond-Birthday-Bound Secure Tweakable Enciphering Scheme Using a Single Pseudorandom Permutation

Author

Benoît Cogliati, Jordan Ethan, Virginie Lallemand, Byeonghak Lee, Jooyoung Lee, Marine Minier, Helmholtz Center for Information Security [Saarbrücken] (CISPA), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), 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)-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)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), Korea Advanced Institute of Science and Technology (KAIST), We would like to thank the anonymous reviewers for their valuable suggestions that helped improving the paper. This work was carried out in the framework of the French-German-Center for Cybersecurity, a collaboration of CISPA and LORIA and was partly supported by the french PIA project 'Lorraine Université d’Excellence', reference ANR-15 IDEX-04-LUE. Jooyoung was supported by Institute for Information & communications Technology Planning & Evaluation(IITP) grant funded by the Korea government(MSIT) (No.2019-0-01343, Regional strategic industry convergence security core talent training business). Part of this work was written while Benoît Cogliati was employed by the University of Luxembourg., 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 Algorithms, Computation, Image and Geometry (LORIA - ALGO), 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), and 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)

Subjects
TK7885-7895, Computer engineering. Computer hardware, Computational Mathematics, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Applied Mathematics, tweakable enciphering mode, beyond-birthday-bound security, SPN, Software, Computer Science Applications
Abstract

International audience; In this work, we propose a construction of 2-round tweakable substitution permutation networks using a single secret S-box. This construction is based on non-linear permutation layers using independent round keys, and achieves security beyond the birthday bound in the random permutation model. When instantiated with an n-bit block cipher with ωn-bit keys, the resulting tweakable block cipher, dubbed CTET+, can be viewed as a tweakable enciphering scheme that encrypts ωκ-bit messages for any integer ω ≥ 2 using 5n + κ-bit keys and n-bit tweaks, providing 2n/3-bit security. Compared to the 2-round non-linear SPN analyzed in [CDK+18], we both minimize it by requiring a single permutation, and weaken the requirements on the middle linear layer, allowing better performance. As a result, CTET+ becomes the first tweakable enciphering scheme that provides beyond-birthday-bound security using a single permutation, while its efficiency is still comparable to existing schemes including AES-XTS, EME, XCB and TET. Furthermore, we propose a new tweakable enciphering scheme, dubbed AES6-CTET+, which is an actual instantiation of CTET+ using a reduced round AES block cipher as the underlying secret S-box. Extensive cryptanalysis of this algorithm allows us to claim 127 bits of security.Such tweakable enciphering schemes with huge block sizes become desirable in the context of disk encryption, since processing a whole sector as a single block significantly worsens the granularity for attackers when compared to, for example, AES-XTS, which treats every 16-byte block on the disk independently. Besides, as a huge amount of data is being stored and encrypted at rest under many different keys in clouds, beyond-birthday-bound security will most likely become necessary in the short term.

Published
2021

3. Constrained overdamped Langevin dynamics for symmetric multimarginal optimal transportation

Author

Aurélien Alfonsi, Rafaël Coyaud, Virginie Ehrlacher, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Mathematical Risk Handling (MATHRISK), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), MATHematics for MatERIALS (MATHERIALS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC), The Labex Bézout is acknowledged for funding the PhD thesis of Rafaël Coyaud. Aurélien Alfonsi benefited from the support of the 'Chaire Risques Financiers', Fondation du Risque. We are very grateful to Gero Friesecke, Daniela Vögler, Tony Lelièvre, Gabriel Stoltz and Pierre Monmarché for stimulating discussions, as well as Mathieu Lewin for precious comments on the paper. This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme – Grant Agreement n◦ 810367., European Project: 810367,EMC2(2019), and École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris

Subjects
Applied Mathematics, Modeling and Simulation, FOS: Mathematics, Mathematics - Numerical Analysis, Numerical Analysis (math.NA), [MATH]Mathematics [math]
Abstract

The Strictly Correlated Electrons (SCE) limit of the Levy–Lieb functional in Density Functional Theory (DFT) gives rise to a symmetric multi-marginal optimal transport problem with Coulomb cost, where the number of marginal laws is equal to the number of electrons in the system, which can be very large in relevant applications. In this work, we design a numerical method, built upon constrained overdamped Langevin processes to solve Moment Constrained Optimal Transport (MCOT) relaxations (introduced in [A. Alfonsi, R. Coyaud, V. Ehrlacher and D. Lombardi, Approximation of optimal transport problems with marginal moments constraints, Math. Comp. 90 (2021) 689–737; C. Villani, Optimal Transport: Old and New (Springer Science & Business Media, 2008)]) of symmetric multi-marginal optimal transport problems with Coulomb cost. Some minimizers of such relaxations can be written as discrete measures charging a low number of points belonging to a space whose dimension, in the symmetrical case, scales linearly with the number of marginal laws. We leverage the sparsity of those minimizers in the design of the numerical method and prove that there is no strict local minimizer to the resulting problem. We illustrate the performance of the proposed method by numerical examples which solves MCOT relaxations of 3D systems with up to 100 electrons.

Published
2021

4. The DGDD Method for Reduced-Order Modeling of Conservation Laws

Author

Angelo Iollo, Charbel Farhat, Sebastian Grimberg, Michel Bergmann, Sébastien Riffaud, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Modeling Enablers for Multi-PHysics and InteractionS (MEMPHIS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Aeronautics and Astronautics [Stanford] (AA Stanford), Stanford University, Department of Mechanical Engineering [Stanford], Institute for Computational and Mathematical Engineering [Stanford] (ICME), This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 872442. Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d’Aquitaine (see https://www.plafrim.fr/)., Plafrim, MEMPHIS, European Project: 872442,ARIA, European Project: 872442,ARIA(2019), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
ECSW method, Polynomial, Physics and Astronomy (miscellaneous), Proper Orthogonal Decomposition, 010103 numerical & computational mathematics, 01 natural sciences, symbols.namesake, Discontinuous Galerkin method, Applied mathematics, Domain decomposition, 0101 mathematics, Representation (mathematics), Parametric statistics, Mathematics, Numerical Analysis, Conservation law, Applied Mathematics, Domain decomposition methods, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Computer Science Applications, Euler equations, 010101 applied mathematics, Reduced-order model, Computational Mathematics, Modeling and Simulation, symbols, Reduction (mathematics), [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; The discontinuous Galerkin domain decomposition (DGDD) method couples subdomains of high-fidelity polynomial approximation to regions of low-dimensional resolution for the numerical solution of systems of conservation laws. In the low-fidelity regions, the solution is approximated by empirical modes constructed by Proper Orthogonal Decomposition and a reduced-order model is used to predict the solution. The high-dimensional model instead solves the system of conservation laws only in regions where the solution is not amenable to a low-dimensional representation. The coupling between the high-dimensional and the reduced-order models is then performed in a straightforward manner through numerical fluxes at discrete cell boundaries. We show results from application of the proposed method to parametric problems governed by the quasi-1D and 2D compressible Euler equations. In particular, we investigate the prediction of unsteady flows in a converging-diverging nozzle and over a NACA0012 airfoil in presence of shocks. The results demonstrate the stability and the accuracy of the proposed method and the significant reduction of the computational cost with respect to the high-dimensional model.

Published
2021

5. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths

Author

Muhammad Zaid Dauhoo, Laurent Dumas, Yusra Bibi Ruhomally, Université de Maurice, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), University of Mauritius, UoM, and We would like to acknowledge the assistance of Mr Maheshsingh Mungur from the University of Mauritius in the preparation of this work. This work has been conducted under the HEC (Higher Education Commission Mauritius) MPhil/PhD scholarship. The authors would also like to thank the reviewers for their constructive and valuable comments, which led to the improvement of the paper.

Subjects
Statistics and Probability, 050402 sociology, Relation (database), media_common.quotation_subject, targeted campaigns of prevention, [SDV]Life Sciences [q-bio], Population, 02 engineering and technology, relation-based, 0504 sociology, 0202 electrical engineering, electronic engineering, information engineering, Set (psychology), education, Recreation, Neighbourhood (mathematics), media_common, Consumption (economics), education.field_of_study, peer influence, Applied Mathematics, Addiction, 05 social sciences, Marijuana, Modeling and Simulation, graph cellular automaton, Graph (abstract data type), 020201 artificial intelligence & image processing, Psychology, Social psychology
Abstract

International audience; A novel approach depicting the dynamics of marijuana usage to gauge the effects of peer influence in a school population, is the site of investigation. Consumption of drug is considered as a contagious social epidemic which is spread mainly by peer influences. A relation-based graph-CA (r-GCA) model consisting of 4 states namely, Nonusers (N), Experimental users (E), Recreational users (R) and Addicts (A), is formulated in order to represent the prevalence of the epidemic on a campus. The r-GCA model is set up by local transition rules which delineates the proliferation of marijuana use. Data available in [4] is opted to verify and validate the r-GCA. Simulations of the r-GCA system are presented and discussed. The numerical results agree quite accurately with the observed data. Using the model, the enactment of campaigns of prevention targeting N, E and R states respectively were conducted and analysed. The results indicate a significant decline in marijuana consumption on the campus when a campaign of prevention targeting the latter three states simultaneously, is enacted.

Published
2021

6. Diffusion-redistanciation schemes for 2D and 3D constrained Willmore flow: application to the equilibrium shapes of vesicles

Author

Emmanuel Maitre, Mourad E. H. Ismail, Arnaud Sengers, Thibaut Metivet, ModELisation de l'apparence des phénomènes Non-linéaires (ELAN), 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), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Equations aux Dérivées Partielles (EDP), Laboratoire Jean Kuntzmann (LJK), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), DYnamique des Fluides COmplexes et Morphogénèse [Grenoble] (DYFCOM-LIPhy ), Laboratoire Interdisciplinaire de Physique [Saint Martin d’Hères] (LIPhy ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Most of the computations presented in this paper were performed using the Froggy platform of the GRICAD infrastructure (https://gricad.univ-grenoble-alpes.fr), which is supported by the Rhône-Alpes region (GRANT CPER07_13 CIRA) and the Equip@Meso project (reference ANR-10-EQPX-29-01) of the programme Investissements d’Avenir supervised by the Agence Nationale pour la Recherche, and the Atlas cluster from the Research Institute in Advanced Mathematics (IRMA - UMR7501)., ANR-10-EQPX-0029,EQUIP@MESO,Equipement d'excellence de calcul intensif de Mesocentres coordonnés - Tremplin vers le calcul petaflopique et l'exascale(2010), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2020-....] (UGA [2020-....])-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2020-....] (Grenoble INP [2020-....]), Université Grenoble Alpes [2020-....] (UGA [2020-....])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2020-....] (UGA [2020-....])-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2020-....] (Grenoble INP [2020-....]), Université Grenoble Alpes [2020-....] (UGA [2020-....]), Université Grenoble Alpes [2020-....] (UGA [2020-....])-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2020-....] (UGA [2020-....])-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2020-....] (Grenoble INP [2020-....]), DYnamique des Fluides COmplexes et Morphogénèse [Grenoble] [2020-….] (DYFCOM-LIPhy [2020-….]), Laboratoire Interdisciplinaire de Physique [Saint Martin d’Hères] [2020-….] (LIPhy [2020-….]), and Université Grenoble Alpes [2020-....] (UGA [2020-....])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2020-....] (UGA [2020-....])-Centre National de la Recherche Scientifique (CNRS)

Subjects
Volume and area preserving, Vol- ume and area preserving, Diffusion generated motion, Physics and Astronomy (miscellaneous), Computer science, Interface (Java), and phrases: Diffusion generated motion, Signed distance function, Clifford torus, 010103 numerical & computational mathematics, Willmore flow, 01 natural sciences, Level set, Dimension (vector space), FOS: Mathematics, Applied mathematics, Mathematics - Numerical Analysis, [PHYS.MECA.MEFL]Physics [physics]/Mechanics [physics]/Fluid mechanics [physics.class-ph], 0101 mathematics, Diffusion (business), [MATH]Mathematics [math], High-order geometrical flow, Numerical Analysis, Level set (data structures), Applied Mathematics, Numerical Analysis (math.NA), Thresholding, Computer Science Applications, 010101 applied mathematics, Computational Mathematics, Flow (mathematics), Modeling and Simulation, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

In this paper we present a novel algorithm for simulating geometrical flows, and in particular the Willmore flow, with conservation of volume and area. The idea is to adapt the class of diffusion-redistanciation algorithms to the Willmore flow in both two and three dimensions. These algorithms rely on alternating diffusions of the signed distance function to the interface and a redistanciation step, and with careful choice of the applied diffusions, end up moving the zero level-set of the distance function by some geometrical quantity without resorting to any explicit transport equation. The constraints are enforced between the diffusion and redistanciation steps via a simple rescaling method. The energy globally decreases at the end of each global step. The algorithms feature the computational efficiency of thresholding methods without requiring any adaptive remeshing thanks to the use of a signed distance function to describe the interface. This opens their application to dynamic fluid-structure simulations for large and realistic cases. The methodology is validated by computing the equilibrium shapes of two- and three-dimensional vesicles, as well as the Clifford torus.

Published
2020

7. The fast iterated bootstrap

Author

Mirza Trokic, Russell Davidson, McGill University = Université McGill [Montréal, Canada], Centre interuniversitaire de recherche en économie quantitative (CIREQ), Aix-Marseille Sciences Economiques (AMSE), École des hautes études en sciences sociales (EHESS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), IHS Markit, and This research was supported by the Canada Research Chair program (Chair in Economics, McGill University), and by grants from the Social Sciences and Humanities Research Council of Canada and the Fonds de Recherche du QuebecSociete Culture, Canada. We are grateful to seminar participants at the Third French Econometric Conference, the Singapore Management University, the Hong Kong University of Science and Technology, and the University of Sydney, for useful comments. We also thank our discussant Matt Webb for insightful comments at the 2017 CESG. Our thanks go to three anonymous referees and a guest co-editor for insightful comments that helped us improve the paper.

Subjects
Economics and Econometrics, Series (mathematics), Computer science, Applied Mathematics, 05 social sciences, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C12 - Hypothesis Testing: General, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C10 - General, Sense (electronics), [SHS.ECO]Humanities and Social Sciences/Economics and Finance, 01 natural sciences, Power (physics), Bootstrap iteration Fast iterated bootstrap, 010104 statistics & probability, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, Null (SQL), Iterated function, Distortion, 0502 economics and business, bootstrap iteration, fast iterated bootstrap, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C15 - Statistical Simulation Methods: General, 0101 mathematics, Algorithm, 050205 econometrics
Abstract

International audience; The standard forms of bootstrap iteration are very computationally demanding. As a result, there have been several attempts to alleviate the computational burden by use of approximations. In this paper, we extend the fast double bootstrap of Davidson and MacKinnon (2007) to higher orders of iteration, and provide algorithms for their implementation. The new methods make computational demands that increase only linearly with the level of iteration, unlike standard procedures, whose demands increase exponentially. In a series of simulation experiments, we show that the fast triple bootstrap improves on both the standard and fast double bootstraps, in the sense that it suffers from less size distortion under the null with no accompanying loss of power.

Published
2020

8. Multidimensional inequality and inframodular order

Author

Alain Chateauneuf, Zaier Aouani, Department of economics, University of Kansas, University of Kansas [Lawrence] (KU), IPAG Business School, Centre d'économie de la Sorbonne (CES), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), Paris School of Economics (PSE), École des Ponts ParisTech (ENPC)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), This paper is part of the research project ANR ‘‘Mesure des inégalités ordinales et multidimensionnelles’’ (ORDINEQ) of the French National Research Agency (Agence Nationale de la Recherche), whose financial support is gratefully acknowledged., and ANR-16-CE41-0005,ORDINEQ,La Mesure des Inégalités Ordinales et Multidimensionnelles(2016)

Subjects
Economics and Econometrics, education.field_of_study, Multi-attribute inequality, Inequality, Applied Mathematics, media_common.quotation_subject, 05 social sciences, Population, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Inframodular functions, Multidimensional Pigou–Dalton transfers, Order (business), 0502 economics and business, Econometrics, Inframodular order, 050207 economics, education, 050205 econometrics, media_common, Mathematics
Abstract

International audience; Motivated by the pertinence of Pigou–Dalton (PD) transfers for inequality measurement when only one attribute is involved, we show that inframodular functions are consistent with multidimensional PD transfers and that weakly inframodular functions fit more accurately with the traditional notion of PD transfers. We emphasize, for inequality rankings of allocations of multiple attributes in a population, the similarities of the inframodular order, defined using inframodular functions, with the concave order in the unidimensional framework.

Published
2020

9. Online estimation of integrated squared density derivatives

Author

Abdelkader Mokkadem, Mariane Pelletier, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), and We deeply thank the Referees for their thoughtful remarks, which led to a substantially improved version of our paper.

Subjects
Statistics and Probability, Recursive estimation, Mean squared error, 010102 general mathematics, Bandwidth (signal processing), Estimator, Probability density function, Density estimation, Online estimation, Rate of convergence, Stochastic algorithm, 01 natural sciences, 010104 statistics & probability, Kernel estimators of integrals, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Applied mathematics, 0101 mathematics, Statistics, Probability and Uncertainty, Mathematics, Parametric statistics
Abstract

Hall and Marron (1987) introduced kernel estimators of integrals of the squared m -order derivatives of a probability density. Mokkadem and Pelletier (2020) gave recursive versions of their estimators, but the main drawback of these estimators is that their update requires the use of all past data. The aim of this paper is the study of online versions of the estimators introduced by Hall and Marron (1987), that is of estimators which are not only recursive, but which also have the property that their update uses only the last available data. Rates of convergence in mean squared error (MSE) are calculated. Similarly to the estimators of Hall and Marron (1987) and of Mokkadem and Pelletier (2020), our online estimators achieve the parametric rate n − 1 when m = 0 or when higher order kernels are used. For the case when the parametric rate is not obtained, we also study an online version of the estimator proposed by Jones and Sheather (1991). Finally, we provide recursive estimators of the optimal bandwidth in the framework of density estimation.

Published
2020

10. Minimal NMR distance information for rigidity of protein graphs

Author

Leo Liberti, Benjamin Bardiaux, Michael Nilges, Thérèse E. Malliavin, Bradley Worley, Bruce R. Donald, Carlile Lavor, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Duke University [Durham], Bioinformatique structurale, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), C.L. would like to thank the Brazilian research agencies CNPq, FAPESP and B.D. would like to thank the NIH grants R01 GM-118543 and R01 GM-078031 for their financial support., We are also thankful to Angela Gronenborn and Michael Souza, for discussions that clarify some ideas in the paper, and to anonymous referees that made very important comments to this work., Bioinformatique structurale - Structural Bioinformatics, Universidade Estadual de Campinas = University of Campinas (UNICAMP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computational complexity theory, Nuclear Magnetic Resonance, 0211 other engineering and technologies, Structure (category theory), Rigidity (psychology), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Topology, 01 natural sciences, Article, Cardinality, Protein structure, Distance Geometry, Discrete Mathematics and Combinatorics, Molecule, Combinatorial search, Mathematics, Quantitative Biology::Biomolecules, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM], Applied Mathematics, Solution set, 021107 urban & regional planning, [SDV.BBM.BP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biophysics, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM], Vertex orders, 010201 computation theory & mathematics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular structure
Abstract

International audience; Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.

Published
2019

11. Stochastic modeling reveals how motor protein and filament properties affect intermediate filament transport

Author

Sandrine Etienne-Manneville, Stéphanie Portet, Cécile Leduc, J. C. Dallon, Brigham Young University (BYU), Polarité cellulaire, Migration et Cancer - Cell Polarity, Migration and Cancer, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), University of Manitoba [Winnipeg], This work was supported by: EPSRC grant numbers EP/K032208/1 and EP/R014604/1 and by La Ligue contre le cancer and the Institut Pasteur., The authors would like to thank the Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programme 'Coupling Geometric PDE’s with Physics for Cell Morphology, Motility and Pattern Formation' when the work on this paper was undertaken., Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS), and ANR-16-CE13-0019,SiFi2Net,Filaments intermédiaires: du filament unique au réseau(2016)

Subjects
0301 basic medicine, Statistics and Probability, Materials science, [SDV]Life Sciences [q-bio], Dynein, Biological Transport, Active, Kinesins, Catch bond, macromolecular substances, [SDV.BC]Life Sciences [q-bio]/Cellular Biology, Microtubules, Models, Biological, General Biochemistry, Genetics and Molecular Biology, Quantitative Biology::Cell Behavior, Protein filament, Motor protein, Quantitative Biology::Subcellular Processes, 03 medical and health sciences, 0302 clinical medicine, Molecular motor, Vimentin, Intermediate filaments, Intermediate filament, Cytoskeleton, Stochastic Processes, General Immunology and Microbiology, Applied Mathematics, Dyneins, Molecular motors, General Medicine, Kinesin, Stochastic, 030104 developmental biology, Modeling and Simulation, Biophysics, General Agricultural and Biological Sciences, 030217 neurology & neurosurgery
Abstract

International audience; Intermediate filaments are a key component of the cytoskeleton. Their transport along microtubules plays an essential role in the control of the shape and structural organization of cells. To identify the key parameters responsible for the control of intermediate filament transport, we generated a model of elastic filament transport by microtubule-associated dynein and kinesin. The model is also applicable to the transport of any elastically-coupled cargoes. We investigate the effect of filament properties such as number of motor binding sites, length, and elasticity on motion of filaments. Additionally, we consider the effect of motor properties, i.e. off rates, on filament transport. When one motor has a catch bond off rate it dictates the motion, whereas when motors have the same type of off rate filaments can alternate between retrograde and anterograde motions. The elasticity of filaments optimizes the filament transport and the coordination of motors along the length of the filament.

Published
2019

12. Linear Search by a Pair of Distinct-Speed Robots

Author

Tomasz Kociumaka, Jurek Czyzowicz, David Ilcinkas, Leszek Gąsieniec, Ralf Klasing, Dominik Pająk, Evangelos Bampas, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), University of Warsaw (UW), Institute of informatics [Wrocław], See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Pajak, Dominik S, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW)-University of Warsaw (UW), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)

Subjects
Engineering, General Computer Science, Computer science, different speeds, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Bang-bang robot, linear search, 01 natural sciences, Article, Computer Science::Robotics, Position (vector), mobile robots, 0202 electrical engineering, electronic engineering, information engineering, Cartesian coordinate robot, Point (geometry), Computer vision, [INFO]Computer Science [cs], Online algorithm, Simulation, Linear search, 021103 operations research, business.industry, Applied Mathematics, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, group search, Moment (physics), Line (geometry), Robot, 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business
Abstract

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

Published
2019

13. Quality of Real-Time Streaming in Wireless Cellular Networks - Stochastic Modeling and Analysis

Author

Bartlomiej Blaszczyszyn, Miodrag Jovanovic, Mohamed Kadhem Karray, Dynamics of Geometric Networks (DYOGENE), 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), France Télécom Recherche & Développement (FT R&D), France Télécom, This paper reports the results of the research undertaken under CRE-CIFRE thesis co-advising agreement between Inria and Orange Labs., 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), 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), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt

Subjects
FOS: Computer and information sciences, Computer science, Throughput, Computer Science - Networking and Internet Architecture, Base station, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], outage, FOS: Mathematics, Wireless, Electrical and Electronic Engineering, Radio resource management, Dimensioning, deep outage, stochastic model, Networking and Internet Architecture (cs.NI), business.industry, Wireless network, Applied Mathematics, Quality of service, Probability (math.PR), Real-time streaming, capacity-sharing, Poisson process, Computer Science Applications, LTE, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], interruptions, Cellular network, quality of service, Resource allocation, business, Mathematics - Probability, mobile TV, Computer network
Abstract

We present a new stochastic service model with capacity sharing and interruptions, appropriate for the evaluation of the quality of real-time streaming (RTS), like e.g. mobile TV, in wireless cellular networks. The general model takes into account multi-class Markovian process of call arrivals, (to capture different radio channel conditions, requested streaming bit-rates and durations) and allows for a general resource allocation policy saying which users are temporarily denied the requested fixed streaming bit-rates (put in outage) due to resource constraints. We give expressions for several important performance characteristics of the model, including mean time spent in outage and mean number of outage incidents for a typical user of a given class. These expressions involve only stationary probabilities of the (free) traffic demand process, which is a vector of independent Poisson random variables describing the number of users of different classes. In order to analyze RTS in 3GPP Long Term Evolution (LTE) cellular networks, we specify our general model assuming orthogonal user channels with the peak bit-rates close to the theoretical Shannon's bound in the additive white Gaussian noise (AWGN) channel, which leads to the resource constraints in a multi-rate linear form. In this setting we consider a natural class of least-effort-served-first resource allocation policies, for which the characteristics of the model can be further evaluated using Fourier analysis of Poisson variables. Within this class we identify and evaluate an optimal and a fair policy, the latter being suggested by LTE implementations. We also propose some intermediate policies, which allow to solve the optimality/fairness tradeoff caused by unequal user radio-channel conditions. Our results can be used for the evaluation of the quality of RTS in LTE networks and dimensioning of these networks., Comment: (06/2012)

Published
2014

14. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles

Author

Paola Flocchini, David Ilcinkas, Nicola Santoro, School of Electrical Engineering and Computer Science (EECS), University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Ottawa], Carleton University, See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
Theoretical computer science, General Computer Science, FIFO (computing and electronics), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Topology (electrical circuits), 0102 computer and information sciences, 02 engineering and technology, Dangerous graphs, Topology, 01 natural sciences, Graph exploration, Autonomous robots, 0202 electrical engineering, electronic engineering, information engineering, Search problem, Pebble, Mathematics, Applied Mathematics, Black hole search, Distributed computing, Computer Science Applications, 010201 computation theory & mathematics, Asynchronous communication, Theory of computation, 020201 artificial intelligence & image processing, Node (circuits), Mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of two asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node), can locate the black hole in an arbitrary network of known topology; this can be done with Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles.

Published
2012

15. Communication algorithms with advice

Author

Pierre Fraigniaud, Andrzej Pelc, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Computer Networks and Communications, Distributed computing, Message complexity, Network, 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Graph, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Size of advice, Dissemination, Mathematics, Linear number, business.industry, Applied Mathematics, Telecommunications network, Algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Broadcast communication network, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Advice (complexity), Wakeup
Abstract

International audience; We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

Published
2010

16. Labeling Schemes for Tree Representation

Author

David Ilcinkas, David Peleg, Pierre Fraigniaud, Amos Korman, Reuven Cohen, Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Pierre Fraigniaud and David Ilcinkas were supported by project ``PairAPair' of the ACI Masses de Données, project ``Fragile' of the ACI Sécurité et Informatique, and project ``Grand Large' of INRIA., Ajit Pal, Ajay D. Kshemkalyani, Rajeev Kumar, Arobinda Gupta, Department of Electrical and Computer Engineering [Boston University] (ECE), Boston University [Boston] (BU), Technion - Israel Institute of Technology [Haifa], See paper for details., and ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007)

Subjects
K-ary tree, General Computer Science, Symmetric graph, Edge-graceful labeling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, symbols.namesake, 0202 electrical engineering, electronic engineering, information engineering, Connectivity, Mathematics, Minimum degree spanning tree, Discrete mathematics, spanning tree, Spanning tree, Applied Mathematics, Shortest-path tree, Complete graph, 020206 networking & telecommunications, 020207 software engineering, Numbering, Labeling scheme, Computer Science Applications, Planar graph, tree representation, Tree structure, 010201 computation theory & mathematics, symbols, Regular graph, Gomory–Hu tree
Abstract

International audience; This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports} tree labeling $\cL_{all}$ gives each node $v$ of $G$ a label containing the port numbers of all the {\em tree} edges incident to $v$. The {\em upward} tree labeling $\cL_{up}$ labels each node $v$ by the number of the port leading from $v$ to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted $M_{up}(T)$ and $S_{up}(T)$ for $\cL_{up}$ and $M_{all}(T)$ and $S_{all}(T)$ for $\cL_{all}$. The problem studied in this paper is the following: Given a graph $G$ and a predefined port labeling for it, with the ports of each node $v$ numbered by $0,\ldots,\deg(v)-1$, select a rooted spanning tree for $G$ minimizing (one of) these measures. We show that the problem is polynomial for $M_{up}(T)$, $S_{up}(T)$ and $S_{all}(T)$ but NP-hard for $M_{all}(T)$ (even for 3-regular planar graphs). We show that for every graph $G$ and port numbering there exists a spanning tree $T$ for which $S_{up}(T) = O(n\log\log n)$. We give a tight bound of $O(n)$ in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.

Published
2005