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:6a3cc74af0eb4 DTSTART;TZID=America/Toronto:20260626T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260626T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-rian-neogi-multidimensional-budget SUMMARY:CombOpt ReadingGroup - Rian Neogi-Multidimensional Budget-feasible\ nmechanism design CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Rian Neogi\n\nAFFILIATION:\n University of Waterlo o\n\nLOCATION:\n MC 6029\n\nABSTRACT:  \n\nIn budget-feasible mechanism design\, there is a set of items U. A\nbuyer wishes to purchase a set of i tems from the sellers of maximum\nvalue\, where the value of a subset S of items is provided by a\nvaluation function v. Each element e is held by a distinct seller\, who\nincurs a private cost c_e for supplying her item. The buyer also has a\nbudget of B on the total payments made to the seller s. The private\ncosts c_e are known only to the sellers\, and not to the b uyer. Each\nseller e reports a cost r_e to the mechanism\, which may or ma y not be\nequal to her true cost c_e. As a result\, a seller may choose to \nmisreport her cost if she sees that she is better off when doing so\n(fo r example\, the mechanism might be giving her a higher payment under\nthe misreported cost).  \nBudget-feasible mechanisms have been well-studied o ver the past 15\nyears. In this talk\, we will introduce a generalization of the\nsetting\, where each agent can now hold multiple items. This\ngene ralizes the problem into what is known as a multi-parameter\ndomain\, whic h brings about several complications\, including strong\nimpossibility res ults with respect to the typical benchmark of the\nalgorithmic optimum. In lieu of these impossibility results\, we\npropose a novel benchmark for t he setting. We prove positive results\nwith respect to this new benchmark\ , qualitatively matching prior\nresults in single-parameter budget-feasibl e mechanism design. \nThis is joint work with Kanstantsin Pashkovich and C haitanya Swamy\,\nand is to appear in EC 2026. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b00e4a DTSTART;TZID=America/Toronto:20260702T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260702T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-jeronimo-1 SUMMARY:Algebraic and Enumerative combinatorics seminar -Jerónimo\nValenci a-Porras-Type C multiline queues and the open-boundary TASEP CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Jerónimo Valencia-Porras\n\nAFFILIATION:\n Universi ty of Waterloo\n\nLOCATION:\n MC 6460\n\nABSTRACT: The totally asymmetric simple exclusion process (TASEP) is\na finite Markov chain of particles h opping between adjacent sites on a\none-dimensional lattice. The multispec ies TASEP is a generalization in\nwhich particles have different types. Th ese processes have interesting\nconnections to algebraic combinatorics: th e stationary distribution of\nthe TASEP on a circle is connected to Macdon ald polynomials at t=0\,\nwhereas the stationary distribution of the open- boundary TASEP is\nconnected to Koorwinder polynomials at t=0.\n\nMultilin e queues were introduced by Ferrari and Martin (2007) to\ncompute the stat ionary distribution of the multispecies TASEP on a\ncircle. It has been a long-standing open problem to find a\ncombinatorial formula for the statio nary distribution of the\nmultispecies TASEP with open boundaries. Recentl y\, we studied the\ncombinatorics of Ferrari–Martin multiline queues usi ng type A\ncrystals. In this talk\, we use crystals of type C to construct an\nanalog of multiline queues and give a combinatorial formula for the\n stationary distribution of the multispecies open-boundary TASEP for a\ncer tain specialization of the boundary parameters. This is joint work\nwith O lya Mandelshtam.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGR OUND AT\nBEGINNING GRADUATE LEVEL STARTING AT 1:30PM IN MC 5417. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b021de DTSTART;TZID=America/Toronto:20260626T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260626T113000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-bruce-xu-and-maggie-simmons-hqc SUMMARY:Crypto Reading Group - Bruce Xu and Maggie Simmons-HQC Implementati on\nand Optimisation CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Bruce Xu and Maggie Simmons\n\nAFFILIATION:\n Univ ersity of Waterloo\n\nLOCATION:\n MC 5417\n\nABSTRACT:\n\nThis week will cover the implementation and optimization of key\nsub-routines within HQC. We will begin by examining the implementation\nof Reed-Solomon decoding w ithin HQC\, which includes the BCH-view of\nsyndromes\, weighted Newton's identity\, the Berlekamp-Massey algorithm\,\nand more. We will also discus s high-performance polynomial\nmultiplication via the Karatsuba algorithm and hardware optimization. \nReferences: [3] and [4] \n[3] J. Dong\, Y. Ho u\, S. Wang\, L. Sha\, F. Xiao\, Z. Dong\, and J. Lin.\nHIGH: Harnessing G PU Parallelism for Optimized HQC Performance. In\nIACR Cryptology ePrint A rchive\, 2026. \n[4] HQC Team. Hamming Quasi-Cyclic (HQC)\, NIST Submissio n\, 2025. \nA week-by-week plan is outlined at the following\nlink: https ://www.leonardocolo.com/seminars/Spring26.html. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b03639 DTSTART;TZID=America/Toronto:20260626T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260626T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-rutger-campbell-excluded-minors-z3-gainable SUMMARY:Tutte Colloquium -Rutger Campbell-The excluded minors for Z3 -gaina ble\nbiased graphs CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Rutger Campbell\n\nAFFILIATION:\n Institute for Basi c Science\, Korea\n\nLOCATION:\n MC 5501\n\nABSTRACT: A biased graph is a pair (G\,B) consisting of a graph G and\na collection B of “balanced \" cycles in G. Biased graphs arise\nnaturally as the cycles that have ide ntity weight in a group-labelling\nof arcs where opposite arcs have invers e weight. I present an excluded\nminor characterization for biased graphs that have such a\ngroup-labelling over Z3. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b04316 DTSTART;TZID=America/Toronto:20260625T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260625T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-mike-0 SUMMARY:Algebraic and Enumerative combinatorics seminar -Mike Cummings-Webs \nand smooth components of two column Springer fibers CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Mike Cummings\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 6460\n\nABSTRACT:  When you encounter an algebraic variety in the wild\, you\nmight ask: What do its components look like? Wh ich components are\nsmooth? How do the components intersect? For Springer fibres\, answers\nto these questions are only known in some very special c ases. This is\nparticularly surprising because other aspects Springer fibr es have\nbeen studied for the past 50 years and they appear throughout\nco mbinatorics and adjacent areas. For just one example:\nHall–Littlewood p olynomials can be obtained from the cohomology of\nSpringer fibres by taki ng graded Frobenius characteristic.\n\nOne classical theorem says that the components of Springer fibers are\nindexed by standard Young tableaux. In this talk\, we will discuss the\nbenefits of instead using webs to index the components in two cases:\nthe \"two row\" case\, and our recent contri butions in the \"two column\"\ncase. We will see that in these cases\, web s both characterize and\ndescribe the smooth components of Springer fibres \, and give a\ngeometric interpretation of rotation of webs.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUND AT\nBEGINNING GRADUATE LE VEL STARTING AT 1:30PM IN MC 5417. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b05134 DTSTART;TZID=America/Toronto:20260619T123000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260619T133000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-kevin-cheung-home-away-pattern-set SUMMARY:CombOpt ReadingGroup - Kevin Cheung-The home-away pattern set\nfeas ibility problem in sports scheduling CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Kevin Cheung\n\nAFFILIATION:\n Carleton university \n\nLOCATION:\n DC 2568\n\nABSTRACT:  In sports scheduling\, a single ro und-robin schedule for\n$2n$ teams consists of $2n-1$ rounds so that each team plays each of\nthe other $2n-1$ teams exactly once across the round s and that each\nteam plays exactly one game in each round. With each gam e played at\nthe venue of one of the two opposing teams\, a table of home -away\npatterns can be extracted from a single round-robin schedule so\nth at the $(i\,j)$-entry indicates whether team $i$ plays a home game\nor an away game in round $j$. \n\nThe home-away pattern set feasibility probl em turns the process around\nand asks: Given an arbitrarily constructed t able of home-away\npatterns\, is there a single round-robin schedule comp atible with it?\nEven though single round-robin schedules do not often ar ise in\npractice\, it is not uncommon in sports scheduling to first speci fy\nwhen teams should play home games and then decide on which opponents\ nthey should play against. Being able to efficiently determine if a\nhome -away pattern set is feasible can help with quick generation of\npotentia l schedules.\n\nAs of today\, it is not known if the problem is NP-complet e. This talk\nwill focus on polynomial-time checkable necessary condition s for\nfeasibility and conditions under which they are also sufficient. S ome\npersonal reflections on the problem will conclude the talk. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b05e8d DTSTART;TZID=America/Toronto:20260619T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260619T113000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-mojtaba-fadavi-and-anna-henderson-hqc SUMMARY:Crypto Reading Group - Mojtaba Fadavi and Anna Henderson-HQC PKE/KE M CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Mojtaba Fadavi and Anna Henderson\n\nAFFILIATION:\ n University of Waterloo\n\nLOCATION:\n MC 5417\n\nABSTRACT:\n\nThis sess ion is devoted to the HQC cryptosystem itself\, in both its\npublic-key en cryption and key-encapsulation forms. We will explain how\nthe scheme work s\, describe its main components and design choices\, and\ndiscuss the cor responding security analysis\, including comments on the\npost-quantum set ting. By this stage\, the reading group should have\nenough background to appreciate both the structure and the rationale\nof HQC. \nReferences: [1] and [4] \n[1] C. Aguilar-Melchor\, O. Blazy\, J.-C. Deneuville\, P. Gabor it and G.\nZémor. Efficient Encryption From Random Quasi-Cyclic Codes. In IEEE\nTransactions on Information Theory\, vol. 64\, no. 5\, pp. 3927–3 943\,\n2018. \n[4] HQC Team. Hamming Quasi-Cyclic (HQC)\, NIST Submission\ , 2025. \nA week-by-week plan is outlined at the following\nlink: https:/ /www.leonardocolo.com/seminars/Spring26.html. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b06d98 DTSTART;TZID=America/Toronto:20260612T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260612T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-sina-kalantarzadeh-designing-ptas SUMMARY:CombOpt ReadingGroup - Sina Kalantarzadeh-Designing a PTAS for\nPhi losopher Inequalities under Constant-Depth Laminar Constraints CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Sina Kalantarzadeh\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT:\n\nIn stochastic online opti mization\, prophet inequalities under matroid\nconstraints have been studi ed extensively. The philosopher\nbenchmark(optimal online strategy) is wea ker than the prophet\nbenchmark\, but it is still not fully understood how well one can\ncompete against the optimal online strategy using polynomia l\ncomputational power. Pashkovich and Dehaan showed that it is\nimpossibl e to design a PTAS for computing optimal online strategy in\ngraphic matro ids. \nIn this talk we consider a special class of matroid constraints so\ ncalled laminar matroids. There are (n) items arriving in a known\norder\, and each item has a probability distribution over its realized\nvalue. We are also given a collection of bins on these items\, where\neach bin (B) has a capacity (c(B)). The bins form a laminar family.\nWhen an item arriv es\, its value is revealed\, and the algorithm must\nimmediately decide wh ether to accept or reject it\, while respecting\nall laminar capacity cons traints. The goal is to maximize the expected\ngain of the total value of the accepted items and compare it to the\ngain of the optimal online polic y\, rather than to the prophet.\nAnari et al. designed a polynomial-time a pproximation scheme(PTAS) for\nconstant-depth instances\, meaning that eac h item belongs to only a\nconstant number of bins. Their approach uses the fact that the optimal\nonline policy can be formulated as a linear progra m(LP). We will first\nexamine this LP in the simple case where the laminar family consists\nof a single bin of capacity one. In general\, however\, the LP has\nexponential size and therefore cannot be solved directly in po lynomial\ntime. The main idea is to select certain small bins inside the l aminar\nfamily for which the corresponding subproblems are no longer\nexpo nentially large. On these selected parts\, one can use the optimal\nonline policy\, and then combine these local policies to obtain a\nglobal approx imation. It remains open whether one can design a PTAS\nfor general lamina r families.  DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b07c28 DTSTART;TZID=America/Toronto:20260618T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260618T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-scott SUMMARY:Algebraic and Enumerative combinatorics seminar -Scott\nNeville-Eve ntual sign coherence CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Scott Neville\n\nAFFILIATION:\n LACIM\n\nLOCATION:\n MC 6460\n\nABSTRACT: The sign coherence of c-vectors is one of the funda mental\ntheorems of cluster algebras with principal coefficients.  Gekhtm an\nand Nakanishi posed the Asymptotic Sign Coherence Conjecture for\nclus ter algebras with arbitrary coefficients\, which says sign\ncoherence shou ld eventually hold in any sufficiently generic infinite\nmutation sequence .  We prove that for cluster algebras from quivers\nof arbitrary rank\, t heir conjecture holds with probability 1 for a\nrandom mutation sequence.   Our results also establish the conjecture\nin full generality for many families of quivers.  This is joint work\nwith Amanda Burcroff.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUND AT\nBEGINNING GRADUAT E LEVEL STARTING AT 1:30PM IN MC 5417. DTSTAMP:20260625T061435Z END:VEVENT BEGIN:VEVENT UID:6a3cc74b089f9 DTSTART;TZID=America/Toronto:20260612T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260612T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-douglas-stebila-adding-functionality-post SUMMARY:Tutte Colloquium -Douglas Stebila-Adding functionality to post-quan tum\ncryptography with variants of the Fujisaki-Okamoto transform CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Douglas Stebila\n\nAFFILIATION:\n University of Wate rloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: The Fujisaki-Okamoto (FO) transf orm is a fundamental\nbuilding block in new post-quantum cryptography stan dards like NIST's\nML-KEM\, where it is used to convert a weakly secure pu blic key\nencryption scheme into a key encapsulation mechanism (KEM) secur e\nagainst active attackers. In this talk\, we'll explore two approaches\n to add extra security and functionality to post-quantum KEMs by\nenhancing the FO transform. First\, we see how a birthday-style\ncollision argument lets an attacker who collects many ciphertexts\nhalve the security of the FrodoKEM and HQC standards\, and how\nextending the FO transform with pub lic salts thwarts this multi-target\nattack. Second\, we turn to implement ation flaws: for 19 months\, HQC's\nreference implementation effectively s kipped a security-critical\nverification step\, yet basic correctness test s still passed. We show\nhow the principle of \"verifiable verification\"\ , via an extension of\nthe FO transform\, ties security to functionality\, so that an\nimplementation which that skips it visibly breaks. DTSTAMP:20260625T061435Z END:VEVENT END:VCALENDAR