LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Upper and Lower Bounds for the Linear Ordering Principle
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Upper and Lower Bounds for the Linear Ordering Principle

71 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Ilya Volkovich of Boston College presents this Institute for Advanced Study computer science and discrete mathematics seminar on the Linear Ordering Principle, a total search problem generalizing the task of finding a minimum element when the underlying order is not total. Building on Korten and Pitassi's 2024 definition of the complexity class L2P, Volkovich, in joint work with Edward Hirsch, sandwiches L2P between the promise classes PprMA and PprSBP, using an iterative procedure that calls a prSBP oracle to estimate average order rank and locate a minimum element. The talk works through the consequences of these containment results, including an affirmative answer to a 2011 open question by Chakaravarthy and Roy on whether PprMA is contained in S2P, and a resolution of Korten and Pitassi's question about Karp-Lipton-style collapse for L2P. It is a technical complexity-theory seminar aimed at researchers already familiar with Arthur-Merlin protocols and the polynomial hierarchy.

At a glance

Lecture facts

Runtime compared with the other 350 Mathematics lectures
Runtime1 h 11 m
Compared with MathematicsShorter than 56%
Source channelInstitute for Advanced Study (YouTube)