6 papers
Two-Cut Coherence of Quintic Forms: Lifting Separations and Second-Derivative Completeness
Karthik Sheshadri
For a homogeneous polynomial f of degree d, the degree-k restricted strength C_k(f) is the least number of products needed to write f with factor degrees k and d-k. We introduce a…
Trellis State Complexity as an Exact Tropical Factorization Rank
Karthik Sheshadri
Let $C\subseteq\F_2^m$ be a binary linear code and let be a bipartition of its coordinates. The \emph{conditional decoding matrix} of at this cut is the matrix…
Contested Cluster Selectors: Local Ambiguity, Normal Forms, and Backtracking Cost in Random Constraint Satisfaction
Karthik Sheshadri
We introduce and empirically investigate \emph{contested cluster selectors} (\CCS): variables that are non-backbone, carry information about solution-cluster identity, and are repe…
The Exact Reach of Conormal Invariants in Determinantal Complexity: a Quadratic No-Go Theorem
Karthik Sheshadri
We study the polar (conormal) method for determinantal-complexity lower bounds, including the framework used in the companion bound dc(sum_i x_i^N) >= (1/(4e)-o(1))N^2. We obtain q…
A near-quadratic lower bound on the border determinantal complexity of via conormal specialization
Karthik Sheshadri
The border determinantal complexity $\dcb(f)$ of a polynomial is the least such that is a limit of determinants of matrices of affine-linear forms. We prove…
A symmetric determinantal lower bound for diagonal power sums via polar degree
Karthik Sheshadri
The symmetric determinantal complexity sdc(f) of a polynomial f is the least m such that f = det(M) for an m x m symmetric matrix M of affine-linear forms. We prove, over the compl…