Computational Complexity

We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomised algorithm for the following problem: If a homogeneous polynomial $f\in K[x_1,...,x_n]$ (where $K\subseteq \mathbb{C}$) of degree d is given as a blackbox, decide ...

This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs), a.k.a. (Ordinary) Difference Equations. It presents a new framework using these equations as a central tool for computation and ...

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-...${\mathsf{}}^{\mathsf{}}\mathsf{}\mathsf{}$${\mathsf{}}^{\mathsf{}}\mathsf{}\mathsf{}$

We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with ...

We study the power of preprocessing adversaries in finding bounded-length collisions in the widely used Merkle-Damgård (MD) hashing in the random oracle model. Specifically, we consider adversaries with arbitrary S-bit advice about the random ...

Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and $(x,y)\mapsto x·2^y$. The same authors applied power circuits to give a ...

For a natural number $m$, a distribution is called $m$-grained, if each element appears with probability that is an integer multiple of $1/m$. We prove that, for any constant $c<1$, testing whether a distribution over $[\mathrm{\Theta }(m)]$ is $m$-grained requires $\mathrm{\Omega }(m^c)$ ...

While it can be easily shown by counting that almost all Boolean predicates of n variables have circuit size $\mathrm{\Omega }(2^n/n)$, we have no example of an NP function requiring even a superlinear number of gates. Moreover, only modest linear lower bounds are ...$\mathrm{}$$$