Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR25-062 | 13th May 2025
Prerona Chatterjee, Anamay Tengse

Lower Bounds from Succinct Hitting Sets

We investigate the consequences of the existence of ``efficiently describable'' hitting sets for polynomial sized algebraic circuit (VP), in particular, \emph{VP-succinct hitting sets}.
Existence of such hitting sets is known to be equivalent to a ``natural-proofs-barrier'' towards algebraic circuit lower bounds, from the works that introduced this concept (Forbes ... more >>>


TR25-061 | 10th May 2025
Partha Mukhopadhyay, C Ramya, Pratik Shastri

Efficient Polynomial Identity Testing Over Nonassociative Algebras

We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrubeš, Yehudayoff, and Wigderson (CCC 2010) and Fijalkow, Lagarde, Ohlmann, ... more >>>


TR25-060 | 6th May 2025
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

Sign-Rank of $k$-Hamming Distance is Constant

We prove that the sign-rank of the $k$-Hamming Distance matrix on $n$ bits is $2^{O(k)}$, independent of the number of bits $n$. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (RANDOM 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the ... more >>>



Next next


ISSN 1433-8092 | Imprint