A large class of problems in symbolic computation can be expressed as the task of
computing some polynomials; and arithmetic circuits form the most standard model for …

This paper initiates a systematic development of a theory of non-commutative optimization, a
setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and …

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic
questions, have a remarkablenumber of diverse origins and motivations. They …

We propose a new second-order method for geodesically convex optimization on the natural
hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling …

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs)
are codes that allow the recovery of each message bit from a constant number of entries of …

In this paper, we present a deterministic polynomial time algorithm for testing whether a
symbolic matrix in non-commuting variables over QQ is invertible or not. The analogous …

Progress on Polynomial Identity Testing Page 1 Bulletin of the EATCS no 99, pp. 49 79,
October 2009 Oc European Association for Theoretical Computer Science T C …

An arithmetic formula is multilinear if the polynomial computed by each of its subformulas is
multilinear. We prove that any multilinear arithmetic formula for the permanent or the …

We study the problem of obtaining efficient, deterministic, black-box polynomial identity
testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and …

Cyber-physical system applications such as autonomous vehicles, wearable devices, and
avionic systems generate a large volume of time-series data. Designers often look for tools …