BEGIN:VCALENDAR
X-WR-CALNAME:Webnotice (All Departments)
X-WR-CALDESC:Webnotice (All Departments) at University of Waterloo
X-PUBLISHED-TTL:PT60M
PRODID:-//UW-Webnotice/NONSGML 0.1//EN
VERSION:2.0
BEGIN:VEVENT
DTSTAMP:20200817T153000Z
UID:2020_e01ea1d26d7ef68ae478a5722c1f5730.wnotice@math.uwaterloo.ca
DTSTART:20200817T153000Z
DTEND:20200817T163000Z
SUMMARY:State transfer and the size of the graph (Algebraic Graph Theory Seminar)
LOCATION:Zoom
DESCRIPTION:State transfer and the size of the graph\nGabriel Coutinho, Universidade Federal de Minas Gerais\n\nhttps://us02web.zoom.us/j/86564623661?pwd=T1h6eGdHZTlVTDJYdkJOcXNlQ2l3QT09 Meeting ID: 865 6462 3661 Password: 697900\n\nIf there is perfect state transfer between two vertices at distance d, how small can the graph be compared to d? This question is motivated by the fact that the known infinite families of graphs admitting state transfer at increasingly large distances are all obtained from graph products, thus their sizes grow exponentially compared to their diameter. On the other hand, building quantum systems with many qubits can be expensive. I will show that the size of graphs admitting state transfer is at least cubic in the diameter, and I will also discuss some improvements in the exponential upper bound due to A. Kay. Nevertheless, the question that motivates this talk remains open, and in the end we will discuss some possible research directions.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200817T170000Z
UID:2020_d6befae6969fef953b30e59add459a70.wnotice@math.uwaterloo.ca
DTSTART:20200817T170000Z
DTEND:20200817T180000Z
SUMMARY:NeuRA: Using Neural Networks to Improve WiFi Rate Adaptation (Systems and Networking Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:NeuRA: Using Neural Networks to Improve WiFi Rate Adaptation\nShervin Khastoo, Master's candidate, David R. Cheriton School of Computer Science\n\nAlthough a variety of rate adaptation algorithms have been proposed for 802.11 devices, sampling-based algorithms are preferred and used in practice because they only require frame loss information which is available on all devices. Unfortunately, sampling can impose significant overheads because it can lead to excessive frame loss or the choice of suboptimal rates. In this thesis, we design a novel neural network based rate adaptation algorithm, called NeuRA. NeuRA significantly improves the efficiency of sampling in rate adaptation algorithms by using a neural network model to predict the expected throughput of many rates, rather than sampling their throughput. Furthermore, we propose a feature selection technique to select the best set of rates to sample. \n\nDespite decades of research on rate adaptation in 802.11 networks, there are no definitive results which determine which algorithm is the best or if any algorithm is close to optimal. We design an offline algorithm that uses information about the fate of future frames to make statistically optimal frame aggregation and rate adaptation decisions. This algorithm provides an upper bound on the throughput that can be obtained by practical online algorithms and enables us to evaluate rate adaptation algorithms with respect to this upper bound. \n\nOur trace-based evaluations using a wide variety of real-world scenarios show that NeuRA outperforms the widely-used Minstrel HT algorithm by up to 24% (16% on average) and the Intel iwl-mvm-rs algorithm by up to 32% (13% on average). Moreover, the upper bound given by the offline optimal algorithm shows a throughput up to 58% (30% on average) higher than Minstrel HT and up to 31% (12% on average) higher than NeuRA. Hence, NeuRA reduces the gap in throughput between Minstrel HT and the offline optimal algorithm by half. Additionally, our results show that several-fold improvements over Minstrel HT shown in previous work are unlikely to be obtained in real-world scenarios. Finally, we implement NeuRA using the Linux ath9k driver to show that the neural network processing requirements are sufficiently low to be practical and that NeuRA can be used to obtain statistically significant improvements in throughput when compared with Minstrel HT. \n\nDownload the presentation slides at \n\nTo join this presentation on Zoom, please go to \n\nMeeting ID
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200817T180000Z
UID:2020_b09bd6fa7600f54ae970c323b8b1faaa.wnotice@math.uwaterloo.ca
DTSTART:20200817T180000Z
DTEND:20200817T190000Z
SUMMARY:Enumerable functor with positive atomic diagram (Part 3) (Computability Learning Seminar)
LOCATION:Google Meet: https://meet.google.com/fhn-osch-rss
DESCRIPTION:Enumerable functor with positive atomic diagram (Part 3)\nDaniel Yu, Department of Pure Mathematics, University of Waterloo\n\nThis talk focuses on the equivalence between Sigma_1^c interpretation and the existence of positive enumerable functor. We will finish the "interpretation to functor" direction, and start getting an idea of the converse.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200817T190000Z
UID:2020_d2d170884ee94aec8db18933bb4f65cc.wnotice@math.uwaterloo.ca
DTSTART:20200817T190000Z
DTEND:20200817T200000Z
SUMMARY:A graph-based introduction to the chromatic symmetric function (Graphs and Matroids Seminar)
LOCATION:Zoom (details below)
DESCRIPTION:A graph-based introduction to the chromatic symmetric function\nSophie Spirkl, University of Waterloo\n\nThe chromatic symmetric function is a generalization of the chromatic polynomial, and has been studied extensively, mostly in algebraic combinatorics. Ill give an introduction to the chromatic symmetric function from a graph theory point of view, including some results and open questions. \n\nJoint work with Logan Crew. \n\nZoom: https://us02web.zoom.us/j/92293499003 Password: spirkl1
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200818T140000Z
UID:2020_aec6b61c8c5409f28fa405ab65ac1ea4.wnotice@math.uwaterloo.ca
DTSTART:20200818T140000Z
DTEND:20200818T150000Z
SUMMARY:Analyzing the Signal Strength of 2,946 Clients Operating in 446 WiFi Networks (Systems and Networking Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Analyzing the Signal Strength of 2,946 Clients Operating in 446 WiFi Networks\nMidul Jacob, Masters candidate, David R. Cheriton School of Computer Science\n\nIn this thesis we analyze data that was collected over a 24 hour period from 446 access points that provide connections for 2,946 clients. The data was obtained from deployments of modern commercial Google Wifi access points. A focus of this thesis is an analysis of the Received Signal Strength Indication (RSSI) from messages sent from clients to the access point. The RSSI depends on both the environment in which the signals operate and the distance between the client and the access point. \n\nOur dataset includes 417,122 data points of which 45.1% of the data points are from signals using the 2.4 GHz spectrum and the remaining 4.9% are from the 5 GHz spectrum. The data has been collected by each access point (AP) every 5 minutes over a period of 24 hours. We find from our analysis that across all access points, the average number of clients that are simultaneously connected in any 5 minute window is quite small. That is, 65.7% of the APs have on average 3 or fewer clients that are simultaneously connected in any 5 minute window. However, we also find that 6.5% of the APs service on average 9 or more clients. \n\nIn this thesis we develop and utilize a methodology to categorize clients and networks using RSSI values (signal strengths) of the messages received by access points from the clients, to study the possible PHY rates which can be used by clients to send messages to the APs. The methodology also helps us to capture and examine the variability in signal strengths. Several previous studies have characterized WiFi networks using the measured throughput of the clients. However, the throughput experienced and rates used by clients in those studies depend on the capabilities of the clients. We believe that a significant advantage of our methodology is that it is independent of the capabilities of the clients used in the study. In addition, our methodology is also able characterize the environments in which the WiFi devices operate. This is because our methodology primarily uses the signal strength of the messages to characterize devices in a WiFi network and the signal strength changes over time due to the movements of the sender, receiver, or people in the area. \n\nWe use our methodology to analyze both clients and networks. We find from our analysis of clients that, over the 24 hour period, 90% of the signals from 84.2% of the clients are received by the APs with either Good or Moderate signal strengths. Thus, for the majority of the clients signal strengths are mostly quite reliable. We also find that clients using the 2.4 GHz spectrum have signals about as good as or better than clients using the 5 GHz spectrum. However, perhaps one of the most interesting findings is that, when analyzing networks we find that 27% or more of all networks have one or more clients whose signals are received by the AP with unreliable signal strengths. These clients could potentially impede the throughput of all the other clients in the same network and also networks in the vicinity, due to the WiFi performance anomaly problem. We also find that networks with more clients are not more likely to have clients with unreliable signals than expected based on probability. From the results of our analysis of clients and the analysis of networks, we note that a small number of clients may impact the performance of a considerably large number of networks. \n\nTo join this virtual presentation on Zoom, please go to \n\nMeeting ID
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200818T150000Z
UID:2020_558b2cdd0b734d1e1b7658f5acc0cec3.wnotice@math.uwaterloo.ca
DTSTART:20200818T150000Z
DTEND:20200818T160000Z
SUMMARY:On the Relationship Between the Developers Perceptible Ethnicity and the Evaluation of Contributions in GitHub (Software Engineering Research Group Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:On the Relationship Between the Developers Perceptible Ethnicity and the Evaluation of Contributions in GitHub\nReza Nadri, Masters candidate, David R. Cheriton School of Computer Science\n\nContext : Open Source Software (OSS) projects are typically the result of collective efforts performed by developers with different backgrounds. Although the quality of developers contributions should be the only factor influencing the evaluation of the contributions to OSS projects, recent studies have shown that diversity issues affect the acceptance or rejection of the contributions. \n\nObjective \n\nMethodology \n\nResults \n\nConclusion
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200818T170000Z
UID:2020_24e6dd961134d46a7f6c2a297efbbe4c.wnotice@math.uwaterloo.ca
DTSTART:20200818T170000Z
DTEND:20200818T180000Z
SUMMARY:Higher Order Random Walks, Local Spectral Expansion, and Applications (Algorithms and Complexity Group PhD Defence)
LOCATION:Online
DESCRIPTION:Higher Order Random Walks, Local Spectral Expansion, and Applications\nVedat Levi Alev, David R. Cheriton School of Computer Science\n\nThe study of spectral expansion of graphs and expander graphs has been an extremely fruitful line of research in Mathematics and Computer Science, with applications ranging from random walks and fast sampling to optimization. In this dissertation, we study high dimensional local spectral expansion, which is a generalization of the theory of spectral expansion of graphs, to simplicial complexes. \n\nWe study two random walks on simplicial complexes, which we call the down-up walk, which captures a wide array of natural random walks which can be used to sample random combinatorial objects via the so-called heat-bath dynamics, and the swap walk, which can be thought as a random walk on a sparse version of the Kneser graph. \n\nWe prove a sharp bound on the second eigenvalue of the down-up walk and discuss applications of this in establishing the rapid mixing of several Markov chains used for sampling combinatorial objects. \n\nNext, we study the spectrum of the swap walks, and show that using local spectral expansion we can relate the spectrum of swap-walk on any simplicial complex to the spec- trum of the Kneser graph. We will mention applications of this result in (i) approximating constraint satisfaction problems (CSPs) on instances where the constraint hypergraph is a high dimensional local spectral expander; and in (ii) the construction of new families of list decodable codes based on (sparse) Ramanujan complexes of Lubotzky, Samuels, and Vishne.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200818T183000Z
UID:2020_d83d8b83f00ace28464ea2851c9e6f2b.wnotice@math.uwaterloo.ca
DTSTART:20200818T183000Z
DTEND:20200818T193000Z
SUMMARY:Dialog Response Generation Using Adversarially Learned Latent Bag-of-Words (Artificial Intelligence Lab Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Dialog Response Generation Using Adversarially Learned Latent Bag-of-Words\nKashif Khan, Masters candidate, David R. Cheriton School of Computer Science\n\nDialog response generation is the task of generating response utterance given a query utterance. Apart from generating relevant and coherent responses, one would like the dialog generation model to generate diverse and informative sentences. \n\nIn this work, we propose and explore a novel multi-stage dialog response generation approach. In the first stage of our proposed multi-stage approach, we construct a variational latent space on the bag-of-words representation of the query and response utterances. In the second stage, transformation from query latent code to response latent code is learned using an adversarial process. The final stage involves fine-tuning a pretrained transformer based model called text-to-text transfer (T5) (Raffel et al., 2019) using a novel training regimen to generate the response utterances by conditioning on the query utterance and the response word learned in the previous stage. \n\nWe evaluate our proposed approach on two popular dialog datasets. We show using quantitative metrics that our proposed approach outperforms the state of the art approaches in generating diverse responses while still performing competitively on other quantitative metrics. \n\nTo join this masters thesis presentation on Zoom, please go to \n\nMeeting ID
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200819T140000Z
UID:2020_6626a193857c83bdb3ebaac634cbc49d.wnotice@math.uwaterloo.ca
DTSTART:20200819T140000Z
DTEND:20200819T150000Z
SUMMARY:Comparing Smartphone Speech Recognition and Touchscreen Typing for Composition and Transcription (Human-Computer Interaction Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Comparing Smartphone Speech Recognition and Touchscreen Typing for Composition and Transcription\nMargaret Foley, Masters candidate, David R. Cheriton School of Computer Science\n\nRuan et al . found transcribing short phrases with speech recognition nearly 200% faster than typing on a smartphone. We extend this comparison to a novel composition task, using a protocol that enables a controlled comparison with transcription. Results show that both composing and transcribing with speech is faster than typing. But, the magnitude of this difference is lower with composition, and speech has a lower error rate than keyboard during composition, but not during transcription. When transcribing, speech outperformed typing in most NASA-TLX measures, but when composing, there were no significant differences between typing and speech for any measure except physical demand. \n\nTo join this presentation on Zoom, please go to
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200819T180000Z
UID:2020_41dbd8d225a5d1bfa5e8220bf85fae66.wnotice@math.uwaterloo.ca
DTSTART:20200819T180000Z
DTEND:20200819T190000Z
SUMMARY:Factoring Semi-primes With (Quantum) SAT Solvers (Institute for Quantum Computing PhD Seminar)
LOCATION:Online PhD seminar
DESCRIPTION:Factoring Semi-primes With (Quantum) SAT Solvers\nSebastian Verschoor, PhD candidate, David R. Cheriton School of Computer Science\n\nThe assumed computationally difficulty of factoring large integers forms the basis of security for RSA public-key cryptography, which specifically relies on products of two large primes or semi-primes. The best-known factoring algorithm for classical computers, the Number Field Sieve, runs in sub-exponential time. Since integer factorization is in NP, one can reduce this problem to any NP-hard problem, such as Boolean Satisfiability (SAT). While reducing factoring to SAT has proved to be useful for studying SAT solvers, attempting to factor large integers via such a reduction has not been found to be successful. \n\nShors quantum factoring algorithm factors any integer in polynomial time, although large-scale fault-tolerant quantum computers capable of implementing Shors algorithm are not yet available, so relevant benchmarking experiments for factoring via Shors algorithm are not yet possible. In recent years, however, several authors have attempted factorizations with the help of quantum processors via reductions to NP-hard problems. While this approach may shed some light on some algorithmic approaches for quantum solutions to NP-hard problems, in the first work we study and question the practical effectiveness of this approach for factoring large numbers. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware. \n\nIn the second work the use of SAT solvers is restricted to a smaller task related to factoring: finding smooth numbers, which is an essential step of the Number Field Sieve. We present a SAT circuit that can be given to quantum SAT solvers such as annealers in order to perform this step of factoring. If quantum SAT solvers achieve any asymptotic speedup over classical brute-force search, then our factoring algorithm is faster than the classical NFS. \n\nTo join this meeting on Webex, please go to \n\nMeeting number
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200820T140000Z
UID:2020_95de4af36728c4ac55d1af69b9adc922.wnotice@math.uwaterloo.ca
DTSTART:20200820T140000Z
DTEND:20200820T150000Z
SUMMARY:Entropy-Based Aggregate Posterior Alignment Techniques for Deterministic Autoencoders and Implications for Adversarial Examples (Artificial Intelligence Lab Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Entropy-Based Aggregate Posterior Alignment Techniques for Deterministic Autoencoders and Implications for Adversarial Examples\nAmur Ghose, Masters candidate, David R. Cheriton School of Computer Science\n\nWe present results obtained in the context of generative neural models specifically autoencoders utilizing standard results from coding theory. The methods are fairly elementary in principle, yet, combined with the ubiquitous practice of Batch Normalization in these models, yield excellent results when it comes to comparing with rival autoencoding architectures. In particular, we resolve a split that arises when comparing two different types of autoencoding models VAEs versus regularized deterministic autoencoders often simply called RAEs (Regularized Auto Encoder). The latter offer superior performance but lose guarantees on their latent space. Further, in the latter, a wide variety of regularizers are applied for excellent performance ranging from L2 regularization to spectral normalization. We, on the other hand, show that a simple entropy like term suffices to kill two birds with one stone that of offering good performance while keeping a well behaved latent space. \n\nThe primary thrust of the thesis exactly consists of a paper presented at UAI 2020 on these matters, titled Batch norm with entropic regularization turns deterministic autoencoders into generative models. This was a joint work with Abdullah Rashwan who was at the time with us at Waterloo as a postdoctoral associate, and is now at Google, and my supervisor, Pascal Poupart. This constitutes chapter 2. Extensions on this that relate to batch norms interplay with adversarial examples are in chapter 3. An overall overview is presented in chapter 1, which serves jointly as an introduction.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200821T143000Z
UID:2020_cb79db15c8c2ec312d527e00f78a4bfc.wnotice@math.uwaterloo.ca
DTSTART:20200821T143000Z
DTEND:20200821T153000Z
SUMMARY:Optimal supermartingales for anytime-valid sequential testing (Seminar)
LOCATION:Online
DESCRIPTION:Optimal supermartingales for anytime-valid sequential testing\nMartin Larsson, Carnegie Mellon University\n\nStatistical testing is `anytime-valid if the decision to stop or continue an experiment can depend on anything that has been observed so far, without compromising statistical error guarantees. For instance, suppose that a promising but inconclusive study receives funding to gather additional data. Then standard p-value analysis is invalidated, but anytime-valid testing is not. A recent approach to anytime-valid testing views a test statistic as a bet against the null hypothesis. These bets are constrained to be supermartingales - hence unprofitable - under the null, but designed to be profitable under the relevant alternative hypotheses. This perspective opens the door to using tools from financial mathematics. In this talk I will explain how notions such as supermartingale measures, fork-convexity, the optional decomposition theorem, and universal portfolios can be used to design optimal supermartingales for anytime-valid sequential testing. (This talk is based on ongoing work with Aaditya Ramdas (CMU) and Johannes Ruf (LSE).)
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200821T170000Z
UID:2020_94b967a76058be8d50b36db40ffe81cc.wnotice@math.uwaterloo.ca
DTSTART:20200821T170000Z
DTEND:20200821T180000Z
SUMMARY:Deterministic Reduction of Integer Nonsingular Linear System Solving to Matrix Multiplication (Symbolic Computation Group PhD Seminar)
LOCATION:Online PhD seminar
DESCRIPTION:Deterministic Reduction of Integer Nonsingular Linear System Solving to Matrix Multiplication\nStavros Birmpilis, PhD candidate, David R. Cheriton School of Computer Science\n\nWe present a deterministic reduction to matrix multiplication for the problem of linear system solving: given as input a nonsingular $A \in \Z^{n \times n}$ and $b \in \Z^{n \times 1}$, compute $A^{-1}b$. The algorithm we give computes the minimal integer $e$ such that all denominators of the entries in $2^eA^{-1}$ are relatively prime to $2$. Then, for a $b$ that has entries with bitlength $O(n)$ times as large as the bitlength of entries in $A$, we give an algorithm to produce the $2$-adic expansion of $2^eA^{-1}b$ up to a precision high enough such that $A^{-1}b$ over $\Q$ can be recovered using rational number reconstruction. Both $e$ and the 2-adic expansion can be computed in $O(\MM(n,\log n + \log ||A||) \times (\log n) (\log n + \loglog ||A||))$ bit operations. Here, $||A||= \max_{ij} |A_{ij}|$ and $\MM(n,d)$ is the cost to multiply together, modulo $2^d$, two $n \times n$ integer matrices. \n\nOur approach is based on the previously known reductions of linear system solving to matrix multiplication which use randomization to find an integer lifting modulus $X$ that is relatively prime to $\det A$. Here, we derandomize by first computing a permutation $P$, a unit upper triangular $M$, and a diagonal $S$ with $\det S$ a power of two, such that $U := APMS^{-1}$ is an integer matrix with $2 \perp \det U$. This allows our modulus $X$ to be chosen a power of $2$. \n\nTo join this PhD seminar on Zoom, please go to \n\nMeeting ID
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200821T180000Z
UID:2020_e1c81b007cbba779ece4e65731ec53c2.wnotice@math.uwaterloo.ca
DTSTART:20200821T180000Z
DTEND:20200821T190000Z
SUMMARY:Analysis of Randomized Algorithms in Real Algebraic Geometry (Symbolic Computation Group Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Analysis of Randomized Algorithms in Real Algebraic Geometry\nJesse Elliott, Masters candidate, David R. Cheriton School of Computer Science\n\nConsider the problem of computing at least one point in each connected component of a smooth real algebraic set. This is a basic and important operation in semi-algebraic geometry. It gives an upper bound on the number of connected components of the algebraic set, it can be used to decide whether or not the algebraic set has real solutions, and it is also used as a subroutine in many higher level algorithms. \n\nWe consider an algorithm for this problem by Safey El Din and Schost: Polar varieties and computation of one point in each connected component of a smooth real algebraic set (ISSAC03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model, and the analysis of the bit complexity and the error probability were left for future work. \n\nWe also consider another algorithm that solves a special case of the problem. Namely, when the algebraic set is a compact hypersurface. \n\nWe determine the bit complexity and error probability of these algorithms. Our main contribution is a quantitative analysis of several genericity statements, such as Thoms weak transversality theorem and Noether normalization properties for polar varieties. Furthermore, in doing this work, we have developed techniques that can be used in the analysis of further randomized algorithms in real algebraic geometry, which rely on related genericity properties. \n\nTo join this presentation on Zoom, please go to \n\nMeeting ID
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200821T193000Z
UID:2020_1d60df4cae9137f7594c9ecca2c6b70d.wnotice@math.uwaterloo.ca
DTSTART:20200821T193000Z
DTEND:20200821T203000Z
SUMMARY:An Algorithmic Reduction Theory for Binary Codes: LLL and more (Tutte Colloquium Colloquium)
LOCATION:Zoom (details below)
DESCRIPTION:An Algorithmic Reduction Theory for Binary Codes: LLL and more\nLéo Ducas, Centrum Wiskunde & Informatica (CWI)\n\nJoint work with Thomas Debris-Alazard and Wessel van Woerden \n\nLattice reduction is the task of finding a basis of short and somewhat orthogonal vectors of a given lattice. In 1985 Lenstra, Lenstra and Lovasz proposed a polynomial time algorithm for this task, with an application to factoring rational polynomials. Since then, the LLL algorithm has found countless application in algorithmic number theory and in cryptanalysis. \n\nThere are many analogies to be drawn between Euclidean lattices and linear codes over finite fields. In this work, we propose to extend the range of these analogies by considering the task of reducing the basis of a binary code. In fact, all it takes is to choose the adequate notion mimicking Euclidean orthogonality (namely orthopodality), after which, all the required notions, arguments, and algorithms unfold before us, in quasi-perfect analogy with lattices. \n\nMeeting ID: 865 3269 0258 Passcode: ducas
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T140000Z
UID:2020_d2e239a2effa4a2d464b31c8cfa534f6.wnotice@math.uwaterloo.ca
DTSTART:20200824T140000Z
DTEND:20200824T150000Z
SUMMARY:Personality Traits of GitHub Maintainers and Their Effects on Project Success (Software Engineering Research Group Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Personality Traits of GitHub Maintainers and Their Effects on Project Success\nSeonghu (Alex) Yun, Masters candidate, David R. Cheriton School of Computer Science\n\nOnline collaborative environments have become important virtual workplaces for developers to work on a common problem. GitHub is an example of such environment that hosts a wealth of open source software projects. Questions such as Who contributes to successful projects? and What are the characteristics of lead developers? require further investigations. \n\nWe qualitatively identify 211 maintainers in 25 maintained repositories and 23 unmaintained repositories in GitHub. We measure their Big Five personality traits (Openness, Conscientiousness, Extraversion, Agreeableness, Neuroticism) as the weighted sum of their Linguistic Inquiry and Word Count (LIWC) dimensions. Our results indicate that maintainers and non-maintainers are significantly different in virtually all personality traits except in Neuroticism. Maintainers in maintained repositories tend to be more open, but less extraverted and less agreeable than maintainers in unmaintained repositories. In addition to Agreeableness being a significant predictor, our analysis suggest that the success of a repository may be explained by the absolute differences in personality traits between maintainers and non-maintainers. \n\nIn sum, our work aims to understand the role of a maintainer and the effects of personality traits on project success. Our findings have direct implications such that developers can be more cognizant of their behaviours, as well as their colleagues, which can result in better collaboration. By highlighting personality differences, we show that studying social and psychological constructs can be invaluable in understanding group dynamics during collaborative process. \n\nTo join this masters thesis presentation virtually on WebEx, please go to \n\nPassword
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T150000Z
UID:2020_d47e0c3de122540f947eb3a328339b95.wnotice@math.uwaterloo.ca
DTSTART:20200824T150000Z
DTEND:20200824T160000Z
SUMMARY:Implementation of the Metal Privileged Architecture (Systems and Networking Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Implementation of the Metal Privileged Architecture\nFatemeh Hassani, Masters candidate, David R. Cheriton School of Computer Science\n\nThe privileged architecture of modern systems is usually expanded using hardware-related approaches like instruction set extensions. These extensions are strongly tied to a particular microarchitecture and operating system developers are not able to customize the privileged mechanisms. As a result, they have to work around fixed abstractions provided by the processor to implement desired functionalities. Programmable approaches such as PALcode also remain heavily tied to the hardware and modifying the privileged architecture has to be done by the processor manufacturer. To accelerate operating system development and enable rapid prototyping of new operating system designs and security models, we need to rethink the privileged architecture design. \n\nWe present a new abstraction called Metal which is decoupled from the microarchitecture. It provides system developers with a general-purpose and easy-to-use interface to build a variety of applications that range from performance measurements to novel privilege models. We implement a simplified version of the Alpha architecture which we call Microalpha and build a prototype of Metal on this architecture. Micoalpha is a five-stage pipelined processor with a multi-level cache hierarchy. We then implement a few applications such as system calls and transactional memory on this architecture to show the practicality of Metal.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T153000Z
UID:2020_c5409f28f33619675e3703d68cba4589.wnotice@math.uwaterloo.ca
DTSTART:20200824T153000Z
DTEND:20200824T163000Z
SUMMARY:Laplacian Quantum Fractional Revival On Graphs (Algebraic Graph Theory Seminar)
LOCATION:Zoom
DESCRIPTION:Laplacian Quantum Fractional Revival On Graphs\nBobae Johnson, August Liu, Malena Schmidt, Neo Yin, York University\n\nhttps://us02web.zoom.us/j/86564623661?pwd=T1h6eGdHZTlVTDJYdkJOcXNlQ2l3QT09 Meeting ID: 865 6462 3661 Password: 697900\n\nGiven a set of quantum bits, we can model their interactions using graphs. The continuous-time quantum walks on a graph can be viewed as the Schrödinger dynamics of a particle hopping between adjacent vertices. In this talk, the transition matrix of the continuous-time quantum walk is given by $e^{-itL}$, where $L$ is the graphs Laplacian matrix. \n\nWe study the phenomenon of fractional revival (LaFR), useful in generating entanglement between two quantum bits. In particular, we characterize LaFR using spectral properties of the graph and present an infinite family of examples. We then prove the non-existence of LaFR on trees. Finally, we proceed to study an approximate version of LaFR called pretty good fractional revival on special families of trees. \n\nThis is joint work under the Fields Institute Undergraduate Summer Research Program 2020.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T170000Z
UID:2020_7fc425e66401f65bd21acaa143fc7f26.wnotice@math.uwaterloo.ca
DTSTART:20200824T170000Z
DTEND:20200824T180000Z
SUMMARY:Towards Effective Utilization of Pretrained Language Models Knowledge Distillation from BERT (Artificial Intelligence Lab Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Towards Effective Utilization of Pretrained Language Models Knowledge Distillation from BERT\nLinqing Liu, Masters candidate, David R. Cheriton School of Computer Science\n\nIn the natural language processing (NLP) literature, neural networks are becoming increasingly deeper and more complex. Recent advancements in neural NLP are large pretrained language models (e.g., BERT), which lead to significant performance gains in various downstream tasks. Such models, however, require intensive computational resource to train and are difficult to deploy in practice due to poor inference-time efficiency. In this thesis, we are trying to solve this problem through knowledge distillation (KD), where a large pretrained model serves as teacher and transfers its knowledge to a small student model. We also want to demonstrate the competitiveness of small, shallow neural networks. \n\nWe propose a simple yet effective approach that transfers the knowledge of a large pretrained network (namely, BERT) to a shallow neural architecture (namely, a bidirectional long short-term memory network). To facilitate this process, we propose heuristic data augmentation methods, so that the teacher model can better express its knowledge on the augmented corpus. Experimental results on various natural language understanding tasks show that our distilled model achieves high performance comparable to the ELMo model (a LSTM based pretrained model) in both single-sentence and sentence-pair tasks, while using roughly 60100 times fewer parameters and 815 times less inference time. \n\nAlthough experiments show that small BiLSTMs are more expressive on natural language tasks than previously thought, we wish to further exploit its capacity through a different KD framework. We propose MKD, a Multi-Task Knowledge Distillation Approach. It distills the student model from different tasks jointly, so that the distilled model learns a more universal language representation by leveraging cross-task data. Furthermore, we evaluate our approach on two different student model architectures, one is bi-attentive LSTM based network, another uses three layer Transformer models. For LSTM based student, our approach keeps the advantage of inference speed while maintaining comparable performance as those specifically designed for Transformer methods. For our Transformer-based student, it does provide a modest gain, and outperforms other KD methods without using external training data.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T190000Z
UID:2020_baeb67c6bbfc103708f3e8c3aa2bb511.wnotice@math.uwaterloo.ca
DTSTART:20200824T190000Z
DTEND:20200824T200000Z
SUMMARY:AutoCPA: Automatic Continuous Profiling and Analysis (Systems and Networking Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:AutoCPA: Automatic Continuous Profiling and Analysis\nZahra Rezapour Siahgourabi, Masters candidate, David R. Cheriton School of Computer Science\n\nPoor data locality continues to be a performance bottleneck in todays popular applications. The hierarchy of caches exiting in modern processors reduces data access latency from the main memory. However, inefficient cache utilization results in data cache miss overhead. Applications usually make frequent accesses to far away data that neglects the locality in the memory hierarchy. One approach to boost applications performance is to reorder structure fields in a manner that efficiently utilizes the cache. To do so, extensive program-wide information is needed to gain insight about the access frequencies and access patterns of data. \n\nThis thesis introduces AutoCPA, which exploits hardware performance monitoring counters to find optimization opportunities in target applications, and provides insightful guidance for structure reordering. This system is a low-overhead and easy-to-use toolchain that uses a sampling-based approach to collect and analyze memory traces. Moreover, it generates a prioritized set of reordering that can improve cache utilization and locality. The recommendations for the optimal structure layout provided by this tool are obtained from multiple cache analysis algorithms implemented in AutoCPA. Performance results obtained by running AutoCPA on two widely-used applications, Redis and Memcached, illustrate the benefit of the implementation. These results confirm the general performance improvement of applications, with up to 10% Instruction Per Cycle increase in Redis commands.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200824T190000Z
UID:2020_d103a9b2b12bedd3f474c079aee20fdf.wnotice@math.uwaterloo.ca
DTSTART:20200824T190000Z
DTEND:20200824T200000Z
SUMMARY:Ideal clutters and dyadic fractional packings (Graphs and Matroids Seminar)
LOCATION:Zoom (details below)
DESCRIPTION:Ideal clutters and dyadic fractional packings\nAhmad Abdi, London School of Economics\n\nA clutter is a finite family of finite sets where no set contains another one. Clutters form a very broad class of objects generalizing graphs and matroids in more than one way, and are also accompanied by notions of duality (more specifically, the blocking relation) and minor theory. \n\nMost questions about clutters can be traced back to the study of three key parameters: the covering number, the fractional packing number, and the packing number, ordered from largest to smallest. The first two parameters are known to be equal, and efficiently computable, for the class of ideal clutters, an important class of clutters rooted in Combinatorial Optimization and Polyhedral Combinatorics. \n\nIn 1975, Seymour conjectured that for every ideal clutter, the fractional packing number can be attained not just by a fractional vector, but by a vector whose entries are dyadic rational numbers. As a first step, we prove this conjecture in the case when the fractional packing number is equal to 2; we also provide a quasi-polynomial time algorithm for finding the dyadic vector. Our proof techniques rely on the key insight that ideal clutters are so-called clean, i.e. they forbid two infinite classes of clutters as a minor, one coming from projective planes, and another coming from odd holes. \n\nIn this self-contained talk, after contextualizing Seymours conjecture, I shall motivate clean clutters and survey two important subclasses other than ideal clutters, namely, binary clutters (coming from binary matroids), and clutters without an intersecting family as a minor. \n\nBased on joint work with Gérard Cornuéjols, Bertrand Guenin, and Levent Tunçel. \n\nZoom: https://us02web.zoom.us/j/92293499003 Password: abdi1
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200826T140000Z
UID:2020_dbeb29ba3a44ccce3e6bb6db84d571ff.wnotice@math.uwaterloo.ca
DTSTART:20200826T140000Z
DTEND:20200826T150000Z
SUMMARY:Monotonicity Testing for Boolean Functions over Graph Products (Algorithms and Complexity Group Master's Thesis Presentation)
LOCATION:Online presentation
DESCRIPTION:Monotonicity Testing for Boolean Functions over Graph Products\nZhengkun Chen, Masters candidate, David R. Cheriton School of Computer Science\n\nWe establish a directed analogue of Chung and Tetalis isoperimetric inequality for graph products. We use this inequality to obtain new bounds on the query complexity for testing monotonicity of Boolean-valued functions over products of general posets.
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200827T153000Z
UID:2020_c1064cce5ef835cd4799a3f90651e832.wnotice@math.uwaterloo.ca
DTSTART:20200827T153000Z
DTEND:20200827T163000Z
SUMMARY:LegRoast: Efficient post-quantum signatures from the Legendre PRF (Cryptography Seminar)
LOCATION:Online (details below)
DESCRIPTION:LegRoast: Efficient post-quantum signatures from the Legendre PRF\nEdward Eaton, University of Waterloo\n\nWe introduce an efficient post-quantum signature scheme that relies on the one-wayness of the Legendre PRF. This "LEGendRe One-wAyness SignaTure" (LegRoast) builds upon the MPC-in-the-head technique to construct an efficient zero-knowledge proof, which is then turned into a signature scheme with the Fiat-Shamir transform. Unlike many other Fiat-Shamir signatures, the security of LegRoast can be proven without using the forking lemma, and this leads to a tight (classical) ROM proof. We also introduce a generalization that relies on the one-wayness of higher-power residue characters; the "POwer Residue ChaRacter One-wAyness SignaTure" (PorcRoast). LegRoast outperforms existing MPC-in-the-head-based signatures (most notably Picnic/Picnic2) in terms of signature size and speed. Moreover, PorcRoast outperforms LegRoast by a factor of 2 in both signature size and signing time. For example, one of our parameter sets targeting NIST security level I results in a signature size of 7.2 KB and a signing time of 2.8ms. This makes PorcRoast the most efficient signature scheme based on symmetric primitives in terms of signature size and signing time. \n\nMeeting link: https://bbb.crysp.org/b/dou-jk2-z4j (using BigBlueButton) with Access code: 281013
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200828T193000Z
UID:2020_daa8fc8f7703b89bb11ebe3df3ed83b5.wnotice@math.uwaterloo.ca
DTSTART:20200828T193000Z
DTEND:20200828T203000Z
SUMMARY:Pure pairs (Tutte Colloquium Colloquium)
LOCATION:Zoom (details below)
DESCRIPTION:Pure pairs\nSophie Spirkl, University of Waterloo\n\nA pure pair in a graph G is a pair of subsets A and B of the vertex set such that between A and B, either all edges or no edges are present in G. This concept was first introduced in connected with the Erdos-Hajnal conjecture, but has since developed a life of its own. I will give an overview of results and open questions on pure pairs. \n\nBased on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour. \n\nMeeting ID: 859 0582 8819 Passcode: spirkl
END:VEVENT
BEGIN:VEVENT
DTSTAMP:20200917T150000Z
UID:2020_ee53413398fd89e971dc9f99c72bea8d.wnotice@math.uwaterloo.ca
DTSTART:20200917T150000Z
DTEND:20200917T160000Z
SUMMARY:Where's the Question? A Multi-channel Deep Convolutional Neural Network for Question Identification in Textual Data (Human-Computer Interaction PhD Seminar)
LOCATION:Online
DESCRIPTION:Where's the Question? A Multi-channel Deep Convolutional Neural Network for Question Identification in Textual Data\nGeorgios Michalopoulos, David R. Cheriton School of Computer Science\n\nIn this study, we investigated the key characteristics exhibited by questions in medical narrative data (e.g., review logs) in order to uncover the most impactful variables on data quality issues during the data entry and review process of a real-word clinical system. \n\nMore specifically, we evaluated the performance of traditional rule-based and learning-based methods for detecting question sentences. Next, we proposed a novel multi-channel deep convolutional neural network architecture designed for the purpose of separating real questions that expect an answer (information or help) about an issue from sentences that are not questions, as well as from questions referring to an issue mentioned in a nearby sentence (e.g., can you clarify this?), which we will refer as "c-questions". Finally, we performed a comprehensive performance comparison analysis of the proposed multi-channel deep convolutional neural network against other deep neural networks. We illustrated the efficacy of the proposed network which achieved the best F1 score on a benchmark dataset of medical logs about renal patients and on a general domain dataset.
END:VEVENT
END:VCALENDAR