BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Drupal iCal API//EN X-WR-CALNAME:Events items teaser X-WR-TIMEZONE:America/Toronto BEGIN:VTIMEZONE TZID:America/Toronto X-LIC-LOCATION:America/Toronto BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20260308T070000 END:DAYLIGHT BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20251102T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:69afede824fb9 DTSTART;TZID=America/Toronto:20260313T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260313T113000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-huanhuan-chen-updatable-encryption SUMMARY:Crypto Reading Group - Huanhuan Chen-Updatable Encryption CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Huanhuan Chen\n\nAFFILIATION:\n University of Wate rloo\n\nLOCATION:\n MC 6029\n\nABSTRACT:Updatable encryption (UE) enables a cloud server to update\nciphertexts using client-generated tokens. There are two types of UE:\nciphertext-independent (c-i) and ciphertext-depende nt (c-d). In terms\nof construction and efficiency\, c-i UE utilizes a sin gle token to\nupdate all ciphertexts. The update mechanism relies mainly o n the\nhomomorphic properties of exponentiation\, which limits the efficie ncy\nof encryption and updating. Although c-d UE may seem inconvenient as\ nit requires downloading parts of the ciphertexts during token\ngeneration \, it allows for easy implementation of the Dec-then-Enc\nstructure. This methodology significantly simplifies the construction\nof the update mecha nism. Notably\, the c-d UE scheme proposed by Boneh\net al. (ASIACRYPT’2 0) has been reported to be 200 times faster than\nprior UE schemes based o n DDH hardness\, which is the case for most\nexisting c-i UE schemes. Furt hermore\, c-d UE ensures a high level of\nsecurity as the token does not r eveal any information about the key\,\nwhich is difficult for c-i UE to ac hieve. However\, previous security\nstudies on c-d UE only addressed selec tive security\; the studies for\nadaptive security remain an open problem. \n\nIn this study\, we make three significant contributions to\nciphertext -dependent updatable encryption (c-d UE). Firstly\, we\nprovide stronger s ecurity notions compared to previous work\, which\ncapture adaptive securi ty and also consider the adversary’s\ndecryption capabilities under the adaptive corruption setting.\nSecondly\, we propose a new c-d UE scheme th at achieves the proposed\nsecurity notions. The token generation technique significantly differs\nfrom the previous Dec-then-Enc structure\, while s till preventing key\nleakages. At last\, we introduce a packing technique that enables the\nsimultaneous encryption and updating of multiple message s within a\nsingle ciphertext. This technique helps alleviate the cost of c-d UE\nby reducing the need to download partial ciphertexts during token\ ngeneration. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede8290b0 DTSTART;TZID=America/Toronto:20260312T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260312T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-en umerative-combinatorics-stephan-pfannerer SUMMARY:Algebraic & Enumerative Combinatorics - Stephan\nPfannerer-Rotation -invariant web bases from hourglass plabic graphs CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Stephan Pfannerer\n\nAFFILIATION:\n University of Wa terloo\n\nLOCATION:\n MC 5417\n\nABSTRACT: \n\nIn 1995\, Kuperberg introd uced a remarkable collection of trivalent web\nbases which encode tensor i nvariants of U_q(sl_3). Extending these\nbases to general sl_r has been an open problem ever since. We present\na solution to the r=4 case by introd ucing hourglass plabic graphs\, a\nnew generalization of Postnikov's plabi c graphs. Joint work with\nChristian Gaetz\, Oliver Pechenik\, Jessica Str iker and Joshua Swanson. \nThere will be a pre-seminar presenting relevant background at the\nbeginning graduate level starting at 1:30pm in MC 5417 .\nThere will be a pre-seminar presenting relevant background at the\nbegi nning graduate level starting at 1:30pm in MC 5417. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede829f13 DTSTART;TZID=America/Toronto:20260313T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260313T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-seunghoon-lee-parallel-reversible-pebbling SUMMARY:Tutte Colloquium -Seunghoon Lee-Parallel Reversible Pebbling:\nTime -Space Tradeoffs on DAGs (with Cryptographic Motivation) CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Seunghoon Lee\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 5011\n\nABSTRACT: The (parallel) pebbling game is a useful abstraction for\nanalyzing the resources (e.g.\, space\, space-time \, amortized\nspace-time) needed to evaluate a function f with a static\nd ata-dependency graph G on a (parallel) computer. The underlying\nquestion is purely combinatorial: what tradeoffs does a directed\nacyclic graph (DA G) force between storing intermediate values and\nrecomputing them? This v iewpoint has been particularly influential in\ncryptography\, where many “Memory-Hard Function” (MHF)\nconstructions can be modeled by evaluati ng a fixed DAG.\n\nClassical pebbling\, however\, does not capture an esse ntial constraint\nin quantum/reversible computation: intermediate informat ion cannot be\ndiscarded freely\, so cleanup must respect the dependency s tructure.\nWhile sequential reversible pebbling has been used to study spa ce-time\ntradeoffs in sequential settings\, it does not reflect the space- time\ntradeoffs for parallel quantum/reversible algorithms. To model this\ ,\nwe introduce the parallel reversible pebbling game and use it to\nanaly ze reversible space-time and amortized costs for important graph\nfamilies \, including line graphs and structured DAGs arising in MHF\nconstructions (e.g.\, Argon2i and DRSample). \nThe talk highlights two core results: Fi rst\, we give a lower bound on\nthe reversible amortized space-time cost f or a line graph\, which\nyields a separation between classical and reversi ble pebbling costs\,\nshowing a super-constant (yet sub-polynomial) gap. S econd\, this\noverhead is nevertheless controlled: we show that any classi cal\nparallel pebbling can be transformed into a reversible one with only a\nsub-polynomial loss. This generic transformation serves as a central\nt ool for analyzing broader graph families. \nThe talk will focus on the com binatorial aspects of cryptographic\napplications\; no background in crypt ography is assumed. Based on joint\nwork with Jeremiah Blocki and Blake Ho lman: The Parallel Reversible\nPebbling Game: Analyzing the Post-Quantum S ecurity of iMHFs (TCC\n2022)\, and The Impact of Reversibility on Parallel Pebbling (EUROCRYPT\n2025). DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82a9d3 DTSTART;TZID=America/Toronto:20260309T144500 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260309T154500 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m atroids-taite-lagrange-classes-graphs-sub-linear SUMMARY:Graphs and Matroids - Taite LaGrange-Classes of graphs with sub-lin ear\ntwin-width CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Taite LaGrange\n\nAFFILIATION:\n University of Water loo\n\nROOM:\n MC 5479\n\nABSTRACT:Twin-width is a graph and matrix parame ter introduced in 2021\nby Bonnet\, Kim\, Thomassé\, and Watrigant as ess entially a measure of\nthe 'error' between vertex neighbourhoods over a se ries of vertex\ncontractions. This talk covers some graph classes with unb ounded\ntwin-width. We present a tool for obtaining twin-width bounds in\n general by contracting a graph based on a partition by distinct\nneighbour hoods. For a graph G on n vertices\, we show that if such a\npartition exi sts\, then the twin-width of G is at worst sub-linear with\nrespect to n. We use this to obtain an upper bound on the twin-width\nof interval graphs and of graphs with bounded VC dimension. The latter\nimplies that heredit ary classes have sub-linear twin-width if and only\nif they have bounded V C dimension. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82b603 DTSTART;TZID=America/Toronto:20260306T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260306T113000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-leonardo-colo-cube-isogeny-based SUMMARY:Crypto Reading Group - Leonardo Colò-IS-CUBE: An isogeny-based\nco mpact KEM using a boxed SIDH diagram CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Leonardo Colò\n\nAFFILIATION:\n University of Wat erloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: Isogeny-basedcryptographyisoneo fthecandidatesforpost-\nquantum cryptography. One of the benefits of using isogeny-based\ncryptography is its compactness. In particular\, a key exc hange scheme\nSIDH allowed us to use a 4λ-bit prime for the security para meter λ.\nUnfortunately\, SIDH was broken in 2022 by some studies. After that\,\nsome isogeny-based key exchange and public key encryption schemes have\nbeen proposed\; however\, most of these schemes use primes whose siz es\nare not guaranteed as linearly related to the security parameter λ.\n As far as we know\, the remaining schemes have not been implemented due\nt o the computation of isogenies of high dimensional abelian varieties\,\nor they need to use a “weak” curve (i.e.\, a curve whose\nendomorphism r ing is known) as the starting curve.\n\nIn this study\, we propose a novel compact isogeny-based key encapsula-\ntion mechanism named IS-CUBE via Ka ni’s theorem and a 3-dimensional\nSIDH diagram. A prime used in IS-CUBE is of the size of about 8λ\nbits\, and we can use a random supersingular elliptic curve for the\nstarting curve. The public key of IS-CUBE is about 3 times larger than\nthat of SIKE\, and the ciphertext of IS-CUBE is abou t 4 times larger\nthan that of SIKE from theoretical estimation. In practi ce\, compared\nto FESTA\, the public key of IS-CUBE is slightly larger and its\nciphertext is slightly smaller. \nThe core idea of IS-CUBE comes fro m the hardness of some already known\ncomputational problems and a novel c omputational problem (the Long\nIsogeny with Torsion (LIT) problem)\, whic h is the problem to compute a\nhidden isogeny from two given supersingular elliptic curves and\ninformation of torsion points of relatively small or der. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82c1d6 DTSTART;TZID=America/Toronto:20260306T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260306T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-kathie-cameron-reconfiguration-vertex SUMMARY:Tutte Colloquium -Kathie Cameron-Reconfiguration of Vertex Colourin gs CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Kathie Cameron\n\nAFFILIATION:\n Wilfrid Laurier Uni versity\n\nLOCATION:\n MC 5011\n\nABSTRACT: A k-colouring of a graph is a n assignment of at most k\ncolours to its vertices so that the ends of eac h edge get different\ncolours. We consider two types of “reconfiguration steps” for\ntransforming a given k-colouring into a target k-colouring. The first\nis to change the colour of a vertex to a colour which does not appear\non any of the vertices it is adjacent to. We say that a graph G i s\nrecolourable if for every k greater than its chromatic number\, any\nk- colouring of G can be transformed into any other by these\nreconfiguration steps. The second (more general) type of\nreconfiguration step is Kempe s waps. We call a graph Kempe connected\nif for every k\, any k-colouring ca n be transformed into any other by\nKempe swaps.\n\nWe have characterized the graphs H such that all graphs which don’t\ncontain H as an induced s ubgraph are recolourable\, and done the same\nfor Kempe connectedness. We have shown that modular decomposition and\na stronger version of clique cu tsets can be used to show that certain\nclasses are recolourable. We also give some classes of graphs which\nadmit colourings that are “frozen” with respect to these\nreconfiguration steps. \nThis is joint work with Ma noj Belavadi and parts are also joint with\nElias Hildred\, Owen Merkel an d Dewi Sintiari. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82ce18 DTSTART;TZID=America/Toronto:20260302T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260302T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-kostya-pashkovich-sequential-linear SUMMARY:Tutte Colloquium -Kostya Pashkovich-Sequential Linear Contracts on\ nMatroids CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Kostya Pashkovich \n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: In this talk\, we present se quential contracts under matroid\nconstraints. In the sequential setting\, an agent can take actions one\nby one. After each action\, the agent obse rves the stochastic value of\nthe action and then decides which action to take next\, if any. At the\nend\, the agent decides what subset of taken a ctions to use for the\nprincipal's reward\; and the principal receives the total value of this\nsubset as a reward. Taking each action induces a cer tain cost for the\nagent. Thus\, to motivate the agent to take actions the principal is\nexpected to offer an appropriate contract. A contract descr ibes the\npayment from the principal to the agent as a function of the\npr incipal's reward obtained through the agent's actions. In this work\,\nwe concentrate on studying linear contracts\, i.e. the contracts where\nthe p rincipal transfers a fraction of their total reward to the agent.\nWe assu me that the total principal's reward is calculated based on a\nsubset of a ctions that forms an independent set in a given matroid. We\nestablish a r elationship between the problem of finding an optimal\nlinear contract (or computing the corresponding principal's utility)\nand the so called matro id (un)reliability problem. Generally\, the\nabove problems turn out to be equivalent subject to adding parallel\ncopies of elements to the given ma troid. (Joint work with Jacob\nSkitsko and Yun Xing) DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82da52 DTSTART;TZID=America/Toronto:20260227T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260227T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-graeme-smith-quantum-capacities-and-quantum SUMMARY:Tutte Colloquium -Graeme Smith-Quantum Capacities and Quantum\nSyne rgies CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Graeme Smith\n\nAFFILIATION:\n University of Waterlo o\n\nLOCATION:\n MC 5501\n\nABSTRACT: A central goal of quantum informati on theory is to\ndetermine the capacities of a quantum channel for sending different\nsorts of information.  I’ll highlight the new and fundament ally\nquantum aspects that arise in quantum information theory compared to \nthe classical theory. These include the central role of entanglement\,\n nonadditivity\, and synergies between resources. I will also discuss\nsome challenging open questions that we will have to solve to push the\ntheory forward. \n  DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82e67a DTSTART;TZID=America/Toronto:20260305T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260305T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-en umerative-combinatorics-maria-gillespie-positive SUMMARY:Algebraic & Enumerative Combinatorics - Maria Gillespie-A Positive\ nCombinatorial Rule for Psi Class Products on Multicolored Spaces CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Maria Gillespie\n\nAFFILIATION:\n Colorado State Uni versity\n\nLOCATION:\n MC 5417\n\nABSTRACT: We use a new combinatorial co nstruction and a\nsign-reversing involution to simplify an alternating sum that arises\nnaturally in intersection theory on moduli spaces of curves. In\nparticular\, it is well known that a product of ψ classes on the\nmo duli space M₀\,ₙ-bar\, the most commonly studied compactification\nof the moduli space M₀\,ₙ of choices of n distinct marked points on\nℙ ¹\, is equal to a multinomial coefficient and has many natural\ncombinato rial interpretations.\n\nThere are similar ψ class products on other comp actifications of\nM₀\,ₙ\, including the \"multicolored\" spaces\, in w hich the answer is\na positive integer and yet only signed summation formu las were known.\nWe simplify the alternating sum formula in the multicolor ed case to\ngive a positive combinatorial rule\, and discuss some applicat ions of\nthe formula. This is joint work with Vance Blankers and Jake Levi nson.\nThere will be a pre-seminar presenting relevant background at the\n beginning graduate level starting at 1:30pm in MC 5417. DTSTAMP:20260310T100944Z END:VEVENT BEGIN:VEVENT UID:69afede82f200 DTSTART;TZID=America/Toronto:20260227T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260227T113000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-jack-zhao-post-quantum-pke-unstructured SUMMARY:Crypto Reading Group - Jack Zhao-Post-Quantum PKE from Unstructured \nNoisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich’s LPN CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Jack Zhao\n\nAFFILIATION:\n University of Waterloo \n\nLOCATION:\n MC 6029\n\nABSTRACT: Much of post-quantum PKE from unstru ctured noisy linear\nalgebra relies on LWE or Alekhnovich’s LPN: both as sume samples of\nthe form (A\, As+e) are computationally indistinguishable from (A\, u)\,\nbut with different noise models. LWE uses “short” err ors\, while\nAlekhnovich LPN uses sparse errors. Motivated by uncertainty around\nfuture cryptanalytic advances\, we ask whether one can still obtai n PKE\nfrom noisy linear assumptions even if both LWE and Alekhnovich LPN\ nwere broken. We talk about two new assumptions: Learning with Two\nErrors (LW2E)\, which mixes an LWE-style short error with an LPN-style\nsparse e rror\, and Learning with Short and Sparse Errors (LWSSE)\, which\nuses err ors that are simultaneously short and sparse but denser than\nAlekhnovich LPN. DTSTAMP:20260310T100944Z END:VEVENT END:VCALENDAR