An arithmetic read-once formula (ROF) is a formula (circuit of fan-out
1) over
$+, \times$ where each variable labels at most one leaf.
Every multilinear polynomial can be expressed as the sum of ROFs.
In this work, we prove, for certain multilinear polynomials,
a tight lower bound ... more >>>

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

Polynomial Identity Testing (PIT) algorithms have focused on
polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted
formulas. Read-once polynomials (ROPs) are computed by read-once
formulas (ROFs) and are the simplest of read-restricted polynomials.
Building structures above these, we show the following:
\begin{enumerate}
\item A deterministic polynomial-time non-black-box ... more >>>