Igor Pak

STOC Conference 2025 Conference Paper

Vanishing of Schubert Coefficients

• Igor Pak
• Colleen Robichaux

Schubert coefficients are nonnegative integers that arise in Algebraic Geometry and play a central role in Algebraic Combinatorics. Computing them is both difficult and mysterious. It is known that they are in GapP , but little else is known except in special cases. Notably, it is a major open problem to show that they are in # P in full generality. We study the hardness of vanishing of Schubert coefficients, i.e. whether they are equal to zero. Until this work it was open whether the vanishing is in PH . In fact, it was believed to be not in PH . We prove that the vanishing problem is in coAM assuming the GRH (the Generalized Riemann Hypothesis ). Our approach is based on a reduction to HNP ( Parametric Hilbert’s Nullstellensatz ) recently introduced by Ait El Manssour et al. We then use a completely different approach to show that the non-vanishing of Schubert coefficients is in NP ℂ ∩ P ℝ in the Blum–Shub–Smale (BSS) model of computation. This result is incomparable to the inclusion in AM and underscores the algebraic nature of Schubert coefficients. We apply our approach to show that computing Schubert coefficients is in # P ℂ . This is the first nontrivial upper bound for the problem. We present our results in the generality of all series of classical reductive groups : general linear, special orthogonal, and symplectic groups of complex matrices, corresponding to root systems A , B , C , and D , respectively. With one notable exception, the above results extend to all series.

TCS Journal 2024 Journal Article

Computational complexity of counting coincidences

• Swee Hong Chan
• Igor Pak

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 R 3 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.

STOC Conference 2024 Conference Paper

Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial Hierarchy

• Swee Hong Chan
• Igor Pak

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.

SODA Conference 2023 Conference Paper

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

• Christian Ikenmeyer
• Igor Pak
• Greta Panova

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.

FOCS Conference 2022 Conference Paper

What is in #P and what is not?

• Christian Ikenmeyer
• Igor Pak

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.

STOC Conference 2017 Conference Paper

Complexity of short Presburger arithmetic

• Danny Nguyen
• Igor Pak

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.

FOCS Conference 2017 Conference Paper

Short Presburger Arithmetic Is Hard

• Danny Nguyen
• Igor Pak

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 Σ m P -complete or Π m P -complete, when the first quantifier is ∃ or ∀, respectively. Counting versions and restricted systems are also analyzed.

SODA Conference 2016 Conference Paper

Permutation patterns are hard to count

• Scott Garrabrant
• Igor Pak

Let ℱ ⊂ S k be a finite set of permutations and let C n ( ℱ ) denote the number of permutations σ ∊ S n avoiding the set of patterns ℱ. We prove that { C n ( ℱ )} 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 { C n ( ℱ )} is P-recursive.

TCS Journal 2004 Journal Article

Tilings of rectangles with T-tetrominoes

• Michael Korn
• Igor Pak

We prove that any two tilings of a rectangular region by T-tetrominoes are connected by moves involving only 2 and 4 tiles. We also show that the number of such tilings is an evaluation of the Tutte polynomial. The results are extended to a more general class of regions.

TCS Journal 2003 Journal Article

Tile invariants: new horizons

• Igor Pak

Let T be a finite set of tiles. The group of invariants G( T ), introduced by Pak (Trans. AMS 352 (2000) 5525), is a group of linear relations between the number of copies of tiles in tilings of the same region. We survey known results about G, the height function approach, the local move property, various applications and special cases.

SODA Conference 2002 Conference Paper

Expansion of product replacement graphs

• Alexander Gamburd
• Igor Pak

SODA Conference 2002 Conference Paper

Mixing time and long paths in graphs

• Igor Pak

SODA Conference 2000 Conference Paper

Strong bias of group generators: an obstacle to the "product replacement algorithm"

• László Babai
• Igor Pak

FOCS Conference 2000 Conference Paper

The product replacement algorithm is polynomial

• Igor Pak

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.

STOC Conference 1999 Conference Paper

Lifting Markov Chains to Speed up Mixing

• Fang Chen
• László Lovász 0001
• Igor Pak

SODA Conference 1999 Conference Paper

Using Stopping Times to Bound Mixing Times

• Igor Pak