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:6aacd1f4cd984 DTSTART;TZID=America/Toronto:20260925T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260925T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/generating-a nd-utilizing-various-types-negative-dependence-1 SUMMARY:Generating and utilizing various types of negative dependence CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Aravind Srinivasan\n\nAFFILIATION:\n University of M aryland\n\nLOCATION:\n MC 5501\n\nABSTRACT: Various notions of negative d ependence arise naturally\nand/or are desirable in various random processe s and randomized\nalgorithms. We survey how to generate and utilize a few such notions\nof negative dependence\, and sketch applications to concentr ation\ninequalities\, fairness\, and approximation algorithms. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4ce9f5 DTSTART;TZID=America/Toronto:20260918T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260918T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/many-mirrors -grassmannian-and-beyond SUMMARY:The many mirrors of the Grassmannian (and beyond) CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Elana Kalashnikov\n\nAFFILIATION:\n University of Wa terloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: The mirror of a smooth Fano to ric variety is a Laurent\npolynomial\, and this Laurent polynomial encodes interesting\nenumerative data of the toric variety.  For example\, the J acobian\nring of the Laurent polynomial is isomorphic to the small quantum \ncohomology ring of the toric variety. In this talk\, I’ll describe\nth is aspect of the (now basically classical) toric mirror theorem\, and\nexp lain how this picture is expected to extend to other smooth Fano\nvarietie s. The Grassmannian’s strong combinatorial structure  makes\nit one of the nicest examples of non-toric Fano varieties to study in\nthis context. I’ll present several mirror constructions for the\nGrassmannian that ea ch reflect a different perspective on its\ngeometry. Finally\, I’ll disc uss some extensions of these\nconstructions to generalizations of the Gras smannian.  DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4cf584 DTSTART;TZID=America/Toronto:20260911T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260911T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-luke-postle-university-waterloo SUMMARY:Tutte Colloquium - Luke Postle\, University of Waterloo CLASS:PUBLIC DESCRIPTION:Title: A PROOF OF NASH-WILLIAMS’ CONJECTURE\n\nSpeaker: Luke Postle\n  \n\nAffiliation: University of Waterloo\n  \n\nLocation: MC 5 501\n  \n\nAbstract: A central open question in extremal design theory i s\nNash-Williams’ Conjecture from 1970\, namely that every\ntriangle-div isible graph on n vertices (for n large enough) with\nminimum degree at le ast 0.75n has a triangle decomposition. In this\ntalk\, we discuss the his tory of the problem and our recent resolution\nof this conjecture\, as wel l as other applications in design theory. We\nalso overview the proof\, hi ghlighting the new techniques we developed\nto resolve the fractional vers ion as well as the full conjecture.\nJoint work with Michelle Delcourt. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d0297 DTSTART;TZID=America/Toronto:20260908T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260908T143000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/mike-cumming s-introduction-complexes-and-simplicial-homology SUMMARY:Mike Cummings-Introduction\, ∆-complexes\, and simplicial homolog y CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Mike Cummings\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 6029\n\n-------------------------\n\nABSTRACT: This term we are running a learning seminar on homology and\ncohomology\, follo wing Chapters 2 and 3 of Hatcher.  In this first\nmeeting\, we will brief ly talk about our plans for the seminar\, and\nthen will jump right into s implicial homology. All are welcome! DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d0d1e DTSTART;TZID=America/Toronto:20260811T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260811T150000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/iqc-seminar- calvin-liu-recent-advances-random-quantum SUMMARY:IQC Seminar - Calvin Liu - Recent advances in random quantum circui t\nsampling CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Calvin Liu\n\nAFFILIATION: \n University of Waterlo o\n\nLOCATION:\n MC 5029\n\nABSTRACT: \n\nIn 2019\, Google announced the demonstration of quantum supremacy by\nperforming a computational task kno wn as random circuit sampling on\ntheir 53-qubit quantum computer Sycamore . In their paper\, they claimed\nthat it would take classical computers 10 000 years to perform the same\ntask. Almost seven years has passed\, and w hat happened to this claim\nsince then? In this talk\, I will provide a hi gh-level update on the\nsubsequent developments in quantum hardware experi ments\, classical\nsimulation software\, asymptotic classical simulation a lgorithms\, and\nproving the hardness of classical simulation. This talk i s aimed at a\nnon-quantum computing audience\, and no prior background in quantum\ncomputing is assumed. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d17f1 DTSTART;TZID=America/Toronto:20260807T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-michael-friedlander-measure-cone-randomness SUMMARY:Tutte Colloquium -Michael Friedlander-The Measure of a Cone:\nRando mness and exactness in convex optimization CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Michael Friedlander\n\nAFFILIATION:\n University of British Columbia.\n\nLOCATION:\n MC 5501\n\nABSTRACT: Conic geometry enco des combinatorial properties of a convex\nprogram. Under a probabilistic model of the data\, these combinatorial\nproperties become random events. Their likelihood is the measure of a\ncone. We illustrate this view with a dual pair of questions. First\,\nhow much can a linear program be regu larized before its solution\nchanges? With random costs\, the answer turn s on the Gaussian measure\nof the solution's normal cone. Second\, how ma ny measurements are\nneeded to separate a superposition of structured sig nals? Here\, each\nsignal's complexity is the statistical dimension of its  descent cone.\nA convex program recovers the components once the measure ment count\nexceeds the total complexity.\n\nBased on joint work with Sha rvaj Kubal\, Yaniv Plan\, and Matthew Scott\;\nZhenan Fan\, Halyun Jeong\ , and Babhru Joshi\; and Ives Macêdo and Ting\nKei Pong. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d237b DTSTART;TZID=America/Toronto:20260807T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-david-aleman-unsplittable-0 SUMMARY:CombOpt ReadingGroup - David Aleman-Unsplittable multicommodity flo ws\nin fully planar instances CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n David Aleman\n\nAFFILIATION:\n University of Water loo\n\nLOCATION:\n MC 6029\n\nABSTRACT: \n\nThe multicommodity flow probl em involves routing multiple distinct\ncommodities through a shared networ k. An instance is given by\nan _undirected _graph G=(V\, E(G) ) with ed ge capacities\, and a\ncollection of source-sink pairs (s_i\,t_i) in V wit h associated\nnonnegative demands d(s_i\, t_i). It will be convenient to t hink of the\nsource-sink pairs as forming the edges of a demand graph H=( V\, E(H)\n). A flow is _feasible_ if it routes all demands without excee ding\nthe edge capacities\, and it is _unsplittable_ if it routes each\n demand along a single path. Let C be the smallest value such that the\nexi stence of a feasible flow implies the existence of an unsplittable\nflow t hat exceeds the edge capacities by at most an additivie amount\nof C times the maximum demand value.  \nWe show that if G+H = (V\, E(G) U E(H) ) is planar\, then  1.5<= C <=\n2. \nJoint work with Kumar\, Poremba\, and Sh epherd.    DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d2a30 DTSTART;TZID=America/Toronto:20260731T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260731T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-sina-kalantarzadeh-minimum-bounded SUMMARY:CombOpt ReadingGroup - Sina Kalantarzadeh-Minimum Bounded Degree\nS panning Trees CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Sina Kalantarzadeh\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: I will present Goemans’s beautiful\, though no longer\nstate-of-the-art\, 2006 result on the Minimu m Bounded-Degree Spanning\nTree problem. Given a weighted graph (G=(V\,E)) and degree bounds\n(B\\to\\mathbb{N})\, the goal is to find a minimum-cos t spanning tree (T)\nsatisfying (d_T(v)\\le B(v)) for every (v\\in V). Thi s problem is\nNP-hard. Fürer and Raghavachari (1992) gave a polynomial-ti me\nalgorithm for the unweighted setting that produces a spanning tree\nsa tisfying (d_T(v)\\le B(v)+1). For the weighted problem\, Goemans\ndesigned an elegant LP-rounding algorithm that returns a tree of cost\nat most tha t of the optimal degree-bounded solution while satisfying\n(d_T(v)\\le B(v )+2). I will explain this result and the simple yet\nbeautiful combinatori al optimization ideas underlying it. In 2007\,\nSingh and Lau improved the violation to (B(v)+1) using iterative\nrelaxation\, which I might give a talk about in later sessions. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d30c1 DTSTART;TZID=America/Toronto:20260804T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260804T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/optimization -seminar-david-torregrosa-belen-convergence SUMMARY:Optimization seminar-David Torregrosa Belén-Convergence of a proxi mal\nstochastic subgradient method under the Kurdyka-Lojasiewicz condition CLASS:PUBLIC DESCRIPTION:SPEAKER:\n David Torregrosa Belén\n\nAFFILIATION:\n University of Alicante\n\nLOCATION:\n MC 5501\n\nABSTRACT:This talk presents a proxi mal stochastic subgradient\nmethod for minimizing the sum of an expected cost and a lower\nsemicontinuous\, prox-bounded function. We target a bro ad class of\nnonconvex integrands obeying a nonsmooth\, localized variant of the\ndescent lemma in the decision variable\, which in particular cov ers\nsmooth losses with Lipschitz gradient. At each iteration\, the\nexpe cted cost is replaced by a sample average that is progressively\nrefined\ , and the proximal stepsize is selected by an Armijo-type line\nsearch en forcing a\nsufficient decrease property up to stochastic errors induced by \nthe sample-based approximation. This framework accommodates more\ngener al problem formulations than existing methods and our analysis\nyields c onvergence guarantees that\, to the best of our knowledge\,\nare new even  in the smooth setting. Specifically\, we establish almost\nsure converg ence of the sequence of function values and stationarity\nof every accumu lation point of the trajectories under the relaxed\nrequirement that the sample-size sequence be merely nondecreasing and\nunbounded. Leveraging t he Kurdyka-Lojasiewicz property\, we further\nproof convergence of the wh ole trajectory to a single stationary\npoint. Finally\, for exponential-t ype desingularizing functions and\npolynomially growing sample sizes\, we derive explicit polynomial\nconvergence rates\, up to logarithmic factor \, for both the function\nvalues and the iterates. This is a joint work w ith Felipe Atenas\,\nPedro Pérez-Aros and Alejandro\nJofré\, from the Un iversity of Chile. DTSTAMP:20260918T055356Z END:VEVENT BEGIN:VEVENT UID:6aacd1f4d3886 DTSTART;TZID=America/Toronto:20260804T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260804T120000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/optimization -seminar-ting-kei-pong-conditional-gradient SUMMARY:Optimization seminar-Ting Kei Pong-A Conditional-Gradient-Based\nSi ngle-Loop Augmented Lagrangian Method for Inequality Constrained\nProblems CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Ting Kei Pong\n\nAFFILIATION:\n The Hong Kong Polyte chnic University\n\nLOCATION:\n MC 5501\n\nABSTRACT:We consider the proble m of minimizing the sum of a Lipschitz\ndifferentiable convex function an d a proper closed convex function\nthat admits efficient linear minimiza tion oracles\, subject to\nmultiple smooth convex inequality constraint s. We adapt the\nclassical augmented Lagrangian (AL) method for these pr oblems: in\neach iteration\, our algorithm consists of one step of condit ional\ngradient (CG) method applied to the AL function\, followed by\nan  update of the dual variable as in classical AL methods with a\ndiminish ing dual stepsize. We study the convergence rate of our\nalgorithm under two standard stepsize rules for the CG method\,\nnamely\, an open-loop s tepsize and the short stepsize\, and obtain a\nrate that matches the bes t-known complexity for this class of\nproblems. We also establish accele rated rates when\nthe aforementioned proper closed convex function is the  indicator\nfunction of a uniformly convex set. This is a joint work wit h\nXiaozhou Wang and Zev Woodstock. DTSTAMP:20260918T055356Z END:VEVENT END:VCALENDAR