Tata Institute of Fundamental Research
A Largish Sum-of-squares Implies Circuit Hardness (and Derandomization)
STCS Seminar
Speaker:
Prof. Nitin Saxena (Indian Institute of Technology Kanpur
Kanpur, Uttar Pradesh)
Organiser:
Arkadev Chattopadhyay
Date:
Thursday, 23 Jul 2020, 14:00 to 15:00
Venue:
(Scan to add to calendar)
Abstract:
Abstract: We study the sum of squares (*SOS*) representation of polynomials, i.e. f = \sum_{i\in s} c_i f_i^2 , where c_i are field elements and f_i(x_1,\ldots,x_n) are polynomials. We are interested in `measuring' the number of monomials that appear across f_i's; call this *support-sum* S(f). Let the degree of f be d and, for simplicity of exposition, fix n=1. We conjecture: For some *explicit* f and some constant \epsilon > 1/2, S(f) \ge d^\epsilon. We prove that the conjecture implies VP\ne VNP (& blackbox-PIT in QuasiP). A more sophisticated version of the conjecture, for sum-of-cubes representation, implies blackbox-PIT is in P.
Note that S(f) \ge d^{1/2} is trivially achieved. So, compared to this, a marginally better lower bound in the SOS suffices to solve the major questions of algebraic complexity. The *SOS-conjecture* is largely field independent, and is itself supported by a dimension-based fact: It holds for a `randomly chosen' degree-d polynomial f(x).
This is ongoing work with Pranjal Dutta (CMI/IITK) and Thomas Thierauf (Ulm/Aalen).
| Speaker: | Prof. Nitin Saxena (Indian Institute of Technology Kanpur Kanpur, Uttar Pradesh) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Thursday, 23 Jul 2020, 14:00 to 15:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
Abstract: We study the sum of squares (*SOS*) representation of polynomials, i.e. f = \sum_{i\in s} c_i f_i^2 , where c_i are field elements and f_i(x_1,\ldots,x_n) are polynomials. We are interested in `measuring' the number of monomials that appear across f_i's; call this *support-sum* S(f). Let the degree of f be d and, for simplicity of exposition, fix n=1. We conjecture: For some *explicit* f and some constant \epsilon > 1/2, S(f) \ge d^\epsilon. We prove that the conjecture implies VP\ne VNP (& blackbox-PIT in QuasiP). A more sophisticated version of the conjecture, for sum-of-cubes representation, implies blackbox-PIT is in P.
Note that S(f) \ge d^{1/2} is trivially achieved. So, compared to this, a marginally better lower bound in the SOS suffices to solve the major questions of algebraic complexity. The *SOS-conjecture* is largely field independent, and is itself supported by a dimension-based fact: It holds for a `randomly chosen' degree-d polynomial f(x).
This is ongoing work with Pranjal Dutta (CMI/IITK) and Thomas Thierauf (Ulm/Aalen).
Note that S(f) \ge d^{1/2} is trivially achieved. So, compared to this, a marginally better lower bound in the SOS suffices to solve the major questions of algebraic complexity. The *SOS-conjecture* is largely field independent, and is itself supported by a dimension-based fact: It holds for a `randomly chosen' degree-d polynomial f(x).
This is ongoing work with Pranjal Dutta (CMI/IITK) and Thomas Thierauf (Ulm/Aalen).