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:20260422T212731Z
UID:TCSCombBham/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSCombBham/
 1/">Vizing's Theorem in Near-Linear Time</a>\nby Sayan Bhattacharya (Unive
 rsity of Warwick) as part of TCS + Combinatorics Joint Seminar Birmingham\
 n\nLecture held in Aston Webb G33.\n\nAbstract\nA textbook theorem by Vizi
 ng from the 1960s guarantees that any graph with n nodes\, m edges and max
 imum degree \\Delta admits a proper edge coloring with only (\\Delta+1) co
 lors. But\, how quickly can we compute such a (\\Delta+1)-coloring in a gi
 ven input graph? We present the first near-linear time algorithm for this 
 fundamental problem. Our algorithm runs in only O(m \\log \\Delta) time\; 
 this matches the longstanding O(m \\log \\Delta) time bound for computing 
 a \\Delta-edge coloring in bipartite graphs.\n \nJoint work with Sepehr As
 sadi\, Soheil Behnezhad\, Martin Costa\, Shay Solomon and Tinayi Zhang.\n
LOCATION:https://researchseminars.org/talk/TCSCombBham/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Parinya Chalermsook (University of Sheffield)
DTSTART:20250620T130000Z
DTEND:20250620T140000Z
DTSTAMP:20260422T212731Z
UID:TCSCombBham/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSCombBham/
 2/">Extremal Combinatorics Meets Algorithms and Data Structures</a>\nby Pa
 rinya Chalermsook (University of Sheffield) as part of TCS + Combinatorics
  Joint Seminar Birmingham\n\nLecture held in Aston Webb Dome Lecture Theat
 re.\n\nAbstract\nThis talk explores a rich interplay between extremal comb
 inatorics and the analysis of algorithms and data structures. In the first
  part of the talk\, I will explain how classical Ramsey theory tightly cap
 tures a fundamental question in approximation algorithms and how the LP ro
 unding perspectives (techniques that are central in approximation algorith
 ms) led to breaking a 6-decade-old extremal bound on rectangle coloring. I
 n the second part\, I will discuss the role of extremal combinatorics in t
 he context of sorting and binary search trees (in particular\, the long-st
 anding dynamic optimality conjecture). In both scenarios\, such interplay 
 has been crucial in making progress and highlights the two-way dialogue be
 tween the two fields.\n
LOCATION:https://researchseminars.org/talk/TCSCombBham/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Thomas Sauerwald (University of Cambridge)
DTSTART:20251003T143000Z
DTEND:20251003T153000Z
DTSTAMP:20260422T212731Z
UID:TCSCombBham/3
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSCombBham/
 3/">Balanced Allocations: The Power of Choice versus Noise</a>\nby Thomas 
 Sauerwald (University of Cambridge) as part of TCS + Combinatorics Joint S
 eminar Birmingham\n\nLecture held in Watson Lecture Theatre B.\n\nAbstract
 \nIn the balanced allocation problem we wish to allocate m balls (jobs) in
 to 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 the maxi
 mum load and average load. For the one-choice protocol\, where each ball i
 s 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 placed i
 n the least loaded of the two\, it was shown more than 20 years ago that t
 he 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 been obs
 erved in hashing and routing.\n\nIn this talk\, we will present new result
 s in settings where the load information is restricted or noisy. For examp
 le\, the queried load information of bins might be (i) outdated\, (ii) sub
 ject to some adversarial or random perturbation or (iii) only retrievable 
 by binary queries. We also exhibit settings with strong noise and demonstr
 ate that having more choices can lead to a worse performance.\n\nThis is b
 ased on joint works with Dimitrios Los and John Sylvester. More informatio
 n and some illustrations of the results are also available under:\n\nhttps
 ://dimitrioslos.com/research/phd-thesis/index.html\n
LOCATION:https://researchseminars.org/talk/TCSCombBham/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bruno Pasqualotto Cavalar (University of Oxford)
DTSTART:20251031T140000Z
DTEND:20251031T150000Z
DTSTAMP:20260422T212731Z
UID:TCSCombBham/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSCombBham/
 4/">Monotone Circuit Complexity of Matching</a>\nby Bruno Pasqualotto Cava
 lar (University of Oxford) as part of TCS + Combinatorics Joint Seminar Bi
 rmingham\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/TCSCombBham/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Jenssen (KCL)
DTSTART:20260327T153000Z
DTEND:20260327T163000Z
DTSTAMP:20260422T212731Z
UID:TCSCombBham/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSCombBham/
 5/">Perspectives on Sphere Packing</a>\nby Matthew Jenssen (KCL) as part o
 f TCS + Combinatorics Joint Seminar Birmingham\n\nLecture held in Poynting
  small lecture theatre.\n\nAbstract\nThe classical sphere packing problem 
 asks: what is the densest possible arrangement of identical\, non-overlapp
 ing spheres in Euclidean space? Over the past century\, sphere packings ha
 ve been intensely studied by mathematicians\, physicists and computer scie
 ntists alike. The interaction between these perspectives has been remarkab
 ly fruitful\, yielding new insights into the nature of packings and many r
 elated problems. In this talk I will survey these viewpoints\, discuss rec
 ent advances\, and highlight connections to combinatorics and algorithms a
 long the way.\n
LOCATION:https://researchseminars.org/talk/TCSCombBham/5/
END:VEVENT
END:VCALENDAR