More Like this

1. Proof Complexity Lower Bounds from Algebraic Circuit Complexity

   https://doi.org/10.4086/toc.2021.v017a010  

   Forbes, Michael A. ; Shpilka, Amir ; Tzameret, Iddo ; Wigderson, Avi ( January 2021 , Theory of Computing)

   Raz, Ran (Ed.)

   We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem. 

   more » « less
2. Principal Specialization of Dual Characters of Flagged Weyl Modules

   https://doi.org/10.37236/10460  

   Mészáros, Karola ; St. Dizier, Avery ; Tanjaya, Arthur ( October 2021 , The Electronic Journal of Combinatorics)

   Schur polynomials are special cases of Schubert polynomials, which in turn are special cases of dual characters of flagged Weyl modules. The principal specialization of Schur and Schubert polynomials has a long history, with Macdonald famously expressing the principal specialization of any Schubert polynomial in terms of reduced words. We prove a lower bound on the principal specialization of dual characters of flagged Weyl modules. Our result yields an alternative proof of a conjecture of Stanley about  the principal specialization of Schubert polynomials, originally proved by Weigandt. 

   more » « less
3. Metaplectic representations of Hecke algebras, Weyl group actions, and associated polynomials

   https://doi.org/10.1007/s00029-021-00654-1  

   Sahi, Siddhartha ; Stokman, Jasper V. ; Venkateswaran, Vidya ( July 2021 , Selecta Mathematica)

   null (Ed.)

   Abstract We construct a family of representations of affine Hecke algebras, which depend on a number of auxiliary parameters $$g_i$$ g i , and which we refer to as metaplectic representations. We realize these representations as quotients of certain parabolically induced modules, and we apply the method of Baxterization (localization) to obtain actions of corresponding Weyl groups on rational functions on the torus. Our construction both generalizes and provides a conceptual proof of earlier results of Chinta, Gunnells, and Puskas, which had depended on a crucial computer verification. A key motivation is that when the parameters $$g_i$$ g i are specialized to certain Gauss sums, the resulting representation and its localization arise naturally in the consideration of p -parts of Weyl group multiple Dirichlet series. In this special case, similar results have been previously obtained in the literature by the study of Iwahori Whittaker functions for principal series of metaplectic covers of reductive p -adic groups. However this technique is not available for generic parameters $$g_i$$ g i . It turns out that the metaplectic representations can be extended to the double affine Hecke algebra, where they share many important properties with Cherednik’s basic polynomial representation, which they generalize. This allows us to introduce families of metaplectic polynomials, which depend on the $$g_i$$ g i , and which generalize Macdonald polynomials. In this paper we discuss in some detail the situation for type A , which is of considerable interest in algebraic combinatorics. We postpone some of the proofs, as well as a discussion of other types, to the sequel. 

   more » « less
4. HALF-SPACE MACDONALD PROCESSES

   https://doi.org/10.1017/fmp.2020.3  

   BARRAQUAND, GUILLAUME ; BORODIN, ALEXEI ; CORWIN, IVAN ( January 2020 , Forum of Mathematics, Pi)

   null (Ed.)

   Macdonald processes are measures on sequences of integer partitions built using the Cauchy summation identity for Macdonald symmetric functions. These measures are a useful tool to uncover the integrability of many probabilistic systems, including the Kardar–Parisi–Zhang (KPZ) equation and a number of other models in its universality class. In this paper, we develop the structural theory behind half-space variants of these models and the corresponding half-space Macdonald processes. These processes are built using a Littlewood summation identity instead of the Cauchy identity, and their analysis is considerably harder than their full-space counterparts. We compute moments and Laplace transforms of observables for general half-space Macdonald measures. Introducing new dynamics preserving this class of measures, we relate them to various stochastic processes, in particular the log-gamma polymer in a half-quadrant (they are also related to the stochastic six-vertex model in a half-quadrant and the half-space ASEP). For the polymer model, we provide explicit integral formulas for the Laplace transform of the partition function. Nonrigorous saddle-point asymptotics yield convergence of the directed polymer free energy to either the Tracy–Widom (associated to the Gaussian orthogonal or symplectic ensemble) or the Gaussian distribution depending on the average size of weights on the boundary. 

   more » « less
5. More on zeros and approximation of the Ising partition function

   https://doi.org/10.1017/fms.2021.40  

   Barvinok, Alexander ; Barvinok, Nicholas ( January 2021 , Forum of Mathematics, Sigma)

   Abstract We consider the problem of computing the partition function $\sum _x e^{f(x)}$ , where $f: \{-1, 1\}^n \longrightarrow {\mathbb R}$ is a quadratic or cubic polynomial on the Boolean cube $\{-1, 1\}^n$ . In the case of a quadratic polynomial f , we show that the partition function can be approximated within relative error $0 < \epsilon < 1$ in quasi-polynomial $n^{O(\ln n - \ln \epsilon )}$ time if the Lipschitz constant of the non-linear part of f with respect to the $\ell ^1$ metric on the Boolean cube does not exceed $1-\delta $ , for any $\delta>0$ , fixed in advance. For a cubic polynomial f , we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $\sum _x e^{\tilde {f}(x)} \ne 0$ for complex-valued polynomials $\tilde {f}$ in a neighborhood of a real-valued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices. 

   more » « less