The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Radu Curticapean - One of the best experts on this subject based on the ideXlab platform.
-
the Exponential Time complexity of counting quantum graph homomorphisms
Workshop on Graph-Theoretic Concepts in Computer Science, 2019Co-Authors: Hubie Chen, Radu Curticapean, Holger DellAbstract:Many graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy for such problems, classifying which target graphs render the problem polynomial-Time solvable or \(\#\mathrm {P}\)-hard. In this paper, we give a new and shorter proof of this theorem, with previously unknown tight lower bounds under the Exponential-Time hypothesis. We similarly strengthen complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs. Both results crucially rely on our main contribution, a complexity dichotomy for evaluating linear combinations of homomorphism numbers to fixed graphs. In the terminology of Lovasz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.
-
block interpolation a framework for tight Exponential Time counting complexity
arXiv: Computational Complexity, 2015Co-Authors: Radu CurticapeanAbstract:We devise a framework for proving tight lower bounds under the counting Exponential-Time hypothesis #ETH introduced by Dell et al. (ACM Transactions on Algorithms, 2014). Our framework allows us to convert classical #P-hardness results for counting problems into tight lower bounds under #ETH, thus ruling out algorithms with running Time $2^{o(n)}$ on graphs with $n$ vertices and $O(n)$ edges. As exemplary applications of this framework, we obtain tight lower bounds under #ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (IPEC 2016).
-
block interpolation a framework for tight Exponential Time counting complexity
International Colloquium on Automata Languages and Programming, 2015Co-Authors: Radu CurticapeanAbstract:We devise a framework for proving tight lower bounds under the counting Exponential-Time hypothesis \(\mathsf {\#ETH}\) introduced by Dell et al. Our framework allows to convert many known \(\mathsf {\#P}\)-hardness results for counting problems into results of the following type: If the given problem admits an algorithm with running Time \(2^{o(n)}\) on graphs with \(n\) vertices and \(\mathcal {O}(n)\) edges, then \(\mathsf {\#ETH}\) fails. As exemplary applications of this framework, we obtain such tight lower bounds for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for two lines.
Thore Husfeldt - One of the best experts on this subject based on the ideXlab platform.
-
Exponential Time complexity of the permanent and the tutte polynomial
arXiv: Computational Complexity, 2012Co-Authors: Holger Dell, Daniel Marx, Thore Husfeldt, Nina Taslaman, Martin WahlenAbstract:We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in Time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. (b) The permanent of an n x n matrix with entries 0 and 1 cannot be computed in Time exp(o(n)). (c) The Tutte polynomial of an n-vertex multigraph cannot be computed in Time exp(o(n)) at most evaluation points (x,y) in the case of multigraphs, and it cannot be computed in Time exp(o(n/polylog n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in Time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH, namely that the satisfying assignments cannot be counted in Time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.
-
the Exponential Time complexity of computing the probability that a graph is connected
arXiv: Computational Complexity, 2010Co-Authors: Thore Husfeldt, Nina TaslamanAbstract:We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires Time Exponential in Omega(m/ log^2 m) for simple graphs of m edges under the Exponential Time Hypothesis.
-
Exponential Time complexity of the permanent and the tutte polynomial
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Holger Dell, Thore Husfeldt, Martin WahlenAbstract:The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of n-variable 3-CNF formulas requires Time exp(Ω(n)). We relax this hypothesis by introducing its counting version #;ETH, namely that every algorithm that counts the satisfying assignments requires Time exp(Ω(n)). We transfer the sparsification lemma for d-CNF formulas to the counting setting, which makes #ETH robust. Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an n×n matrix with m nonzero entries requires Time exp(Ω(m)). Restricted to 01-matrices, the bound is exp(Ω(m/logm)). Computing the Tutte polynomial of a multigraph with n vertices and m edges requires Time exp(Ω(n)) at points (x, y) with (x - 1)(y - 1) ≠ = 1 and y ∉ {0,±1}. At points (x, 0) with x ∉ {0,±1} it requires Time exp(Ω(n)), and if x = -2,-3, ..., it requires Time exp(Ω(m)). For simple graphs, the bound is exp(Ω(m/log3 m)).
-
the Exponential Time complexity of computing the probability that a graph is connected
Lecture Notes in Computer Science; 6198 pp 192-203 (2010), 2010Co-Authors: Thore Husfeldt, Nina TaslamanAbstract:We show that computation of all-terminal graph reliability requires Time Exponential in Ω(m/ log2 m) for simple graphs of m edges under the Exponential Time Hypothesis.
-
computing the tutte polynomial in vertex Exponential Time
Foundations of Computer Science, 2008Co-Authors: Andreas Bjorklund, Petteri Kaski, Thore Husfeldt, Mikko KoivistoAbstract:The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in Time roughly proportional to the number of spanning trees in the input graph.Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in Time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.
Jesper Nederlof - One of the best experts on this subject based on the ideXlab platform.
-
hamiltonian cycle parameterized by treedepth in single Exponential Time and polynomial space
Workshop on Graph-Theoretic Concepts in Computer Science, 2020Co-Authors: Jesper Nederlof, Michal Pilipczuk, Celine M F Swennenhuis, Karol WegrzyckiAbstract:For many algorithmic problems on graphs of treewidth \(t\), a standard dynamic programming approach gives an algorithm with Time and space complexity \(2^{\mathcal {O}(t)}\cdot n^{\mathcal {O}(1)}\). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining Time complexity of the form \(2^{\mathcal {O}(d)}\cdot n^{\mathcal {O}(1)}\), where \(d\) is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with Time and space complexity \(2^{\mathcal {O}(t\log t)}\cdot n^{\mathcal {O}(1)}\) on graphs of treewidth \(t\), but it is not clear how to convert them into Time-efficient polynomial space algorithms for graphs of low treedepth.
-
hamiltonian cycle parameterized by treedepth in single Exponential Time and polynomial space
arXiv: Data Structures and Algorithms, 2020Co-Authors: Jesper Nederlof, Michal Pilipczuk, Celine M F Swennenhuis, Karol WegrzyckiAbstract:For many algorithmic problems on graphs of treewidth $t$, a standard dynamic programming approach gives an algorithm with Time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining Time complexity of the form $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$, where $d$ is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with Time and space complexity $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$ on graphs of treewidth $t$, but it is not clear how to convert them into Time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. (FOCS'11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in Time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running Time $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$ and polynomial space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit $5^d\cdot n^{\mathcal{O}(1)}$-Time and polynomial space algorithms on graphs of treedepth $d$. The algorithms are randomized Monte Carlo with only false negatives.
-
new tools and connections for Exponential Time approximation
Algorithmica, 2019Co-Authors: Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper NederlofAbstract:In this paper, we develop new tools and connections for Exponential Time approximation. In this setting, we are given a problem instance and an integer r>1, and the goal is to design an approximation algorithm with the fastest possible running Time. We give randomized algorithms that establish an approximation ratio of 1. r for maximum independent set in O∗(exp(O~(n/rlog2r+rlog2r))) Time, 2. r for chromatic number in O∗(exp(O~(n/rlogr+rlog2r))) Time, 3. (2−1/r) for minimum vertex cover in O∗(exp(n/rΩ(r))) Time, and 4. (k−1/r) for minimum k-hypergraph vertex cover in O∗(exp(n/(kr)Ω(kr))) Time. (Throughout, O~ and O∗ omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known Time bounds for all problems were O∗(2n/r) (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-Time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp(n1−o(1)/r1+o(1)) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subExponential-Time. Ph.D. thesis, 2014). Our results show that the naturally-looking O∗(2n/r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and Exponential-Time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan’s PCP (Chan in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).
-
new tools and connections for Exponential Time approximation
arXiv: Data Structures and Algorithms, 2017Co-Authors: Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper NederlofAbstract:In this paper, we develop new tools and connections for Exponential Time approximation. In this setting, we are given a problem instance and a parameter $\alpha>1$, and the goal is to design an $\alpha$-approximation algorithm with the fastest possible running Time. We show the following results: - An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r \log^2 r+r\log^2r)))$ Time, - An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log r+r\log^2r)))$ Time, - A $(2-1/r)$-approximation for minimum vertex cover in $O^*(\exp(n/r^{\Omega(r)}))$ Time, and - A $(k-1/r)$-approximation for minimum $k$-hypergraph vertex cover in $O^*(\exp(n/(kr)^{\Omega(kr)}))$ Time. (Throughout, $\tilde O$ and $O^*$ omit $\mathrm{polyloglog}(r)$ and factors polynomial in the input size, respectively.) The best known Time bounds for all problems were $O^*(2^{n/r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008]. For maximum independent set and chromatic number, these bounds were complemented by $\exp(n^{1-o(1)}/r^{1+o(1)})$ lower bounds (under the Exponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit, 2014 (Ph.D. Thesis)]. Our results show that the naturally-looking $O^*(2^{n/r})$ bounds are not tight for all these problems. The key to these algorithmic results is a sparsification procedure, allowing the use of better approximation algorithms for bounded degree graphs. For obtaining the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and Exponential-Time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP [Chan, 2016]. It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].
-
deterministic single Exponential Time algorithms for connectivity problems parameterized by treewidth
International Colloquium on Automata Languages and Programming, 2013Co-Authors: Hans L Bodlaender, Marek Cygan, Stefan Kratsch, Jesper NederlofAbstract:It is well known that many local graph problems, like Vertex Cover?and Dominating Set, can be solved in Time 2 O ( tw ) | V | O ( 1 ) for graphs G = ( V , E ) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long Time we did not know how to do this faster than tw O ( tw ) | V | O ( 1 ) . Recently, Cygan et al.?(FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in Time c tw | V | O ( 1 ) for a small constant c, e.g., for Hamiltonian Cycle?and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runTime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runTime in terms of the weights).We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c tw | V | O ( 1 ) Time algorithms, also for weighted and counting versions. For example, in this Time we can solve Traveling Salesman? or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
Magnus Wahlstrom - One of the best experts on this subject based on the ideXlab platform.
-
tight lower bounds for the workflow satisfiability problem based on the strong Exponential Time hypothesis
Information Processing Letters, 2016Co-Authors: Gregory Gutin, Magnus WahlstromAbstract:The Workflow Satisfiability Problem (WSP) is a problem used in access control.The WSP is parameterized by the number of steps.The WSP is considered for regular and user-independent constraints.Tight lower bounds are proved for WSP algorithms with the two types of constraints. The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equal constraints. Since the number of steps k is relatively small in practice, Wang and Li (2010) 21 introduced a parametrisation of WSP by k. Wang and Li (2010) 21 showed that, in general, the WSP is W1-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) 10 and Cohen et al. (2014) 6 designed FPT algorithms of running Time O * ( 2 k ) and O * ( 2 k log 2 ? k ) for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running Time O * ( 2 c k ) and O * ( 2 c k log 2 ? k ) for the two restrictions of WSP, respectively, with any c < 1 , unless the Strong Exponential Time Hypothesis fails.
-
tight lower bounds for the workflow satisfiability problem based on the strong Exponential Time hypothesis
arXiv: Data Structures and Algorithms, 2015Co-Authors: Gregory Gutin, Magnus WahlstromAbstract:The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$. Wang and Li (2010) showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) and Cohen et al. (2014) designed FPT algorithms of running Time $O^*(2^{k})$ and $O^*(2^{k\log_2 k})$ for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running Time $O^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$, unless the Strong Exponential Time Hypothesis fails.
-
new plain Exponential Time classes for graph homomorphism
Theory of Computing Systems \ Mathematical Systems Theory, 2011Co-Authors: Magnus WahlstromAbstract:A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running Time of O *(n(H)cn(G)) (the notation O *(⋅) signifies that polynomial factors have been ignored) for a constant 0
-
new plain Exponential Time classes for graph homomorphism
Computer Science Symposium in Russia, 2009Co-Authors: Magnus WahlstromAbstract:A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f : V (G ) ***V (H ) such that if uv *** E (G ) then f (u )f (v ) *** E (H ). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running Time of O *n (H ) cn (G ), for a constant 0 < c < 1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-Exponential Time, i.e. in Time O *c n (G ) + n (H ) for some constant c . Previous research has identified two such restrictions. If H = K k or contains K k as a core (i.e. a homomorphically equivalent subgraph), then Hom (G,H) is the k -coloring problem, which can be solved in Time O *2 n (G ) (Bjorklund, Husfeldt, Koivisto); and if H has treewidth at most k , then Hom (G,H) can be solved in Time O *(k + 3) n (G ) (Fomin, Heggernes, Kratsch, 2007). We extend these results to cases of bounded cliquewidth: if H has cliquewidth at most k , then we can count the number of homomorphisms from G to H in Time O *(2k + 1) max (n (G ),n (H )), including the Time for finding a k -expression for H . The result extends to deciding HomG,H) when H has a core with a k -expression, in this case with a somewhat worse running Time. If G has cliquewidth at most k , then a similar result holds, with a worse dependency on k : We are able to count Hom (G,H) in Time roughly O *(2k + 1) n (G ) + 22kn (H ), and this also extends to when G has a core of cliquewidth at most k with a similar running Time.
Holger Dell - One of the best experts on this subject based on the ideXlab platform.
-
the Exponential Time complexity of counting quantum graph homomorphisms
Workshop on Graph-Theoretic Concepts in Computer Science, 2019Co-Authors: Hubie Chen, Radu Curticapean, Holger DellAbstract:Many graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy for such problems, classifying which target graphs render the problem polynomial-Time solvable or \(\#\mathrm {P}\)-hard. In this paper, we give a new and shorter proof of this theorem, with previously unknown tight lower bounds under the Exponential-Time hypothesis. We similarly strengthen complexity dichotomies by Focke, Goldberg, and Živný (SODA 2018) for counting surjective homomorphisms to fixed graphs. Both results crucially rely on our main contribution, a complexity dichotomy for evaluating linear combinations of homomorphism numbers to fixed graphs. In the terminology of Lovasz (Colloquium Publications 2012), this amounts to counting homomorphisms to quantum graphs.
-
Exponential Time complexity of the permanent and the tutte polynomial
arXiv: Computational Complexity, 2012Co-Authors: Holger Dell, Daniel Marx, Thore Husfeldt, Nina Taslaman, Martin WahlenAbstract:We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in Time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. (b) The permanent of an n x n matrix with entries 0 and 1 cannot be computed in Time exp(o(n)). (c) The Tutte polynomial of an n-vertex multigraph cannot be computed in Time exp(o(n)) at most evaluation points (x,y) in the case of multigraphs, and it cannot be computed in Time exp(o(n/polylog n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in Time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH, namely that the satisfying assignments cannot be counted in Time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.
-
Exponential Time complexity of the permanent and the tutte polynomial
International Colloquium on Automata Languages and Programming, 2010Co-Authors: Holger Dell, Thore Husfeldt, Martin WahlenAbstract:The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of n-variable 3-CNF formulas requires Time exp(Ω(n)). We relax this hypothesis by introducing its counting version #;ETH, namely that every algorithm that counts the satisfying assignments requires Time exp(Ω(n)). We transfer the sparsification lemma for d-CNF formulas to the counting setting, which makes #ETH robust. Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an n×n matrix with m nonzero entries requires Time exp(Ω(m)). Restricted to 01-matrices, the bound is exp(Ω(m/logm)). Computing the Tutte polynomial of a multigraph with n vertices and m edges requires Time exp(Ω(n)) at points (x, y) with (x - 1)(y - 1) ≠ = 1 and y ∉ {0,±1}. At points (x, 0) with x ∉ {0,±1} it requires Time exp(Ω(n)), and if x = -2,-3, ..., it requires Time exp(Ω(m)). For simple graphs, the bound is exp(Ω(m/log3 m)).
