Korten and Pitassi (FOCS, 2024) defined a new complexity class $L_2P$ as the polynomial-time Turing closure of the Linear Ordering Principle. They put it between $MA$ (Merlin--Arthur protocols) and $S_2P$ (the second symmetric level of the polynomial hierarchy).

In this paper we sandwich $L_2P$ between $P^{prMA}$ and $P^{prSBP}$. (The oracles ... more >>>

The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the rank and partitioning number of a Boolean matrix are quasi-polynomially related.

We propose a relaxed but still equivalent version of the conjecture based on a ... more >>>

Given algorithms $A_1,A_2$ running in logspace and linear time, there are two basic ways to compute the composition $x\rightarrow A_2(A_1(x))$. Applying naive composition gives an algorithm in linear time but linear space, while applying emulative composition (i.e. the composition of space-bounded algorithms) gives an algorithm in logarithmic space but quadratic ... more >>>