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

__
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

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

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

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

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