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:20250309T070000 END:DAYLIGHT BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20251102T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:694699cad18a1 DTSTART;TZID=America/Toronto:20251210T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251210T113000 URL:/combinatorics-and-optimization/events/crypto-readi ng-group-bruno-sterner-loquat-post-quantum SUMMARY:Crypto Reading Group -Bruno Sterner-Loquat: Post-quantum signature\ nfrom the Legendre PRF CLASS:PUBLIC DESCRIPTION:Speaker\n Bruno Sterner\n\nAffiliation\n University of ݮƵ \n\nLocation\n MC 5479\n\nABSTRACT: We give an overview of a new Legendre -based signature\nscheme called Loquat that is friendly for SNARK-based a pplications.\nWhile we primarily focus on the constructive applications\, we also\ndiscuss the historical context\, security and cryptanalysis of the\nLegendre PRF. The primary content of the talk is based on\nia.cr/202 4/868. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad2d58 DTSTART;TZID=America/Toronto:20251201T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251201T160000 URL:/combinatorics-and-optimization/events/graphs-and-m atroids-fernanda-rivera-omana SUMMARY:Graphs and Matroids - Fernanda Rivera Omana CLASS:PUBLIC DESCRIPTION:TITLE:Erdős-Pósa theorem for matroids\n\nSPEAKER:\n Fernanda Rivera Omana\n\nAFFILIATION:\n University of ݮƵ\n\nROOM:\n MC 6029\ n\nABSTRACT: We will look at an analogue theorem of the classical\nErdős -Pósa Theorem. We prove a $GF(q)$-representable matroid\nanalogue of Robe rtson and Seymour's theorem that planar graphs have an\nErdős-Pósa prope rty. Given a matroid $N$\, we prove that for every\nmatroid $M$ with bound ed branch width\, $M$ either contains $r$ skew\ncopies of $N$\, or there i s a small perturbation of $M$ that doesn't\ncontain $N$ as a minor. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad3b89 DTSTART;TZID=America/Toronto:20251204T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251204T153000 URL:/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-taylor SUMMARY:Algebraic and enumerative combinatorics seminar-Taylor Brysiewicz CLASS:PUBLIC DESCRIPTION:TITLE: The degrees of Stiefel Manifolds\n\nSpeaker\n Taylor Br ysiewicz\n\nAffiliation\n Western\n\nLocation\n MC 6029\n\nABSTRACT:\n\nTh e set of orthonormal bases for k-planes in R^n is cut out by the\nequation s X*X^T = I\nwhere X is a k x n matrix of variables and I is k x k identi ty. This\nspace\, known as the Stiefel manifold St(k\,n)\, generalizes th e\northogonal group and can be realized as the homogeneous space\nO(n)/O (n-k). Its algebraic closure\ngives a complex affine variety\, and thus\, it has a degree.\n\nI will discuss our derivation of these degrees. Exten ding 2017 work\non the degrees of special orthogonal groups\, joint work with\nFulvio Gesmundo gives a combinatorial formula in terms of\nnon-int ersecting lattice paths.\nThis result relies on representation theory\, co mmutative\nalgebra\, Ehrhart theory\, polyhedral geometry\, and enumerat ive\ncombinatorics.\n\nI will conclude with some open problems inspired by these objects.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGRO UND AT THE\nBEGINNING GRADUATE LEVEL STARTING AT 1:30PM. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad4915 DTSTART;TZID=America/Toronto:20251203T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251203T113000 URL:/combinatorics-and-optimization/events/crypto-readi ng-group-nic-swanson SUMMARY:Crypto Reading Group -Nic Swanson CLASS:PUBLIC DESCRIPTION:TITLE:PRISM: Simple And Compact Identification and Signatures F rom\nLarge Prime Degree Isogenies\n\nSpeaker\n Nic Swanson\n\nAffiliation\ n University of ݮƵ\n\nLocation\n MC 5479\n\nABSTRACT: The problem o f computing an isogeny of large prime degree\nfrom a supersingular ellipti c curve of unknown endomorphism ring is\nassumed to be hard both for class ical as well as quantum computers. \n\nIn this work\, we first build a tw o-round identification protocol whose\nsecurity reduces to this problem. T he challenge consists of a random\nlarge prime q and the prover simply rep lies with an efficient\nrepresentation of an isogeny of degree q from its public key.  \nUsing the hash-and-sign paradigm\, we then derive a signat ure scheme\nwith a very simple and flexible signing procedure and prove it s\nsecurity in the standard model.  \nOur optimized C implementation of t he signature scheme shows that\nsigning is roughly 1.8× faster than all S QIsign variants\, whereas\nverification is 1.4× times slower. The sizes o f the public key and\nsignature are comparable to existing schemes. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad5669 DTSTART;TZID=America/Toronto:20251128T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251128T163000 URL:/combinatorics-and-optimization/events/tutte-colloq uium-euiwoong-lee-0 SUMMARY:Tutte Colloquium - Euiwoong Lee CLASS:PUBLIC DESCRIPTION:TITLE:Asymptotically Optimal Hardness for k-Set Packing and k-M atroid\nIntersection\n\nSPEAKER:\n Euiwoong Lee\n\nAFFILIATION:\n Universi ty of Michigan\n\nLOCATION:\n MC 5501\n\nABSTRACT: For any epsilon > 0\, we prove that k-Dimensional Matching\nis hard to approximate within a fact or of k/(12 + epsilon) for large k\nunless NP \\subseteq BPP. Listed in Ka rp's 21 NP-complete problems\,\nk-Dimensional Matching is a benchmark comp utational complexity problem\nwhich we find as a special case of many cons trained optimization\nproblems over independence systems including: k-Set Packing\, k-Matroid\nIntersection\, and Matroid k-Parity. For all the afor ementioned\nproblems\, the best known lower bound was an Omega(k /log(k))- hardness\nby Hazan\, Safra\, and Schwartz. In contrast\, state-of-the-art\ nalgorithms achieved an approximation of O(k). Our result narrows down\nth is gap to a constant and thus provides a rationale for the observed\nalgor ithmic difficulties. \n\nThe crux of our result hinges on a novel approxi mation preserving\ngadget from R-degree bounded k-CSPs over alphabet size R to\nkR-Dimensional Matching. Along the way\, we prove that R-degree boun ded\nk-CSPs over alphabet size R are hard to approximate within a factor\n Omega_k(R) using known randomised sparsification methods for CSPs. \nJoint work with Ola Svensson and Theophile Thiery DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad64b6 DTSTART;TZID=America/Toronto:20251124T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251124T160000 URL:/combinatorics-and-optimization/events/graphs-and-m atroids-thinula-silva SUMMARY:Graphs and Matroids - Thinula De Silva CLASS:PUBLIC DESCRIPTION:TITLE:Non-uniform Kahn-Kalai: the fractional version\, the dual and its\npower in capturing “thresholds\"\n\nSPEAKER:\n Thinula De Silv a\n\nAFFILIATION:\n University of ݮƵ\n\nROOM:\n MC 6029\n\nABSTRACT: There have been several advancements in the study of\nthresholds in recent years\, including the groundbreaking proof of the\nKahn-Kalai conjecture by Park and Pham. B. Park and Vondrák also\nlater extended this work in t he non-uniform setting (where we allow\ndifferent edges to have different probabilities\, unlike G(n\, p)). In\nmany concrete applications of determ ining thresholds in G(n\, p)\,\n“spread\" is used to prove the 1-stateme nt. In this talk\, we extend\nthe notion of “spread\" in the non-uniform setting to test its power\nin capturing the “threshold\". This talk is based on joint work with\nJane Gao. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad730d DTSTART;TZID=America/Toronto:20251127T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251127T153000 URL:/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-zeus-dantas SUMMARY:Algebraic and enumerative combinatorics seminar-Zeus Dantas E Moura CLASS:PUBLIC DESCRIPTION:TITLE: Algebraic and enumerative combinatorics seminar\n\nSpea ker\n Zeus Dantas E Moura\n\nAffiliation\n University of Wtaerloo\n\nLocat ion\n MC 6029\n\nABSTRACT:\n\nPermuted-basement Macdonald polynomials E_α ^σ(x_1\, ...\, x_n\; q\, t)\nare nonsymmetric generalizations of symmetr ic Macdonald polynomials\nindexed by a composition α and a permutation σ. They can be\ndescribed combinatorially as generating functions over a ugmented\nfillings of shape α and basement σ.\n\nWe construct determini stic and probabilistic bijections on fillings\nthat prove identities rela ting \n\nE_α^σ\, E_α^{σ s_i}\, E_{s_i α}^σ\, and E_{s_i α}^{σ s_i }. \n\nThese identities arise from two operations on the shape and baseme nt:\nswapping adjacent parts of the shape\, which expands\n\nE_α^σ intoE _{s_i α}^σ and E_{s_i α}^{σ s_i}\; and swapping\nadjacent basement en tries\, \n\nwhich gives E_α^σ = E_α^{σ s_i} when α_i = α_{i+1}.\n\nT HERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUND AT THE\nBEGINNIN G GRADUATE LEVEL STARTING AT 1:30PM. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad8114 DTSTART;TZID=America/Toronto:20251119T103000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251119T113000 URL:/combinatorics-and-optimization/events/crypto-readi ng-group-roy-stracovsky SUMMARY:Crypto Reading Group -Roy Stracovsky CLASS:PUBLIC DESCRIPTION:TITLE:Enhancing Anamorphic Cryptography\n\nSpeaker\n Roy Straco vsky\n\nAffiliation\n Georgia Tech\n\nLocation\n MC 5479\n\nABSTRACT: Ana morphic cryptography (Persiano\, Phan\, and Yung\,\nEurocrypt 2022) allows users who share a “double key” to hide\nencrypted messages in ciphert exts and signatures to allow covert\ncommunication under a hypothetical “dictator” who can monitor all\ncommunication or force parties to give up their cryptographic keys in\norder to check for compliance.\n\nIn this talk\, I will present joint work with Joseph Jaeger which\nenhances the s ecurity and functionality of anamorphic cryptography. We\nfirst enhance th e security of anamorphic signatures by proposing two\nparallel notions of unforgeability (against the aforementioned\ndictator or instead a recipien t) which close gaps in existing\ndefinitions termed robustness (Banfi\, Ge gier\, Hirt\, Maurer\, and Rito\,\nEurocrypt 2024) and private anamorphism (Kutylowski\, Persiano\, Phan\,\nYung\, and Zawada\, Crypto 2023). Previo usly proposed anamorphic schemes\ndo not necessarily achieve our new defin itions but can sometimes be\nmade to do so by modifying the scheme or by l everaging stronger\nassumptions on the underlying building blocks. \nFor o ur second enhancement\, we introduce techniques to stealthily\nexchange ke ys via anamorphic cryptosystems\, allowing covert\ncommunication between u sers that do not a priori share a double key.\nWe propose and analyze mult iple protocols in a four-quadrant security\nmodel capturing passive versus active adversaries who may or may not\nperform key compromise. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad8fd6 DTSTART;TZID=America/Toronto:20251117T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251117T160000 URL:/combinatorics-and-optimization/events/graphs-and-m atroids-jonathan-leake-0 SUMMARY:Graphs and Matroids - Jonathan Leake CLASS:PUBLIC DESCRIPTION:TITLE:The Heron-Rota-Welsh conjecture via Lorentzian polynomial s\n\nSPEAKER:\n Jonathan Leake\n\nAFFILIATION:\n University of ݮƵ\n\ nROOM:\n MC 6029\n\nABSTRACT:The Heron-Rota-Welsh conjecture asserts that the\ncharacteristic polynomial of a matroid has log-concave coefficients.\ nThis conjecture was open since the 1970s until it was proven by\nAdiprasi to\, Huh\, and Katz in 2018 using their newly developed\ncombinatorial Hod ge theory. Their proof was groundbreaking\, but rather\ncomplicated. In th is talk\, we will give a proof of this fact using\nLorentzian polynomials\ , which otherwise will use nothing more than\nbasic theory of matroids\, l inear algebra\, and convexity. DTSTAMP:20251220T124250Z END:VEVENT BEGIN:VEVENT UID:694699cad998f DTSTART;TZID=America/Toronto:20251110T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20251110T160000 URL:/combinatorics-and-optimization/events/graphs-and-m atroids-mathieu-rundstrom SUMMARY:Graphs and Matroids - Mathieu Rundstrom CLASS:PUBLIC DESCRIPTION:TITLE:Almost Regular Matroids\n\nSPEAKER:\n Mathieu Rundstrom\n \nAFFILIATION:\n University of ݮƵ\n\nROOM:\n MC 6029\n\nABSTRACT: R egular matroids form an important and extensively studied\nclass of matroi ds and have numerous known descriptions and\ncharacterizations. In the 198 0s\, Truemper gave a constructive\ndescription of the related class of _a lmost regular matroids_:\nnon-regular matroids $M$ such that for every ele ment $e$ of $M$ either\n$M/e$ or $M\\backslash e$ is regular. In this talk \, we present a\ndescription of almost regular matroids in terms of grafts . A\nconsequence of this description is that almost regular matroids have\ nbounded complexity. We outline some of the proof ideas after\nintroducing the necessary background. DTSTAMP:20251220T124250Z END:VEVENT END:VCALENDAR