Pavel Pudlak

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

Siu Man Chan, Aaron Potechin

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

Joshua Grochow

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

Ludwig Staiger

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

Ludwig Staiger

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

Markus BlĂ¤ser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

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

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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

Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal

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