Show item record

dc.contributor.advisorMcKenzie, Pierre
dc.contributor.authorCôté, Hugo
dc.date.accessioned2019-06-07T16:19:00Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2019-06-07T16:19:00Z
dc.date.issued2019-03-13
dc.date.submitted2018-08
dc.identifier.urihttp://hdl.handle.net/1866/22123
dc.subjectcomplexité de la communicationfr
dc.subjectprogramme de branchement catalytiquefr
dc.subjectcalcul transparentfr
dc.subjectcomposition de fonctionfr
dc.subjectgadgetfr
dc.subjectanalyseurfr
dc.subjectprogramme sur un groupefr
dc.subjectfonction symétriquefr
dc.subjectproduit scalairefr
dc.subjectdag-like communicationfr
dc.subjectcommunication complexityfr
dc.subjectcatalytic branching programfr
dc.subjecttranparent computationfr
dc.subjectfunction compositionfr
dc.subjectanalyzerfr
dc.subjectprogram over a groupfr
dc.subjectsymmetric functionfr
dc.subjectscalar productfr
dc.subject.otherApplied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)fr
dc.titleProgrammes de branchement catalytiques : algorithmes et applicationsfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractLe présent mémoire étudie le modèle de calcul des programmes de branchement k- catalytiques. Un programme de branchement k-catalytique sert à effectuer le calcul de k fonctions booléennes sur une même entrée et représente la contrepartie non uniforme de la notion de machine de Turing catalytique introduite par Buhrman et al. (STOC, 2014). On montre que pour toute fonction booléenne symétrique f il existe un programme de branchement catalytique qui fait le calcul de f un nombre exponentiel de fois avec une taille O(nlgn) par copie. On montre un résultat similaire reliant la complexité de n’importe quelle fonction booléenne f sur n bits se décomposant sous la forme f(x) = h(g(x)) à celle de g et de h, où g est une fonction de {0,1}^n dans G, h une fonction de G dans {0,1} et G est un groupe. On introduit également un ensemble de notions dont celles de gadgets, d’analyseurs et de programmes sur des groupes permettant de montrer comment le calcul catalytique non uniforme peut aller au-delà du calcul transparent. Enfin, le nouveau formalisme introduit révèle le lien jusqu’à maintenant inexploré entre le calcul catalytique et la complexité de la communication.fr
dcterms.abstractThe present master’s thesis studies the computational model of k-catalytic branching programs. A k-catalytic branching program is used to carry out the computation of k boolean functions on the same input and represents the nonuniform counterpart to the notion of catalytic Turing machine introduced by Buhrman et al. (STOC, 2014). It is shown that for any boolean symmetric function f there exists a k-catalytic branching program which computes f an exponential number of times and which has size O(nlgn) per copy. We show a similar result linking the complexity of any boolean function f on n bits expressible as f(x) = h(g(x)) to the complexity of g and h, where g is a function from {0,1}^n to G, h a function from G to {0,1} and G is a group. Furthermore, we introduce a set of notions such as gadgets, analyzers and programs over groups allowing us to show how nonuniform catalytic computation can go beyond transparent computation. Lastly, the new formalism introduced reveals the link until now unexplored between catalytic computation and communication complexity.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record