
Upper and Lower Bounds for the Linear Ordering Principle
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.