[Proof Complexity] MIAO seminar Tue Feb 13 at 16:00 with Oliver Korten: The weak pigeonhole principle and the complexity of explicit constructions

[Jakob Nordström]

Dear colleagues,

On Tuesday February 13 at 16:00 CET (please note the time!) we will have the pleasure of listening to a seminar with Oliver Korten from Columbia University, who will give a talk titled "The weak pigeonhole principle and the complexity of explicit constructions". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday Feb 13 at 16:00 CET (note the time!) on Zoom
The weak pigeonhole principle and the complexity of explicit constructions
(Oliver Korten, Columbia University)

The probabilistic method is a ubiquitous tool used to establish the existence of interesting and useful combinatorial objects, for example strong error correcting codes and expander graphs. A drawback of this method is that it is typically non-constructive: it indicates no efficient deterministic means by which to construct the object of interest, and in many cases replacing the non-constructive argument by a so-called "explicit construction" requires many years of hard-fought mathematical advances. In this talk I will discuss recent work establishing a structural theory for the complexity of such explicit construction problems. This theory is based around a simple search problem called "Range Avoidance," where a function is given from a small set to a much larger one, and a value outside the range is sought. We will establish that most of the interesting and unsolved explicit construction problems fall naturally into a complexity class defined by this problem, and that one of the most famous among these is "complete" (roughly in the sense of NP completeness). We will also explore some subsequent results connecting Range Avoidance to classical topics in complexity theory including derandomization and boolean circuit lower bounds.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98 / +45 28 78 38 11
https://jakobnordstrom.se