2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
linked URL https://indico.math.cnrs.fr/event/8113/
15 17

Computing Sparse Fourier Sum of Squares on Finite Abelian Groups

By Lihong Zhi

The non-negativity of a function on a finite abelian group can be certified by its Fourier sum of squares (FSOS). We propose a method of certifying the nonnegativity of an integer valued function by an FSOS certificate, which is defined to be an FSOS with a small error. We prove the existence of exponentially sparse polynomial and rational FSOS certificates and provide two methods to validate them. As a consequence of the aforementioned existence theorems, we propose a semidefinite programming (SDP)--based algorithm to efficiently compute a sparse FSOS certificate. For applications, we consider certificate problems for maximum satisfiability (MAX-SAT) and maximum k-colorable subgraph (MkCS) and demonstrate our theoretical results and algorithm through numerical experiments.

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.016
  • Cite this video Zhi, Lihong (28/09/2023). Computing Sparse Fourier Sum of Squares on Finite Abelian Groups. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.016
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.016

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback