BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Sayan Bhattacharya (University of Warwick) DTSTART:20250523T130000Z DTEND:20250523T140000Z DTSTAMP:20260404T094341Z UID:TCSCombBham/1 DESCRIPTION:Title: Vizing's Theorem in Near-Linear Time\nby Sayan Bhattacharya (University of Warwick) as part of TCS + Combinatorics Joint Seminar Birm ingham\n\nLecture held in Aston Webb G33.\n\nAbstract\nA textbook theorem by Vizing from the 1960s guarantees that any graph with n nodes\, m edges and maximum degree \\Delta admits a proper edge coloring with only (\\Delt a+1) colors. But\, how quickly can we compute such a (\\Delta+1)-coloring in a given input graph? We present the first near-linear time algorithm fo r this fundamental problem. Our algorithm runs in only O(m \\log \\Delta) time\; this matches the longstanding O(m \\log \\Delta) time bound for com puting a \\Delta-edge coloring in bipartite graphs.\n \nJoint work with Se pehr Assadi\, Soheil Behnezhad\, Martin Costa\, Shay Solomon and Tinayi Zh ang.\n LOCATION:https://stable.researchseminars.org/talk/TCSCombBham/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Parinya Chalermsook (University of Sheffield) DTSTART:20250620T130000Z DTEND:20250620T140000Z DTSTAMP:20260404T094341Z UID:TCSCombBham/2 DESCRIPTION:Title: Extremal Combinatorics Meets Algorithms and Data Structures \nby Parinya Chalermsook (University of Sheffield) as part of TCS + Combin atorics Joint Seminar Birmingham\n\nLecture held in Aston Webb Dome Lectur e Theatre.\n\nAbstract\nThis talk explores a rich interplay between extrem al combinatorics and the analysis of algorithms and data structures. In th e first part of the talk\, I will explain how classical Ramsey theory tigh tly captures a fundamental question in approximation algorithms and how th e LP rounding perspectives (techniques that are central in approximation a lgorithms) led to breaking a 6-decade-old extremal bound on rectangle colo ring. In the second part\, I will discuss the role of extremal combinatori cs in the context of sorting and binary search trees (in particular\, the long-standing dynamic optimality conjecture). In both scenarios\, such int erplay has been crucial in making progress and highlights the two-way dial ogue between the two fields.\n LOCATION:https://stable.researchseminars.org/talk/TCSCombBham/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Thomas Sauerwald (University of Cambridge) DTSTART:20251003T143000Z DTEND:20251003T153000Z DTSTAMP:20260404T094341Z UID:TCSCombBham/3 DESCRIPTION:Title: Balanced Allocations: The Power of Choice versus Noise\nby Thomas Sauerwald (University of Cambridge) as part of TCS + Combinatorics Joint Seminar Birmingham\n\nLecture held in Watson Lecture Theatre B.\n\nA bstract\nIn the balanced allocation problem we wish to allocate m balls (j obs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between t he maximum load and average load. For the one-choice protocol\, where each ball is allocated to a random bin\, the gap diverges for large m. However \, for the two-choice protocol\, where each ball samples two bins and is p laced in the least loaded of the two\, it was shown more than 20 years ago that the gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’\, and similar effects have b een observed in hashing and routing.\n\nIn this talk\, we will present new results in settings where the load information is restricted or noisy. Fo r example\, the queried load information of bins might be (i) outdated\, ( ii) subject to some adversarial or random perturbation or (iii) only retri evable by binary queries. We also exhibit settings with strong noise and d emonstrate that having more choices can lead to a worse performance.\n\nTh is is based on joint works with Dimitrios Los and John Sylvester. More inf ormation and some illustrations of the results are also available under:\n \nhttps://dimitrioslos.com/research/phd-thesis/index.html\n LOCATION:https://stable.researchseminars.org/talk/TCSCombBham/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Bruno Pasqualotto Cavalar (University of Oxford) DTSTART:20251031T140000Z DTEND:20251031T150000Z DTSTAMP:20260404T094341Z UID:TCSCombBham/4 DESCRIPTION:Title: Monotone Circuit Complexity of Matching\nby Bruno Pasqualot to Cavalar (University of Oxford) as part of TCS + Combinatorics Joint Sem inar Birmingham\n\nAbstract: TBA\n LOCATION:https://stable.researchseminars.org/talk/TCSCombBham/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Matthew Jenssen (KCL) DTSTART:20260327T153000Z DTEND:20260327T163000Z DTSTAMP:20260404T094341Z UID:TCSCombBham/5 DESCRIPTION:Title: Perspectives on Sphere Packing\nby Matthew Jenssen (KCL) as part of TCS + Combinatorics Joint Seminar Birmingham\n\nLecture held in P oynting small lecture theatre.\n\nAbstract\nThe classical sphere packing p roblem asks: what is the densest possible arrangement of identical\, non-o verlapping spheres in Euclidean space? Over the past century\, sphere pack ings have been intensely studied by mathematicians\, physicists and comput er scientists alike. The interaction between these perspectives has been r emarkably fruitful\, yielding new insights into the nature of packings and many related problems. In this talk I will survey these viewpoints\, disc uss recent advances\, and highlight connections to combinatorics and algor ithms along the way.\n LOCATION:https://stable.researchseminars.org/talk/TCSCombBham/5/ END:VEVENT END:VCALENDAR