The rank of a matrix has been used a number of times to prove lower
bounds on various types of complexity. In particular it has been used
for the size of monotone formulas and monotone span programs. In most
cases that this approach was used, there is not a single ... more >>>

We prove tight size bounds on monotone switching networks for the NP-complete problem of
$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for
the P-complete problem of generation. This gives alternative proofs of the separations of m-NC
from m-P and of m-NC$^i$ from ... more >>>

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>>

The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested ... more >>>

In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension ... more >>>

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to $\log n$ factor, for any Boolean function composed with $AND$ function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of ... more >>>