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:69dd4f9284ec6 DTSTART;TZID=America/Toronto:20250718T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250718T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-ashwin-nayak-1 SUMMARY:Tutte colloquium-Ashwin Nayak CLASS:PUBLIC DESCRIPTION:TITLE:Learning quantum states\n\nSPEAKER:\n Ashwin Nayak\n\nAFF ILIATION:\n University of Waterloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: Su ppose we are given a sequence of quantum registers\ninitialized to the sa me quantum state rho\, and would like to learn\nthe state rho. That is\,  we would like to design an algorithm that\nproduces a classical descripti on of an approximation to the state.\nHow many copies of rho dowe need to be able to produce a suitable\napproximation? This talk will be a gentle introduction to the problem\nand related results.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9285e6b DTSTART;TZID=America/Toronto:20250711T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250711T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-stephen-melczer-0 SUMMARY:Tutte colloquium-Stephen Melczer CLASS:PUBLIC DESCRIPTION:TITLE:Automated Sequence Asymptotics\n\nSPEAKER:\n Stephen Melc zer\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 5501\n\nABS TRACT:Computing with any sort of object requires a way of encoding\nit on a computer\, which poses a problem in enumerative combinatorics\nwhere the objects of interest are (infinite) combinatorial sequences.\nThankfully\, the generating function of a combinatorial sequence often\nsatisfies natu ral algebraic/differential/functional equations\, which\ncan then be viewe d as data structures for the sequence. In this talk\nwe survey methods to take a sequence encoded by such data structures\nand automatically determi ne asymptotic behaviour using techniques from\nthe field of analytic combi natorics. We also discuss methods to\nautomatically characterize the asymp totic behaviour of multivariate\nsequences using analytic combinatorics in several variables (ACSV).\nThe focus of each topic will be rigorous algor ithms that have already\nbeen implemented in computer algebra systems and can be easily used by\nanyone.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f928668b DTSTART;TZID=America/Toronto:20250704T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250704T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-henry-wolkowicz-2 SUMMARY:Tutte colloquium-Henry Wolkowicz CLASS:PUBLIC DESCRIPTION:TITLE:The omega-Condition Number: Applications to Preconditioni ng and\nLow Rank Generalized Jacobian Updating\n\nSPEAKER:\n Henry Wolkowi cz\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 5501\n\nABST RACT: Preconditioning is essential in iterative methods for\nsolving line ar systems. It is also the implicit objective in updating\napproximations of Jacobians in optimization methods\, e.g.\,~in\nquasi-Newton methods. We study a nonclassic matrix condition number\,\nthe omega-condition number} \, omega for short. omega is the ratio of:\nthe arithmetic and geometric m eans of the singular values\, rather than\nthe largest and smallest for th e classical kappa-condition number. The\nsimple functions in omega allow o ne to exploit  first order\noptimality conditions. We use this fact to de rive explicit formulae\nfor (i) omega-optimal low rank updating of general ized Jacobians\narising in the context of nonsmooth Newton methods\; and ( ii)\nomega-optimal preconditioners of special structure for  iterative\nm ethods for linear systems. In the latter context\, we analyze the\nbenefit s of omega for (a) improving the clustering of eigenvalues\; (b)\nreducing the number of iterations\; and (c) estimating the actual\ncondition of a linear system. Moreover we show strong theoretical\nconnections between th e omega-optimal preconditioners and incomplete\nCholesky factorizations\, and highlight the misleading effects arising\nfrom the inverse invariance of kappa. Our results confirm the efficacy\nof using the omega-condition n umber compared to the kappa-condition\nnumber.\n\n(Joint work with: Woosuk L. Jung\, David Torregrosa-Belen.)\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9286ef2 DTSTART;TZID=America/Toronto:20250627T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250627T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-gary-au-0 SUMMARY:Tutte colloquium-Gary Au CLASS:PUBLIC DESCRIPTION:TITLE:Worst-case instances of the stable set problem of graphs for the\nLovász–Schrijver SDP hierarchy\n\nSPEAKER:\n Gary Au\n\nAFFILI ATION:\n University of Saskatchewan\n\nLOCATION:\n MC 5501\n\nABSTRACT:(Ba sed on joint work with Levent Tunçel.)\n\nIn this talk\, we discuss semid efinite relaxations of the stable set\nproblem of graphs generated by the lift-and-project operator LS_+ (due\nto Lovász and Schrijver)\, and prese nt some of our recent progress on\nthis front. In particular\, we show tha t for every positive integer k\,\nthe smallest graph with LS_+-rank k cont ains exactly 3k vertices. This\nresult is sharp and settles a conjecture p osed by Lipták and Tunçel\nfrom 2003.\n\nThe talk will be accessible to a general audience\, and does not assume\nany prior knowledge of lift-and- project methods.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f928776e DTSTART;TZID=America/Toronto:20250620T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250620T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-sepehr-hajebi SUMMARY:Tutte colloquium-Sepehr Hajebi CLASS:PUBLIC DESCRIPTION:TITLE:Complete bipartite induced minors (and treewidth)\n\nSPEA KER:\n Sepehr Hajebi\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION: \n MC 5501\n\nABSTRACT:I will present a result that describes the unavoida ble\ninduced subgraphs of graphs with a large complete bipartite induced\n minor\, and will discuss the connections and applications to bounding\nthe treewidth in hereditary classes of graphs. If time permits\, I will\nalso sketch some proofs.\n\n Joint work with Maria Chudnovsky and Sophie Spir kl.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9287f04 DTSTART;TZID=America/Toronto:20250613T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250613T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-rose-mccarty SUMMARY:Tutte colloquium-Rose McCarty CLASS:PUBLIC DESCRIPTION:TITLE:The first-order logic of graphs\n\nSPEAKER:\n  Rose McCa rty\n\nAFFILIATION:\n Georgia Institute of Technology\n\nLOCATION:\n MC 55 01\n\nABSTRACT:Over the last ten years\, many wonderful connections have b een\nestablished between structural graph theory\, computational complexit y\,\nand finite model theory. We give an overview of this area\, focusing on\nrecent progress towards understanding the \"stable\" case. We do not\n assume any familiarity with first-order logic\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9288713 DTSTART;TZID=America/Toronto:20250530T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250530T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-lior-gishboliner SUMMARY:Tutte colloquium-Lior Gishboliner CLASS:PUBLIC DESCRIPTION:TITLE:Regularity lemmas for hypergraphs of bounded VC dimension :\nimproved bounds\n\nSPEAKER:\n Lior Gishboliner\, \n\nAFFILIATION:\n Uni versity of Toronto\n\nLOCATION:\n MC 5501\n\nABSTRACT:An important result at the interface of graph theory and\nlogic is that graphs of bounded VC d imension have (small) homogeneous\nvertex-partitions\, i.e.\, partitions w here almost every pair of parts\nhas density close to 0 or 1. Recently\, C hernikov and Towsner proved a\nhypergraph generalization of this fact. The quantitative aspects of\ntheir result remain open. I will present some re cent progress on this\nproblem\, answering two questions of Terry. This is a joint work with\nAsaf Shapira and Yuval Wigderson.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9289189 DTSTART;TZID=America/Toronto:20250523T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250523T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-david-torregrossa-belen SUMMARY:Tutte colloquium-David Torregrossa Belén CLASS:PUBLIC DESCRIPTION:TITLE:Splitting algorithms for monotone inclusions with\nminima l dimension\n\nSPEAKER:\n David Torregrossa Belén\n\nAFFILIATION:\n Cent er for Mathematical Modeling\, University of Chile\n\nLOCATION:\n MC 5501 \n\nABSTRACT: Many situations in convex optimization can be modeled as the \nproblem of finding a zero of a monotone operator\, which can be\nregard ed as a generalization of the gradient of a differentiable\nconvex functi on. In order to numerically address this monotone\ninclusion problem\, it is vital to be able to exploit the inherent\nstructure of the operator  defining it. The algorithms in the family\nof the splitting methods achie ve this by iteratively solving simpler\nsubtasks that are defined by sepa rately using some parts of the\noriginal problem.\n\nIn the first part of this talk\, we will introduce some of the\nmost relevant monotone inclusi on problems and present their\napplications to optimization. Subsequently \, we will draw our\nattention to a common anomaly that has persisted in the design of\nmethods in this family: the dimension of the underlying sp ace\n—which we denote as lifting— of the algorithms abnormally\nincre ases as the problem size grows. This has direct implications on\nthe comp utational performance of the method as a result of the\nincrease of memor y requirements. In this framework\, we characterize\nthe minimal lifting that can be obtained by splitting algorithms\nadept at solving certain ge neral monotone inclusions. Moreover\, we\npresent splitting methods match ing these lifting bounds\, and\nthus having minimal lifting.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f9289940 DTSTART;TZID=America/Toronto:20250516T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250516T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-michael-borinsky SUMMARY:Tutte colloquium-Michael Borinsky CLASS:PUBLIC DESCRIPTION:TITLE:Constraining moduli space cohomology by counting graphs\n \nSPEAKER:\n Michael Borinsky\n\nAFFILIATION:\n Perimeter Institute\n\nLOC ATION:\n MC 5501\n\nABSTRACT: In 1992\, Kontsevich defined complexes spann ed by graphs.\nThese \ncomplexes are increasingly prominent in algebraic topology\,\ngeometric \ngroup theory and mathematical physics. For instan ce\, a 2021 theorem\nby \nChan-Galatius and Payne implies that the top-we ight cohomology of\nthe \nmoduli space of curves of genus g is equal to t he homology of a\nspecific \ngraph complex. I will present a new theorem on the asymptotic growth \nrate of the Euler characteristic of this graph complex and explain\nits \nimplication on the cohomology of the moduli s pace of curves. The\nproof \ninvolves solving a specific graph counting p roblem.\n\n  DTSTAMP:20260413T201826Z END:VEVENT BEGIN:VEVENT UID:69dd4f928a116 DTSTART;TZID=America/Toronto:20250509T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20250509T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-luke-schaeffer SUMMARY:Tutte colloquium-Luke Schaeffer CLASS:PUBLIC DESCRIPTION:TITLE:Faster linear algebra using treewidth\n\nSPEAKER:\n Luke Schaeffer\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 5501\ n\nABSTRACT: \n\n: We look at the complexity of solving sparse linear syst ems 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 fas ter\nwhen that graph has low treewidth. We give a parameterized algorithm\ nin system size and treewidth achieving the conjectured optimal\nperforman ce.\n\nThis is joint work with Daniel Grier.\n\n  DTSTAMP:20260413T201826Z END:VEVENT END:VCALENDAR