La comparaison des enfants qui acquièrent une langue seconde (L2) à des enfants avec trouble spécifique du langage (TSL) a montré des similarités entre les performances morphosyntaxiques des deux groupes. Cette étude vise à mieux comprendre l’acquisition L2 enfantine typique afin de permettre l’identification d’un TSL chez les enfants L2. Une étude longitudinale de taux de propositions enchâssées et d’erreurs ont été a été faite à partir d’échantillons de langage spontané en français de 22 enfants anglophones âgés de 6;9-12;7 et de 19 enfants monolingues francophones avec TSL âgés de 6;5 à 12;11. Les résultats révèlent que les L2 font plus d’enchâssées que les enfants avec SLI, mais les deux groupes ont eu des taux d’erreurs comparables. La discussion porte sur l’implication de ces résultats sur l’identification des TSL chez les enfants L2. / Research on children acquiring a second language (L2 children) and children with SLI has revealed similarities in their morphosyntactic performance. This study seeks to better understand how children acquire an L2 in order to distinguish typical from atypical L2 acquisition. A longitudinal study of clausal embedding and error rates was made based on spontaneous language samples of 22 English-speaking children (aged 6;9-12;7) acquiring French as an L2 and 19 monolingual French-speaking children with SLI (aged 6;5-12;11). The results revealed that L2 children used clausal embedding more often than the children with SLI, but the SLI and L2 had similar error rates. Analyses of the frequency of embedding and errors revealed correlations that were positive in the L2 group and negative in the SLI. The discussion focuses on the implications of these findings for the identification of SLI in L2 children.

The flight search engine is a technology used in the air travel industry. It allows the traveler to search and book for the best flight options, such as the combination of flights while keeping the best services, options, and price. The computation for a flight search query can be very intensive given its parameters and complexity. The project goal is to predict the flight search queries computation cost for a new flight search engine product when dealing with parameters change and optimizations. The problem of flight search cost prediction is a regression problem. We propose to solve the problem by delimiting the problem based on its business logic and meaning. Our problem has data defined as a graph, which is why we have chosen Graph Neural Network. We have investigated multiple pretraining strategies for the evaluation of node embedding concerning a realworld regression task, including using a line graph for the training. The embeddings are used for downstream regression tasks. Our work is based on some stateoftheart Machine Learning, Deep Learning, and Graph Neural Network methods. We conclude that for some business use cases, the predictions are suitable for production use. In addition, the prediction of tree ensemble boosting methods produces negatives predictions which further degrade the R2 score by 4% because of the business meaning. The Deep Neural Network outperformed the most performing Machine Learning methods by 8% to 12% of R2 score. The Deep Neural Network also outperformed Deep Neural Network with pretrained node embedding from the Graph Neural Network methods by 11% to 17% R2 score. The Deep Neural Network achieved 93%, 81%, and 63% R2 score for each task with increasing difficulty. The training time range from 1 hour for Machine Learning models, 2 to 10 hours for Deep Learning models, and 8 to 24 hours for Deep Learning model for tabular data trained end to end with Graph Neural Network layers. The inference time is around 15 minutes. Finally, we found that using Graph Neural Network for the node regression task does not outperform Deep Neural Network. / Flygsökmotor är en teknik som används inom flygresebranschen. Den gör det möjligt för resenären att söka och boka de bästa flygalternativen, t.ex. kombinationer av flygningar med bästa service, alternativ och pris. Beräkningen av en flygsökning kan vara mycket intensiv med tanke på dess parametrar och komplexitet. Projektets mål är att förutsäga beräkningskostnaden för flygsökfrågor för en ny produkt för flygsökmotor när parametrar ändras och optimeringar görs. Problemet med att förutsäga kostnaderna för flygsökning är ett regressionsproblem. Vi föreslår att man löser problemet genom att avgränsa det utifrån dess affärslogik och innebörd. Vårt problem har data som definieras som en graf, vilket är anledningen till att vi har valt Graph Neural Network. Vi har undersökt flera förträningsstrategier för utvärdering av nodinbäddning när det gäller en regressionsuppgift från den verkliga världen, bland annat genom att använda ett linjediagram för träningen. Inbäddningarna används för regressionsuppgifter i efterföljande led. Vårt arbete bygger på några toppmoderna metoder för maskininlärning, djupinlärning och grafiska neurala nätverk. Vi drar slutsatsen att förutsägelserna är lämpliga för produktionsanvändning i vissa Vi drar slutsatsen att förutsägelserna är lämpliga för produktionsanvändning i vissa fall. Dessutom ger förutsägelserna från trädens ensemble av boostingmetoder negativa förutsägelser som ytterligare försämrar R2poängen med 4% på grund av affärsmässiga betydelser. Deep Neural Network överträffade de mest effektiva metoderna för maskininlärning med 812% av R2poängen. Det djupa neurala nätverket överträffade också det djupa neurala nätverket med förtränad node embedding från metoderna för grafiska neurala nätverk med 11 till 17% av R2poängen. Deep Neural Network uppnådde 93, 81 och 63% R2poäng för varje uppgift med stigande svårighetsgrad. Träningstiden varierar från 1 timme för maskininlärningsmodeller, 2 till 10 timmar för djupinlärningsmodeller och 8 till 24 timmar för djupinlärningsmodeller för tabelldata som tränats från början till slut med grafiska neurala nätverkslager. Inferenstiden är cirka 15 minuter. Slutligen fann vi  att användningen av Graph Neural Network för uppgiften om regression av noder inte överträffar Deep Neural Network.

