We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices ... more >>>

We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form
\[
\Sigma^{[r]}\!\wedge^{[d]}\!\Sigma^{[s]}\!\Pi^{[\delta]}.
\]
This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is ... more >>>

We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-knowledge errors (denoted $\epsilon_c$, $\epsilon_s$, and $\epsilon_z$, respectively) that might not be negligible. Under the assumption that there are worst-case hard languages in NP, we show ... more >>>