Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By ... more >>>

The sign rank of a ${\pm 1}$-valued matrix $A$ is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. For every sufficiently large $d$, we give an explicit matrix $A$ with $2^{\Theta(d^2)}$ rows and columns and sign rank $\Theta(d)$ such that $A \land A$ has ... more >>>

We resolve two open problems regarding the Sherali-Adams proof system. First, we show that Res(2), which manipulates 2-DNF formulas, is exponentially stronger than Sherali-Adams. This provides a sharp separation in power between Sherali-Adams and the bounded-depth Frege hierarchy, as Sherali-Adams polynomially simulates Resolution. Second, we prove that Sherali-Adams is not ... more >>>