BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CMSA - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:CMSA
X-ORIGINAL-URL:https://cmsa.fas.harvard.edu
X-WR-CALDESC:Events for CMSA
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20221106T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20231105T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20230314T120000
DTEND;TZID=America/New_York:20230314T130000
DTSTAMP:20260409T084532
CREATED:20230817T170402Z
LAST-MODIFIED:20240118T065025Z
UID:10001237-1678795200-1678798800@cmsa.fas.harvard.edu
SUMMARY:Randomized algorithms in combinatorics
DESCRIPTION:Member Seminar \nSpeaker: Michael Simkin \nTitle: Randomized algorithms in combinatorics \nAbstract: Randomized algorithms have been a computational workhorse for almost as long as there have been computers. Surprisingly\, such algorithms can also be used to attack problems that are neither algorithmic nor probabilistic. Time permitting I will discuss the following combintorial examples: \n\nEnumerative combinatorics and the n-queens problem: In how many ways can one place n queens on an n x n chessboard so that no queen threatens any other?\nConstructions of combinatorial designs and the Erdos high-girth Steiner triple system problem: An order-n Steiner triple system (STS) is a collection of triples on n vertices such that every pair of vertices is contained in exactly one triple. In 1973 Erdos conjectured that there exist STSs with arbitrary large girth (informally\, no small set of vertices spans many triples). I will discuss the use of randomized algorithms to prove this conjecture. Joint work with Kwan\, Sah\, and Sawhney.\nThresholds in random graphs and hypergraphs: I will discuss how randomized algorithms can be combined with the recent resolution of the Kahn–Kalai conjecture to determine thresholds in random (hyper) graph theory. Joint work with Pham\, Sah\, and Sawhney.
URL:https://cmsa.fas.harvard.edu/event/member-seminar-31423/
LOCATION:CMSA Room G10\, CMSA\, 20 Garden Street\, Cambridge\, MA\, 02138\, United States
CATEGORIES:Member Seminar
END:VEVENT
END:VCALENDAR