BEGIN:VCALENDAR
X-WR-CALNAME:Webnotice (Combinatorics and Optimization)
X-WR-CALDESC:Webnotice (Combinatorics and Optimization) 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: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: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: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: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: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
END:VCALENDAR