Google, IBM & Meta Certificates — All 10,000+ Courses at 40% Off
One annual plan covers every course and certificate on Coursera. 40% off for a limited time.
Get Full Access
Explore advanced computational complexity theory through this seminar lecture examining the Linear Ordering Principle (LOP) and its associated complexity class L2P. Delve into the fundamental concept of LOP as a total search problem that extends minimum element finding to partially ordered settings, building upon groundbreaking work by Korten and Pitassi from FOCS 2024. Investigate the newly established tighter bounds for L2P by positioning it between PprMA and PprSBP complexity classes, where SBP represents the unique natural class bridging MA and AM. Learn about the innovative iterative procedure using prSBP oracles to estimate average order ranks and identify minimum elements in linear orders. Examine the significant theoretical implications, including the affirmative resolution of Chakaravarthy and Roy's open question regarding PprMA⊆S2P containment and the settlement of Korten and Pitassi's question about Karp-Lipton-style collapses for L2P. Gain insights into cutting-edge research in discrete mathematics and theoretical computer science through this collaborative work with Edward Hirsch, presented as part of the Computer Science/Discrete Mathematics Seminar series.