Simulating virtual objects which can deform or break apart within their environments is now common in state-of-the-art virtual simulations such as video games or surgery simulations. Real-time performance requires a physical model which provides an approximation to the true solution for fast computations but at the same time provides enough believability of the simulation to the user. Recent research in object deformation and fracture has revolved around embedding portions of the simulation for graphical display inside a much simpler physical domain which is invisible to the user. Embedding complex geometry in a simpler domain allows for very complex effects to occur in a much more robust and computationally efficient manner. This thesis explores a novel method to efficiently embed a high-resolution surface mesh inside a coarse tetrahedral physical mesh for the purposes of interactive simulation and display. A technique to display interior regions as solid geometry without explicitly re-meshing the graphical mesh during fracture has been explored and developed. Keeping the graphical mesh static in memory during simulation allows the geometry to be off-loaded to the GPU while shaders can be utilized to only display portions of the geometry which are locally contained within the physical mesh. Recent advances in GPU technology have also been exploited in order to provide an increase in visual fidelity and help achieve the illusion that the virtual object itself is breaking apart in a physically plausible manner.

As the "network of network", the Internet has been playing a central and crucial role in modern society, culture, knowledge, businesses and so on in a period of over two decades by supporting a wide variety of network technologies and applications. However, due to its popularity and multi-provider nature, the future development of the Internet is limited to simple incremental updates. To address this challenge, network virtualization has been propounded as a potential candidate to provide the essential basis for the future Internet architecture. Network virtualization is capable of providing an open and flexible networking environment in which service providers are allowed to dynamically compose multiple coexisting heterogeneous virtual networks on a shared substrate network. Such a flexible environment will foster the deployment of diversified services and applications. A major challenge in network virtualization area is the Virtual Network Embedding (VNE), which aims to statically or dynamically allocate virtual nodes and virtual links on substrate resources, physical nodes and paths. Making effective use of substrate resources requires high-efficient and survivable VNE techniques. The main contribution of this thesis is two high-performance p-Cycle-based survivable virtual network embedding approaches. These approaches take advantage of p-Cycle-based protection techniques that minimize the backup resources while providing a full VN protection scheme against link and node failures.

We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. In this talk, we provide an overview of the network virtualization environment (NVE) and address two basic problems in this emerging field of networking research. The identity management problem is primarily concerned with ensuring interoperability across heterogeneous identifier spaces for locating and identifying end hosts in different virtual networks. We describe the architectural and the functional components of a novel identity management framework (iMark) that enables end-to-end connectivity across heterogeneous virtual networks in the NVE without revoking their autonomy. The virtual network embedding problem deals with the mapping of virtual nodes and links onto physical network resources. We argue that the separation of the node mapping and the link mapping phases in the existing algorithms considerably reduces the solution space and degrades embedding quality. We propose coordinated node and link mapping to devise two algorithms (D-ViNE and R-ViNE) for the online version of the problem under realistic assumptions and compare their performance with the existing heuristics.

We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. In this talk, we provide an overview of the network virtualization environment (NVE) and address two basic problems in this emerging field of networking research. The identity management problem is primarily concerned with ensuring interoperability across heterogeneous identifier spaces for locating and identifying end hosts in different virtual networks. We describe the architectural and the functional components of a novel identity management framework (iMark) that enables end-to-end connectivity across heterogeneous virtual networks in the NVE without revoking their autonomy. The virtual network embedding problem deals with the mapping of virtual nodes and links onto physical network resources. We argue that the separation of the node mapping and the link mapping phases in the existing algorithms considerably reduces the solution space and degrades embedding quality. We propose coordinated node and link mapping to devise two algorithms (D-ViNE and R-ViNE) for the online version of the problem under realistic assumptions and compare their performance with the existing heuristics.

The objective of this thesis is to present a robust watermarking algorithm for H.264 and to address challenges in compressed-domain video watermarking. To embed a perceptually invisible watermark in highly compressed H.264 video, we use a human visual model. We extend Watson's human visual model developed for 8x8 DCT block to the 4x4 block used in H.264. In addition, we use P-frames to increase the watermark payload. The challenge in embedding the watermark in P-frames is that the video bit rate can increase significantly. By using the structure of the encoder, we significantly reduce the increase in video bit rate due to watermarking. Our method also exploits both temporal and texture masking. We build a theoretical framework for watermark detection using a likelihood ratio test. This framework is used to develop two different video watermark detection algorithms; one detects the watermark only from watermarked coefficients and one detects the watermark from all the ac coefficients in the video. These algorithms can be used in different video watermark detection applications where the detector knows and does not know the precise location of watermarked coefficients. Both watermark detection schemes obtain video watermark detection with controllable detection performance. Furthermore, control of the detector's performance lies completely with the detector and does not place any burden on the watermark embedding system. Therefore, if the video has been attacked, the detector can maintain the same detection performance by using more frames to obtain its detection response. This is not the case with images, since there is a limited number of coefficients that can be watermarked in each image before the watermark is visible.

As one of the major mid-rapidity tracking devices of the STAR detector at the Relativistic Heavy-Ion Collider (RHIC), the Time Projection Chamber (TPC) plays an important role in measuring trajectory and energy of high energy charged particles in polarized proton-proton collision experiments. TPC's in-jet tracking efficiency represents the largest systematic uncertainty on jet energy scale at high transverse momentum, whose measurement contributes to the understanding of the spin structure of protons. The objective of this analysis is to get a better estimation of this systematic uncertainty, through methods of pure Monte-Carlo simulation and real- data embedding, in which simulated tracks are embedded into real-data events. Be- sides, simulated tracks are also embedded into Monte-Carlo events, to make a strict comparison for the uncertainty estimation. The result indicates that the unexplained part of the systematic uncertainty is reduced to 3.3%, from a previous quoted value of 5%. This analysis also suggests that future analysis, such as embedding jets into zero-bias real data and analysis with much higher event statistics, will benefit the understanding of the systematic uncertainty of the in-jet TPC tracking efficiency.