Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR26-301 | 4th November 2026
Pavel Hrubes

Asymptotic non-negative rank can be exponentially smaller than non-negative rank

We investigate the behavior of the non-negative rank of a matrix, $\hbox{rk}_+$, on Kronecker product, $\times$. Beasley et al. [2013] constructed matrices with $\hbox{rk}_+(M\times M)$ strictly smaller than $\hbox{rk}_+(M)^2$.
We will show that i) there exists an $M$ with $\hbox{rk}_+(M\times M)\leq O(\hbox{rk}_+(M)\log(\hbox{rk}_+(M))$.

Defining asymptotic non-negative rank as $\overline{\hbox{rk}}_+(M):= \lim_{k\rightarrow ... more >>>


TR26-300 | 2nd November 2026
Vikraman Arvind, Pushkar Joglekar

Factor Closure in Noncommutative Algebraic Complexity

We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant ... more >>>


TR26-299 | 2nd November 2026
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint