• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Seminar of the laboratory: "On the complexity of quantified integer programming". Lecturer: D. Chistikov

Event ended

On June 20, 2018 Dmitry Chistikov will give a lecture "On the complexity of quantified integer programming".

Address: Faculty of computer science HSE, Kochnovsky proezd, 3.
Language: English
Time: 18:10-19:30
Hall: 503
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.

Abstract

Quantified integer programming is the problem of deciding assertions of the form "for all/there exists x_k ... for all x_2 there exists x_1 such that A x >= c", where vectors of variables x_k, ..., x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes. We show that quantified integer programming with alternation depth k is complete for the k-th level of the polynomial hierarchy.
Joint work with Christoph Haase.