Quasi-polynomial growth

This article is about a growth rate that is exponential in a polylogarithmic function. For polynomials with periodically varying coefficients, see quasi-polynomial.

In theoretical computer science, a function ${\displaystyle f(n)}$ is said to exhibit quasi-polynomial growth when it has an upper bound of the form

$${\displaystyle f(n)=2^{O{\bigl (}(\log n)^{c}{\bigr )}}}$$

for some constant ${\displaystyle c}$, as expressed using big O notation. That is, it is bounded by an exponential function of a polylogarithmic function. This generalizes the polynomials and the functions of polynomial growth, for which one can take ${\displaystyle c=1}$. A function with quasi-polynomial growth is also said to be quasi-polynomially bounded.^[1]

Quasi-polynomial growth has been used in the analysis of algorithms to describe certain algorithms whose computational complexity is not polynomial, but is substantially smaller than exponential. In particular, algorithms whose worst-case running times exhibit quasi-polynomial growth are said to take quasi-polynomial time.^[2] As well as time complexity, some algorithms require quasi-polynomial space complexity,^[3] use a quasi-polynomial number of parallel processors,^[4] can be expressed as algebraic formulas of quasi-polynomial size^[2] or have a quasi-polynomial competitive ratio.^[5] In some other cases, quasi-polynomial growth is used to model restrictions on the inputs to a problem that, when present, lead to good performance from algorithms on those inputs.^[1] It can also bound the size of the output for some problems; for instance, for the shortest path problem with linearly varying edge weights, the number of distinct solutions can be quasipolynomial.^[6][7]

Beyond theoretical computer science, quasi-polynomial growth bounds have also been used in mathematics, for instance in partial results on the Hirsch conjecture for the diameter of polytopes in polyhedral combinatorics,^[8] or relating the sizes of cliques and independent sets in certain classes of graphs.^[9] However, in polyhedral combinatorics and enumerative combinatorics, a different meaning of the same word also is used, for the quasi-polynomials, functions that generalize polynomials by having periodic coefficients.^[10]

References

1. Ackermann, Heiner; Newman, Alantha; Röglin, Heiko; Vöcking, Berthold (2007), "Decision-making based on approximate and smoothed Pareto curves", Theoretical Computer Science, 378 (3): 253–270, doi:10.1016/j.tcs.2007.02.034, MR 2325290
2. von zur Gathen, Joachim (1987), "Feasible arithmetic computations: Valiant's hypothesis", Journal of Symbolic Computation, 4 (2): 137–172, doi:10.1016/S0747-7171(87)80063-9, MR 0922386
3. Fearnley, John; Jain, Sanjay; de Keijzer, Bart; Schewe, Sven; Stephan, Frank; Wojtczak, Dominik (2019), "An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space", Int. J. Softw. Tools Technol. Transf., 21 (3): 325–349, arXiv:1703.01296, doi:10.1007/S10009-019-00509-3
4. Fenner, Stephen; Gurjar, Rohit; Thierauf, Thomas (2021), "Bipartite perfect matching is in quasi-NC", SIAM Journal on Computing, 50 (3): 218–235, arXiv:1601.06319, doi:10.1137/16M1097870, MR 4277935
5. Bosek, Bartlomiej; Krawczyk, Tomasz (2010), "The sub-exponential upper bound for on-line chain partitioning", 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, IEEE Computer Society, pp. 347–354, doi:10.1109/FOCS.2010.40
6. Carstensen, Patricia June (1983), The complexity of some problems in parametric linear and combinatorial programming, Doctoral dissertation, University of Michigan, ProQuest 303275648
7. Barth, Florian; Funke, Stefan; Proissl, Claudius (2022), "An upper bound on the number of extreme shortest paths in arbitrary dimensions", in Chechik, Shiri; Navarro, Gonzalo; Rotenberg, Eva; Herman, Grzegorz (eds.), 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, LIPIcs, vol. 244, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 14:1–14:12, doi:10.4230/LIPICS.ESA.2022.14
8. Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, New Series, 26 (2): 315–316, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448
9. Pilipczuk, Marek; Sokołowski, Michał (2023), "Graphs of bounded twin-width are quasi-polynomially ${\displaystyle \chi }$ -bounded", Journal of Combinatorial Theory, Series B, 161: 382–406, arXiv:2202.07608, doi:10.1016/j.jctb.2023.02.006, MR 4568111
10. McAllister, Tyrrell B.; Woods, Kevin M. (2005), "The minimum period of the Ehrhart quasi-polynomial of a rational polytope", Journal of Combinatorial Theory, Series A, 109 (2): 345–352, arXiv:math/0310255, doi:10.1016/j.jcta.2004.08.006, MR 2121031