[Colloquium] CS Theory Seminar - Tuesday, November 11

Tue Nov 4 08:30:50 CST 2025

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS

Marco Carmosino
International Business Machines (IBM)

[cid:image001.png at 01DC4A74.7A8635F0]

Tuesday, November 11, 2025, at 3:30pm
Kent Chemical Laboratory, Room 102

Title: Constructive Complexity Theory

Abstract: Why do the main questions of complexity theory remain open after decades of intensive research?  This talk surveys exciting new results and tools that are beginning to explain the inherent difficulty of open questions in complexity theory.  We formulate complexity theory as a collection of computational problems, and explore the inherent difficulty of designing efficient algorithms to solve these problems.  Surprisingly, "algorithmic" solutions to major open problems in complexity (including P vs. NP) are necessarily algorithmic.

Bio: Marco Leandro Carmosino is a Research Scientist at IBM. He is broadly interested in the constructive meta-mathematics of computational complexity, learning theory, and cryptography. Previously, he was supported by an NSF Computing Innovation fellowship with Mark Bun, and a Pacific Institute for the Mathematical Sciences Fellowship with Valentine Kabanets. He got his PhD from UCSD in 2019, advised by Russell Impagliazzo.

  Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251104/2400cedf/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 3358278 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251104/2400cedf/attachment-0001.png>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251104/2400cedf/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251104/2400cedf/attachment-0003.txt>