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:20241103T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:68287749d317a DTSTART;TZID=America/Toronto:20250523T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250523T163000 URL:/combinatorics-and-optimization/events/tutte-colloq uium-david-torregrossa-belen SUMMARY:Tutte colloquium-David Torregrossa Belén CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:Splitting algorithms for monotone inclusions with\nminimal dimension\n\nSPEAKER:\n David Torregrossa Belén\n\nAFFILIA TION:\n Center for Mathematical Modeling\, University of Chile\n\nLOCATIO N:\n MC 5501\n\nABSTRACT: Many situations in convex optimization can be mo deled as the\nproblem of finding a zero of a monotone operator\, which ca n be\nregarded as a generalization of the gradient of a differentiable\nc onvex function. In order to numerically address this monotone\ninclusion problem\, it is vital to be able to exploit the inherent\nstructure of th e operator defining it. The algorithms in the family\nof the splitting me thods achieve this by iteratively solving simpler\nsubtasks that are defi ned by separately using some parts of the\noriginal problem.\n\nIn the fi rst part of this talk\, we will introduce some of the\nmost relevant mono tone inclusion problems and present their\napplications to optimization. Subsequently\, we will draw our\nattention to a common anomaly that has p ersisted in the design of\nmethods in this family: the dimension of the u nderlying space\n—which we denote as lifting— of the algorithms abnor mally\nincreases as the problem size grows. This has direct implications on\nthe computational performance of the method as a result of the\nincre ase of memory requirements. In this framework\, we characterize\nthe mini mal lifting that can be obtained by splitting algorithms\nadept at solvin g certain general monotone inclusions. Moreover\, we\npresent splitting m ethods matching these lifting bounds\, and\nthus having minimal lifting.\ n\n \n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749d84f5 DTSTART;TZID=America/Toronto:20250515T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250515T143000 URL:/combinatorics-and-optimization/events/co-reading-g roup-felix-zhou SUMMARY:C&O Reading Group -Felix Zhou CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE: Learning from Coarse Samples\n\nSPEAKER:\n Felix Zhou\n\nAFFILIATION:\n University of À¶Ý®ÊÓƵ\n\nLOCATION:\n MC 6029 \n\nABSTRACT:Coarsening occurs when the exact value of a sample is not\nob served.\nInstead\, only a subset of the sample space containing the exact value\nis known.\nCoarse data naturally arises in diverse fields\, includi ng Economics\,\nEngineering\, Medical and Biological Sciences\, and all ar eas of the\nPhysical Sciences.\nOne of the simplest forms of coarsening is rounding\, where data values\nare mapped to the nearest point on a specif ied lattice.\n\nWe survey applications of coarse learning to regression wi th\nself-selection bias\, regression with second-price auction data\, and\ npresent details of an SGD-based algorithm for coarse Gaussian mean\nestim ation.\n\nBased on joint work with Alkis Kalavasis and Anay Mehrotra\n(htt ps://arxiv.org/abs/2504.07133)\n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749d90a1 DTSTART;TZID=America/Toronto:20250516T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250516T163000 URL:/combinatorics-and-optimization/events/tutte-colloq uium-michael-borinsky SUMMARY:Tutte colloquium-Michael Borinsky CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:Constraining moduli space cohomology by count ing graphs\n\nSPEAKER:\n Michael Borinsky\n\nAFFILIATION:\n Perimeter Inst itute\n\nLOCATION:\n MC 5501\n\nABSTRACT: In 1992\, Kontsevich defined com plexes spanned by graphs.\nThese \ncomplexes are increasingly prominent i n algebraic topology\,\ngeometric \ngroup theory and mathematical physics . For instance\, a 2021 theorem\nby \nChan-Galatius and Payne implies tha t the top-weight cohomology of\nthe \nmoduli space of curves of genus g i s equal to the homology of a\nspecific \ngraph complex. I will present a new theorem on the asymptotic growth \nrate of the Euler characteristic o f this graph complex and explain\nits \nimplication on the cohomology of the moduli space of curves. The\nproof \ninvolves solving a specific grap h counting problem.\n\n \n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749d9c5e DTSTART;TZID=America/Toronto:20250512T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250512T123000 URL:/combinatorics-and-optimization/events/algebraic-gr aph-theory-lorenzo-ciardo SUMMARY:Algebraic Graph Theory-Lorenzo Ciardo CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE: Alice\, Bob\, and colours: An algebraic app roach to quantum\nadvantage\n\nSPEAKER:\n\nLorenzo Ciardo\n\nAFFILIATION:\ n University of Oxford\n\nLOCATION:\n Please contact Sabrina Lato for Zo om link.\n\nABSTRACT: Two-player one-round games exhibit quantum advantag e if the\navailability of quantum resources results in non-classical\ncorr elations between the players' answers\, which allow outperforming\nany cla ssical strategy. The first part of the talk illustrates a link\nbetween (i ) the occurrence of quantum advantage in a game\, and (ii)\nthe complexity of the corresponding classical computational problem.\nIn particular\, I will show that both (i) and (ii) are determined by\nthe same algebraic inv ariants of the game\, known as polymorphisms.\nThis allows transferring me thods from the universal-algebraic theory\nof constraint satisfaction to t he setting of quantum advantage. In\nparticular\, this approach yields a c omplete characterisation of the\noccurrence of quantum advantage for games played on graphs.   \n\nThe second part of the talk outlines recent wor k on the quantum\nchromatic number introduced in\n[Cameron--Montanaro--New man--Severini--Winter'07]. The gap between\nthis parameter and its classic al counterpart is a measure of quantum\nadvantage for the graph colouring game. Using the polymorphic\napproach\, I will show that the maximum gap i s linear when the quantum\nchromatic number makes use of entangled strateg ies on a constant\nnumber of qubits. In contrast\, in the case of unlimite d entanglement\nresources\, I will prove the existence of graphs whose qua ntum\nchromatic number is 3 and whose classical chromatic number is\narbit rarily large\, conditional to the quantum variants of Khot's\nd-to-1 Conje cture [Khot'02] and HÃ¥stad's inapproximability of linear\nequations [HÃ¥s tad'01].\n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749da712 DTSTART;TZID=America/Toronto:20250515T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250515T150000 URL:/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-felix SUMMARY:Algebraic and enumerative combinatorics seminar-Félix Gelinas CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:Source characterization of the hypegraphic po sets\n\nSpeaker\n Félix Gelinas\n\nAffiliation\n York\n\nLocation\n MC 5 479\n\nABSTRACT: For a hypergraph $\\mathbb{H}$ on $[n]$\, the hypergraphi c\nposet $P_\\mathbb{H}$ is the transitive closure of the oriented\n$1$-sk eleton of the hypergraphic polytope $\\Delta_\\mathbb{H}$\, which\nis the Minkowski sum of the standard simplices $\\Delta_H$ for each\nhyperedge $H \\in \\mathbb{H}$. In 2019\, C. Benedetti\, N. Bergeron\, and\nJ. Machace k established a remarkable correspondence between the\ntransitive closure of the oriented $1$-skeleton of $\\Delta_\\mathbb{H}$\nand the flip graph on acyclic orientations of $\\mathbb{H}$. Viewing an\norientation of $\\ma thbb{H}$ as a map $A$ from $\\mathbb{H}$ to $[n]$\,\nwe define the sources of the acyclic orientations as the values $A(H)$\nfor each hyperedge $H \ \in \\mathbb{H}$. In a recent paper\, N. Bergeron\nand V. \n\nPilaud provi ded a characterization of $P_\\mathbb{H}$ based on the\nsources of acyclic orientations for interval hypergraphs.\nSpecifically\, two distinct acycl ic orientations $A$ and $B$ of\n$\\mathbb{H}$ are comparable in $P_\\mathb b{H}$ if and only if their\nsources satisfy $A(H) \\leq B(H)$ for all hype redges $H\\in \\HH$. The\ngoal of this work is to extend this source chara cterization of\n$P_\\mathbb{H}$ to arbitrary hypergraphs on $[n]$.\n\nTHER E WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUND AT THE\nBEGINNING G RADUATE LEVEL STARTING AT 1:30PM\,\n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749db13f DTSTART;TZID=America/Toronto:20250505T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250505T123000 URL:/combinatorics-and-optimization/events/algebraic-gr aph-theory-venkata-raghu-tej-pantangi SUMMARY:Algebraic Graph Theory-Venkata Raghu Tej Pantangi CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE: Random analogues of Erd\\H{o}s-Ko-Rado type results.\n\nSPEAKER:\n\nVenkata Raghu Tej Pantangi\n\nLOCATION:\n Please contact Sabrina Lato for Zoom link.\n\nABSTRACT: The classical Erd\\H{o }s-Ko-Rado (EKR) theorem and its\nvariants can be translated into characte rizing maximum co-cliques of\ngraphs in Association schemes. For instance\ , the classical\nErd\\H{o}s-Ko-Rado characterizes maximum co-cliques in th e Kneser\ngraph. Given a graph $G$\, by $G_{p}$\, we denote the random sub graph of\n$G$ in which edges appear independently\, each with a probabilit y $p$.\nIn this talk\, we consider the following question: for which\nprob abilities is the independence number of $G_{p}$ equal to that of\n$G$? Bol labas-Narayanan-Raigorodskii investigated the independence\nnumbers of ran dom subgraphs of the Kneser graph. In this talk\, we will\ninvestigate the independence numbers of random subgraphs of (i) the\nderangement graph on permutations\; and (ii) the perfect matching\ngraphs. The derangement gra ph is associated with the EKR type result\non permutations and the perfect matching graph is associated with EKR\ntype result on perfect matchings. This is joint work with the members\nof the PIMS Collaborative Research Gr oup on Movement and Symmetry in\ngraphs.   \n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749dbb0a DTSTART;TZID=America/Toronto:20250509T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250509T163000 URL:/combinatorics-and-optimization/events/tutte-colloq uium-luke-schaeffer SUMMARY:Tutte colloquium-Luke Schaeffer CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:Faster linear algebra using treewidth\n\nSPEA KER:\n Luke Schaeffer\n\nAFFILIATION:\n University of À¶Ý®ÊÓƵ\n\nLOCATION :\n MC 5501\n\nABSTRACT: \n\n: We look at the complexity of solving sparse linear systems as a\nfunction of the treewidth of the instance. That is\, the sparse matrix\nis associated with a sparse graph\, and solutions can be found faster\nwhen that graph has low treewidth. We give a parameterize d algorithm\nin system size and treewidth achieving the conjectured optima l\nperformance.\n\nThis is joint work with Daniel Grier.\n\n \n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749dc566 DTSTART;TZID=America/Toronto:20250508T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250508T150000 URL:/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-maximilian SUMMARY:Algebraic and enumerative combinatorics seminar-Maximilian Wiesmann CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:Arrangements and Likelihood\n\nSpeaker\n Maxi milian Wiesmann\n\nAffiliation\n Max Planck\n\nLocation\n MC 5479\n\nABSTR ACT: In this talk\, we establish connections between hypersurface\narrange ments and likelihood geometry. The central object is the\nlikelihood corre spondence which captures the dependence between data\nand critical points of the likelihood function of a statistical model\nparametrized by the pol ynomials defining the arrangement. In particle\nphysics\, this same object is known as the scattering correspondence.\nThe connection to hypersurfac e arrangements leads to a new description\nof the prime ideal of the likel ihood correspondence\, which is often\ncomputationally advantageous. This description is based on the Rees\nalgebra of the likelihood module of the arrangement\, a module closely\nrelated to the module of logarithmic deriv ations. We present results\nfor generic and graphic arrangements.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUND AT THE\nBEGINNING GR ADUATE LEVEL STARTING AT 1PM\,\n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749dce74 DTSTART;TZID=America/Toronto:20250605T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250605T150000 URL:/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-alex-fink SUMMARY:Algebraic and enumerative combinatorics seminar-Alex Fink CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE:The external activity complex of a pair of ma troids\n\nSpeaker\n Alex Fink\n\nAffiliation\n Queen Mary University of Lo ndon \n\nLocation\n MC 5479\n\nABSTRACT: In 2016\, Ardila and Boocher were investigating the variety\nobtained by taking the closure of a linear spa ce within A^n in its\ncompactification (P^1)^n\; later work named this the \"matroid Schubert\nvariety\". Its Gröbner degenerations led them to def ine\, and study the\ncommutative algebra of\, the _external activity compl ex_ of a matroid.\nIf the matroid is on n elements\, this is a complex on 2n vertices\nwhose facets encode the external activity of bases.\n\nIn rec ent work with Andy Berget on Speyer's g-invariant\, we required a\ngeneral isation of the definition of external activity where the input\nwas a pair of matroids on the same ground set. We generalise many of\nthe results of Ardila--Boocher to this setting. Time permitting\, I'll\nalso present the tropical intersection theory machinery we use to\nunderstand the external activity complex of a pair.\n\nFor those who attended my talk at this yea r's CAAC on this paper\, the\ncontent of the present talk is meant to be c omplementary.\n\nTHERE WILL BE A PRE-SEMINAR PRESENTING RELEVANT BACKGROUN D AT THE\nBEGINNING GRADUATE LEVEL STARTING AT 1:30PM\,\n DTSTAMP:20250517T114721Z END:VEVENT BEGIN:VEVENT UID:68287749dd7d0 DTSTART;TZID=America/Toronto:20250428T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250428T123000 URL:/combinatorics-and-optimization/events/algebraic-gr aph-theory-sidhanth-mohanty SUMMARY:Algebraic Graph Theory-Sidhanth Mohanty CLASS:PUBLIC DESCRIPTION:Summary \n\nTITLE: Explicit Lossless Vertex Expanders\n\nSPEAK ER:\n\nSidhanth Mohanty\n\nAFFILIATION:\n\nMassachusetts Institute of Tech nology\n\nLOCATION:\n Please contact Sabrina Lato for Zoom link.\n\nABST RACT: We give the first construction of explicit constant-degree\nlossless vertex expanders. Specifically\, for any ε>0 and sufficiently\nlarge d\, we give an explicit construction of an infinite family of\nd-regular grap hs where every small set S of vertices has (1−ε)d|S|\nneighbors (which implies (1−2ε)d|S| unique-neighbors). Our results\nalso extend naturall y to construct biregular bipartite graphs of any\nconstant imbalance\, whe re small sets on each side have strong\nexpansion guarantees. The graphs w e construct admit a free group\naction\, and hence realize new families of quantum LDPC codes of Lin\nand M. Hsieh with a linear time decoding algor ithm.\n\nOur construction is based on taking an appropriate product of a\n constant-sized lossless expander with a base graph constructed from\nRaman ujan Cayley cubical complexes.\n\nBased on joint work with Jun-Ting Hsieh\ , Alexander Lubotzky\, Assaf\nReiner\, and Rachel Yun Zhang (https://arxiv .org/abs/2504.15087)\n DTSTAMP:20250517T114721Z END:VEVENT END:VCALENDAR