Ilya Volkovich of Boston College : Upper and Lower Bounds for the Linear Ordering Principle

Posted by Lev Reyzin , part of the Mathematical Computer Science Seminar.

At

Aug. 24, 2026, 3 p.m.

In

636 SEO

Abstract

The Linear Ordering Principle (LOP) is a total search problem that generalizes the task of finding the minimum element of a given order to settings in which the order need not be total. Building on this, Korten and Pitassi (FOCS 2024) introduced the complexity class $\L_2P$ as the polynomial-time Turing closure of LOP. They also showed that $\L_2P$ lies between $\MA$ (Merlin–Arthur protocols) and $\S_2P$ (the second symmetric level of the polynomial hierarchy). In this work, we establish tighter upper and lower bounds for $\L_2P$ by sandwiching it between $\P^{\prMA}$ and $\P^{\prSBP}$. Here, the oracles are promise problems, and $\SBP$ is the only currently known natural complexity class that lies between $\MA$ and $\AM$. The containment $\L_2P \subseteq \P^{\prSBP}$ is obtained via an iterative procedure that uses a $\prSBP$ oracle to estimate the average order rank of a subset and to identify the minimum element of a linear order. This technique may be of independent interest.