BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Between Worst-Case and Average-Case Analysis: Algor
 ithms and Applications
DTSTART:20260309T101500
DTEND:20260309T111500
DTSTAMP:20260531T011237Z
UID:5544d3cecaa3edbd453e212840407ff4431509b45869508856e9d23e
CATEGORIES:Conferences - Seminars
DESCRIPTION:Par : Peter Manohar - Institute for Advanced Study\nIC Facult
 y candidate\n\nAbstract\nThe classic study of algorithms focuses on unders
 tanding the behavior of algorithms on either worst-case or average-case in
 puts. Both of these models have well-established drawbacks: the worst-case
  model is overly pessimistic in assuming that the input is adversarially c
 hosen\, while the average-case model is overly optimistic in assuming that
  the input is drawn from an idealized distribution.\n\nA natural method to
  overcome both these issues is to study algorithms for "semirandom" inputs
  --- inputs drawn from distributions with a hybrid of worst-case and avera
 ge-case structure. In this talk\, I will discuss my work on designing algo
 rithms for semirandom constraint satisfaction problems (such as 3-SAT)\, a
 nd explain how my algorithmic tools have led to surprising progress on dec
 ades-old problems in coding theory\, extremal combinatorics\, and more.\n\
 nBio\nPeter Manohar is a postdoctoral researcher at the Institute for Adva
 nced Study. He received his PhD in Computer Science from Carnegie Mellon U
 niversity in 2024\, advised by Venkatesan Guruswami and Pravesh K. Kothari
 \, and his B.S. in EECS from UC Berkeley in 2019.\nHis research interests 
 span several areas of theoretical computer science\, including beyond wors
 t-case analysis of algorithms\, spectral algorithms\, coding theory\, and 
 extremal combinatorics\, and his work has been featured in the Communicati
 ons of the ACM Research Highlights and Quanta Magazine.\n\nMore informatio
 n\n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420 https://epfl.zoom.us/
 j/68916934362
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR