Describing the equality conditions of the Alexandrov–Fenchel inequality has been a major open problem for decades. We prove that for a natural class of convex polytopes, the equality cases of the AF inequality are not in unless the polynomial hierarchy collapses to a finite level. This is the first hardness result for the problem. The proof involves Stanley’s order polytopes and a delicate analysis of linear extensions of finite posets, with some number theoretic results added to the mix. We also give applications to combinatorial interpretations of the defect of Stanley’s log-concave inequality for the number of linear extensions.

Can you decide if there is a coincidence in the numbers counting two different combinatorial objects? For example, can you decide if two regions in R3 have the same number of domino tilings? There are two versions of the problem, with 2×1×1 and 2×2×1 boxes. We prove that in both cases the coincidence problem is not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level. While the conclusions are the same, the proofs are notably different and generalize in different directions. We proceed to explore the coincidence problem for counting independent sets and matchings in graphs, matroid bases, order ideals and linear extensions in posets, permutation patterns, and the Kronecker coefficients. We also make a number of conjectures for counting other combinatorial objects such as plane triangulations, contingency tables, standard Young tableaux, reduced factorizations and the Littlewood–Richardson coefficients.

We prove that deciding the vanishing of the character of the symmetric group is C=P-complete. We use this hardness result to prove that the absolute value and also the square of the character are not contained in #P, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is PP-complete under many-one reductions, and hence PH-hard under Turing-reductions.

Abstract. We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner–Wachs inequality and generalize it to inequalities on order polynomials and their q-analogues via direct injections and Fortuin–Kasteleyn–Ginibre inequalities. Second, we give an injective proof of Sidorenko’s inequality with computational complexity significance, namely, that the difference is in #P. Third, we generalize actions of Coxeter groups on restricted linear extensions, leading to vanishing and uniqueness conditions for the generalized Stanley inequality. We also establish several new inequalities on order polynomials and prove an asymptotic version of Graham’s inequality.

For several classical nonnegative integer functions we investigate if they are members of the counting complexity class # P or not. We prove # P membership in surprising cases, and in other cases we prove non-membership, relying on standard complexity assumptions or on oracle separations. We initiate the study of the polynomial closure properties of # P on affine varieties, i.e., if all problem instances satisfy algebraic constraints. This is directly linked to classical combinatorial proofs of algebraic identities and inequalities. We investigate # TFNP and obtain oracle separations that prove the strict inclusion of # P in all standard syntactic subclasses of # TFNP minus 1.

We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by “short” we mean sentences with a bounded number of variables, quantifiers, inequalities, and Boolean operations; the input consists only of the integer coefficients involved in the linear inequalities. We prove that satisfiability of Short-PA sentences with $m+2$ alternating quantifiers is $\Sigma^{\mathsf{P}}_m$-complete or $\Pi^{\mathsf{P}}_m$-complete when the first quantifier is $\exists$ or $\forall$, respectively. Counting versions and restricted systems are also analyzed. Further applications are given to hardness of two natural problems in integer optimization.

We consider Presburger arithmetic (PA) extended by scalar multiplication by an algebraic irrational number $\alpha$, and call this extension $\alpha$-Presburger arithmetic ($\alpha$-PA). We show that the complexity of deciding sentences in $\alpha$-PA is substantially harder than in PA. Indeed, when $\alpha$ is quadratic and $r\geq 4$, deciding $\alpha$-PA sentences with $r$ alternating quantifier blocks and at most $c\ r$ variables and inequalities requires space at least $K 2^{\cdot^{\cdot^{\cdot^{2^{C\ell(S)}}}}}$ (tower of height $r-3$), where the constants $c, K, C>0$ only depend on $\alpha$, and $\ell(S)$ is the length of the given $\alpha$-PA sentence $S$. Furthermore deciding $\exists^{6}\forall^{4}\exists^{11}$ $\alpha$-PA sentences with at most $k$ inequalities is PSPACE-hard, where $k$ is another constant depending only on~$\alpha$. When $\alpha$ is non-quadratic, already four alternating quantifier blocks suffice for undecidability of $\alpha$-PA sentences.

We extend the Barvinok--Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger arithmetic. We also give an application to the $k$-Frobenius problem.

We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan, which together say that integer programming with at most two alternating quantifiers can be done in polynomial time for a fixed number of variables. As a byproduct of the proof, we show that for two polytopes P, Q in R^4, counting the projection of integer points in Q\P is #P-complete. This contrasts the 2003 result by Barvinok and Woods, which allows counting in polynomial time the projection of integer points in P and Q separately.

We study the computational complexity of short sentences in Presburger arithmetic (SHORT-PA). Here by “short” we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integer coefficients involved in the linear inequalities. We prove that satisfiability of SHORT-PA sentences with m+2 alternating quantifiers is ΣmP-complete or ΠmP-complete, when the first quantifier is ∃ or ∀, respectively. Counting versions and restricted systems are also analyzed.

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.

The Naruse hook-length formula is a recent general formula for the number of standard Young tableaux of skew shapes, given as a positive sum over excited diagrams of products of hook-lengths. In [A. H. Morales, I. Pak, and G. Panova, Hook Formulas for Skew Shapes I. $q$-Analogues and Bijections] we gave two different $q$-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. In this paper we give an elementary proof of Naruse's formula based on the case of border strips. For special border strips, we obtain curious new formulas for the Euler and $q$-Euler numbers in terms of certain Dyck path summations.

Let ℱ ⊂ Sk be a finite set of permutations and let Cn(ℱ) denote the number of permutations σ ∊ Sn avoiding the set of patterns ℱ. We prove that {Cn (ℱ)} cannot be computed in time polynomial in n, unless EXP = ⊕EXP. Our tools also allow us to disprove the Noonan–Zeilberger conjecture which states that the sequence {Cn(ℱ)} is P-recursive.

We study the problem of acute triangulations of convex polyhedra and the space ℜn. Here an acute triangulation is a triangulation into simplices whose dihedral angles are acute. We prove that acute triangulations of the n-cube do not exist for n ≥ 4. Further, we prove that acute triangulations of the space ℜn do not exist for n ≥ 5. In the opposite direction, in ℜ3 we construct nontrivial acute triangulations of all Platonic solids. We also prove nonexistence of an acute triangulation of ℜ4 if all dihedral angles are bounded away from ϒ/2.

We introduce notions of linear reduction and linear equivalence of bijections for the purposes of studying bijections between Young tableaux. Originating in theoretical computer science, these notions allow us to give a unified view of a number of classical bijections and establish formal connections between them.

The product replacement algorithm is a heuristic designed to generate random group elements. The idea is to run a random walk on generating /spl kappa/-tuples of the group, and then output a random component. The algorithm was designed by C.R. Leedham-Green, and further investigated by F. Cellar et al. (1995). It was found to have an outstanding performance, much better than the previously known algorithms (P. Diaconis and L. Saloff-Coste, 1996). The algorithm is now included in two major group algebra packages: GAP (M. Scheonert et al., 1995) and MAGMA (W. Bosma et al., 1997). In spite of the many serious attempts and partial results, the analysis of the algorithm remains difficult at best. For small values of /spl kappa/, even graph connectivity becomes a serious obstacle. The most general results are due to Diaconis and Saloff-Coste, who used a state of the art analytic technique to obtain polynomial bounds in special cases, and (sub)-exponential bounds in the general case. The main result of the paper is a polynomial upper bound for the cost of the algorithm, provided /spl kappa/ is large enough.

Article Free Access Share on On sampling generating sets of finite groups and product replacement algorithm: extended abstract Authors: Igor Pak Department of Mathematics, Yale University, New Haven, CT Department of Mathematics, Yale University, New Haven, CTView Profile , Sergey Bratus Department of Mathematics, Northeastern University, Boston, MA Department of Mathematics, Northeastern University, Boston, MAView Profile Authors Info & Claims ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computationJuly 1999Pages 91–96https://doi.org/10.1145/309831.309871Published:01 July 1999Publication History 5citation250DownloadsMetricsTotal Citations5Total Downloads250Last 12 Months21Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

There are several examples where the mixing time of a Markov chain can be reduced substantially, often to about its square root, by "lifting", i.e., by splitting each state into several states.In several examples of random walks on groups, the lifted chain not only mixes better, but is easier to analyze.We characterize the best mixing time achievable through lifting in terms of multicommodity flows.We show that the reduction to square root is best possible.If the lifted chain is time-reversible, then the gain is smaller, at most a factor of log(l/na), where 110 is the smallest stationary probability of any state.We give an example showing that a gain of a factor of log(l/~o)/log log(l/rro) is possible.