The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles.
Abstract: Generalization error is the gap between an algorithm's performance on the true data distribution (unknown to us) and its performance on the given dataset (known to us).
The problem of chasing convex functions is easy to state: faced with a sequence of convex functions {f_t}, the goal of the algorithm is to output a point x_t at each time, so that the sum of the function costs f_t(x_t), plus the movement costs ||
Games are used to model many instances arising from interaction of more than one computational agent. In program synthesis, existence of strategy is the key in deciding the existence of a program with a given set of specifications.
In this talk we will give a proof of the fact that the two dimensional sphere can be partitioned into finitely many pieces in such a way that a rearrangement of the pieces produces two disjoint copies of the original sphere.
We will study the Decision-Tree complexity of element distinctness using arbitrary binary gates (an instance of which is comparison gates). Concretely, let $m$ and $n$ be natural numbers with $m>n$.