Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HARPREET BEDI:
All reports by Author Harpreet Bedi:

TR24-015 | 9th January 2024
Harpreet Bedi

Degree 2 lower bound for Permanent in arbitrary characteristic

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.

more >>>



ISSN 1433-8092 | Imprint