Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Markus Bläser:

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

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

TR12-142 | 3rd November 2012
Markus Bläser

Noncommutativity makes determinants hard

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

TR03-071 | 18th August 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Privacy in Non-Private Environments

Revisions: 1

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

TR03-009 | 3rd February 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

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

ISSN 1433-8092 | Imprint