Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Christian Engels:

TR17-174 | 13th November 2017
Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

On Expressing Majority as a Majority of Majorities

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

TR16-153 | 28th September 2016
Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials

Revisions: 3

The power symmetric polynomial on $n$ variables of degree $d$ is defined as
$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers
of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by
... more >>>

ISSN 1433-8092 | Imprint