Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-015 | 9th January 2024 20:16

Degree 2 lower bound for Permanent in arbitrary characteristic

RSS-Feed




TR24-015
Authors: Harpreet Bedi
Publication: 28th January 2024 09:20
Downloads: 155
Keywords: 


Abstract:

An elementary proof of quadratic lower bound for determinantal complexity of the permanent in positive characteristic is stated. This is achieved by constructing a sequence of matrices with zero permanent, but the rank of Hessian is bounded below by a degree two polynomial.



ISSN 1433-8092 | Imprint