@inproceedings{10.1145/3055399.3055435,
    Abstract = {We study complexity of short sentences in Presburger arithmetic (Short-PA). Here by ``short'' we mean sentences with a bounded number of variables, quantifers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. We prove that assuming Kannan's partition can be found in polynomial time, the satisfability of Short-PA sentences can be decided in polynomial time. Furthermore, under the same assumption, we show that the numbers of satisfying assignments of short Presburger sentences can also be computed in polynomial time.},
    Address = {New York, NY, USA},
    Author = {Nguyen, Danny and Pak, Igor},
    BookTitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing},
    File = {Complexity of short Presburger arithmetic - 1704.00249.pdf},
    ISBN = {9781450345286},
    Keywords = {Presburger arithmetic, Barvinok\'{z}s algorithm, integer programming, Kannan\'{z}s partition theorem},
    Location = {Montreal, Canada},
    Pages = {812--820},
    Publisher = {Association for Computing Machinery},
    Series = {STOC 2017},
    Title = {Complexity of Short Presburger Arithmetic},
    URL = {https://doi.org/10.1145/3055399.3055435},
    Year = {2017},
    bdsk-url-1 = {https://doi.org/10.1145/3055399.3055435},
    date-added = {2021-09-14 16:48:44 +0200},
    date-modified = {2021-09-14 16:48:44 +0200},
    numpages = {9},
    doi = {10.1145/3055399.3055435}
}

@inproceedings{10.1145/3055399.3055435, Abstract = {We study complexity of short sentences in Presburger arithmetic (Short-PA). Here by ``short'' we mean sentences with a bounded number of variables, quantifers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. We prove that assuming Kannan's partition can be found in polynomial time, the satisfability of Short-PA sentences can be decided in polynomial time. Furthermore, under the same assumption, we show that the numbers of satisfying assignments of short Presburger sentences can also be computed in polynomial time.}, Address = {New York, NY, USA}, Author = {Nguyen, Danny and Pak, Igor}, BookTitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing}, File = {Complexity of short Presburger arithmetic - 1704.00249.pdf}, ISBN = {9781450345286}, Keywords = {Presburger arithmetic, Barvinok\'{z}s algorithm, integer programming, Kannan\'{z}s partition theorem}, Location = {Montreal, Canada}, Pages = {812--820}, Publisher = {Association for Computing Machinery}, Series = {STOC 2017}, Title = {Complexity of Short Presburger Arithmetic}, URL = {https://doi.org/10.1145/3055399.3055435}, Year = {2017}, bdsk-url-1 = {https://doi.org/10.1145/3055399.3055435}, date-added = {2021-09-14 16:48:44 +0200}, date-modified = {2021-09-14 16:48:44 +0200}, numpages = {9}, doi = {10.1145/3055399.3055435} }