A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

Given a graph $G$, we consider the problem of finding the largest set
of edge-disjoint triangles contained in $G$. We show that even the
simpler case of decomposing the edges of
a sparse split graph $G$ into edge-disjoint triangles
is NP-complete. We show next that the case of a general ... more >>>

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>