Linear decision lists are a computational model for Boolean functions built from a sequence of linear threshold function queries. Each query is evaluated in order: if a query returns true, the list outputs the value of the function, and if the answer is false, the process continues to the next ... more >>>

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 >>>