Complexity of Proving CSP-based Ideal Membership Problems

Staff - Faculty of Informatics

Date: 9 November 2022 / 14:30 - 17:00

online

You are cordially invited to attend the PhD Dissertation Defence of Arpitha Prasad Bharathi on Wednesday 9 November 2022 at 14:30 on MS Teams.

Abstract:
The polynomial Ideal Membership Problem (IMP) tests if an input multivariate polynomial belongs to a given ideal or not. It is a well-known fundamental problem with many important applications, though notoriously intractable in the general case. We consider the IMP for polynomial ideals encoding combinatorial problems where the input polynomial has degree at most $d=O(1)$ (we call this problem IMP$_d$). A dichotomy result between ``hard'' (NP-hard) and ``easy'' (polynomial time) IMPs was achieved for IMP$_0$ over the Boolean domain in 1978, over any 3-element domain nearly thirty years later, and finally over any finite domain ten years thereafter. This research work expands the known classes of tractability of IMP$_d$ for $d\geq 1$ by relying on the classification of certain combinatorial problems through polymorphisms, and can be used in applications such as Nullstellensatz and Sum-of-Squares proofs.

Dissertation Committee:

  • Prof. Monaldo Mastrolilli, IDSIA USI-SUPSI, Switzerland (Research Advisor)
  • Prof. Luca Maria Gambardella, Università della Svizzera italiana, Switzerland (Research co-Advisor)
  • Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Vikraman Arvind, Institute of Mathematical Sciences, Chennai, India (External Member)
  • Prof. Annie Raymond, University of Massachusetts, USA (External Member)

Faculties