Events

Sep 29

Semirandom CSP refutation via Kikuchi matrices: Algorithms, Certificates, and Connections

12:30 PM to 2:00 PM

CS conference room (CSB453)

Peter Manohar, Carnegie Mellon University

Abstract: In this talk, we will present new algorithms for semirandom and smoothed instances of constraint satisfaction problems — hybrid instances between worst-case (NP-hard) and average-case (random) instances — with the same algorithmic guarantees and clause density thresholds as the state-of-the-art algorithms for random instances.

The key technical ingredient underpinning our algorithms is a new class of spectral methods based on “Kikuchi matrices” built from hypergraphs associated with the input instance of a constraint satisfaction problem. Our algorithms and spectral techniques additionally have interesting consequences to well-studied problems in extremal combinatorics, coding theory, and cryptography. I will discuss the following two applications:

(1) Resolving Feige's conjecture from 2008, an extremal combinatorics conjecture about the girth vs. density trade-off for hypergraphs that generalizes the Moore bound for graphs;

(2) Proving a cubic lower bound for 3-query locally decodable codes, improving on the quadratic lower bound of Kerendis and de Wolf from 2004.

Oct 03

Theory Student Seminar

12:40 PM to 2:00 PM

CSB 480

https://theory.cs.columbia.edu/theory-student-seminar.html

Oct 06

Theory Lunch - Sunoo Park

12:30 PM to 2:00 PM

CS conference room (CSB453)

Sunoo Park, New York University

Oct 09

Protecting Human Users from Misused AI

11:40 AM to 12:40 PM

CSB 451 CS Auditorium

Ben Y. Zhao, University of Chicago

CS Distinguished Lecture Series - Ben Y. Zhao

Abstract:
Recent developments in machine learning and artificial intelligence have taken nearly everyone by surprise. The arrival of arguably the most transformative wave of AI did not bring us smart cities full of self-driving cars, or robots that do our laundry and mow our lawns. Instead, it brought us over-confident token predictors that hallucinate, deepfake generators that produce realistic images and video, and ubiquitous surveillance. In this talk, I’ll describe some of our recent efforts to warn, and later defend against some of the darker side of AI. In particular, I will tell the story of how our efforts to disrupt unauthorized facial recognition models led unexpectedly to Glaze, a tool to defend human artists against art mimicry by generative image models. I will share some of the ups and downs of implementing and deploying an adversarial ML tool to a global user base, and reflect on mistakes and lessons learned.

Bio:
Ben Zhao is Neubauer Professor of Computer Science at University of Chicago. He completed his Ph.D. at U.C. Berkeley (2004), and B.S. from Yale (1997). He is a Fellow of the ACM, and a recipient of the NSF CAREER award, MIT Technology Review's TR-35 Award (Young Innovators Under 35), USENIX Internet Defense Prize, ComputerWorld Magazine's Top 40 Tech Innovators award, IEEE ITC Early Career Award, and Faculty awards from Google, Amazon, and Facebook. His work has been covered by media outlets including New York Times, CNN, NBC, BBC, MIT Tech Review, Wall Street Journal, Forbes, and New Scientist. He has published over 180 articles in areas of security and privacy, machine learning, networking, and HCI. He served as TPC (co-)chair for the World Wide Web conference (WWW 2016) and ACM Internet Measurement Conference (IMC 2018). He also serves on the steering committee for HotNets.

Oct 10

Theory Student Seminar

12:30 PM to 2:00 PM

CSB 480

https://theory.cs.columbia.edu/theory-student-seminar.html

Oct 18

Coffee and Questions

2:00 PM to 4:00 PM

CSB 452

Coffee and Questions will be a recurring social event for current CS students to speak with each other and the CS Advising team in the CS Lounge (CSB 452). Light refreshments will be provided, with occasional faculty/ departmental guests in attendance.

Oct 23

Next-Generation Domain-Specific Accelerators: From Hardware to System

2:30 PM to 3:30 PM

CS conference room (CSB453)

Sophia Shao, UC Berkeley

Abstract:
In the era of diminishing returns from technology scaling, domain-specific accelerators have become a key component in today’s computing platforms. The natural evolution of this trend will lead to an increasing volume and diversity of accelerators for emerging applications such as machine learning, robotics, data centers, and many more. However, today’s accelerators are largely designed in isolation, with little consideration of how they interact with software and other components, leading to suboptimal end-to-end performance.

In this talk, I will discuss the challenges and opportunities associated with the design of next-generation domain-specific systems. Specifically, I will describe our group's recent work on domain-specific accelerator design, integration, and simulation, with the goal of democratizing accelerated computing for all applications. The results of our endeavors indicate a future in which domain-specific systems can be thoroughly designed, integrated, and evaluated to achieve high efficiency across different applications.

Bio:
Professor Sophia Shao is an Assistant Professor of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Previously, she was a Senior Research Scientist at NVIDIA and received her Ph.D. degree in 2016 from Harvard University. Her research interests are in the area of computer architecture, with a special focus on domain-specific architecture, deep-learning accelerators, and high-productivity hardware design methodology. Her work has been awarded a Distinguished Artifact Award at ISCA’2023, the Best Paper Award at DAC’2021, the Best Paper Award at JSSC’2020, a Best Paper Award at MICRO’2019, a Research Highlight of Communications of ACM (2021), Top Picks in Computer Architecture (2014), and Honorable Mentions (2019*2). She is a
recipient of an NSF CAREER Award, the 2022 IEEE TCCA Young Computer Architect Award, an Intel Rising Star Faculty Award, a Google Research Scholar Award, and the inaugural Dr. Sudhakar Yalamanchili Award. Her personal webpage is https://people.eecs.berkeley.edu/~ysshao/.

Oct 25

Distinguished Lecture - Sarita Adve

11:40 AM to 12:40 PM

CSB 451 CS Auditorium

Sarita Adve, University of Illinois at Urbana-Champaign

Nov 01

Distinguished Lecture - Heng Ji

11:40 AM to 12:40 PM

CSB 451 CS Auditorium

Heng Ji, University of Illinois at Urbana-Champaign

Nov 06

Academic Holiday (No Classes Held)

9:00 AM to 9:00 PM

Nov 07

Election Day (University Holiday)

9:00 AM to 9:00 PM

Nov 08

Distinguished Lecture - Caroline Uhler

11:40 AM to 12:40 PM

CSB 451 CS Auditorium

Caroline Uhler, Massachusetts Institute of Technology

Nov 15

Distinguished Lecture - Monica Lam

11:40 AM to 12:40 PM

CSB 451 CS Auditorium

Monica Lam, Stanford University

Nov 15

Coffee and Questions

2:00 PM to 4:00 PM

CSB 452

Coffee and Questions will be a recurring social event for current CS students to speak with each other and the CS Advising team in the CS Lounge (CSB 452). Light refreshments will be provided, with occasional faculty/ departmental guests in attendance.

Nov 23

Thanksgiving - University Holiday

9:00 AM to 5:00 PM

Nov 24

University Holiday

9:00 AM to 5:00 PM

Dec 25

Christmas Day - University Holiday

9:00 AM to 5:00 PM

Dec 26

University Holiday

10:00 AM to 12:00 PM

Dec 29

University Holiday

10:00 AM to 12:00 PM

Jan '24 01

New Year's Day - University Holiday

10:00 AM to 12:00 PM