All reports by Author Markus Bläser:

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
TR18-064
| 3rd April 2018
__

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Generalized Matrix Completion and Algebraic Natural Proofs

__
TR16-145
| 16th September 2016
__

Markus Bläser, Gorav Jindal, Anurag Pandey#### Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Revisions: 2

__
TR12-142
| 3rd November 2012
__

Markus Bläser#### Noncommutativity makes determinants hard

__
TR03-071
| 18th August 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Privacy in Non-Private Environments

Revisions: 1

__
TR03-009
| 3rd February 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

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

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

Markus Bläser, Gorav Jindal, Anurag Pandey

We consider the problem of commutative rank computation of a given matrix space, $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is $n$, subsumes problems such as testing perfect matching in graphs ... more >>>

Markus Bläser

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that $A$ is fixed. We obtain the following dichotomy: If $A/rad(A)$ is noncommutative, then computing the determinant over $A$ is hard. ``Hard'' here means $\#P$-hard over fields of characteristic $0$ and $ModP_p$-hard over ... more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study private computations in information-theoretical settings on

networks that are not 2-connected. Non-2-connected networks are

``non-private'' in the sense that most functions cannot privately be

computed on such networks. We relax the notion of privacy by

introducing lossy private protocols, which generalize private

protocols. We measure the information each ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study the role of connectivity of communication networks in private

computations under information theoretic settings. It will be shown that

some functions can be computed by private protocols even if the

underlying network is 1-connected but not 2-connected. Then we give a

complete characterisation of non-degenerate functions that can ...
more >>>