An official website of the United States government
Let f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the AND-function of f, where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F2-degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f∧ is polynomially related to the AND-decision tree complexity of f. The results rely on a new structural result regarding boolean functions f: {0, 1}n → {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f: {0, 1}n → with a larger range.
more »
« less
Interpolation Polynomials, Bar Monomials, and Their Positivity
Abstract We prove a conjecture of Knop–Sahi on the positivity of interpolation polynomials, which is an inhomogeneous generalization of Macdonald’s conjecture for Jack polynomials. We also formulate and prove the nonsymmetric version of this conjecture, and in fact, we deduce everything from an even stronger positivity result. This last result concerns certain inhomogeneous analogues of ordinary monomials that we call bar monomials. Their positivity involves in an essential way a new partial order on compositions that we call the bar order, and a new operation that we call a glissade.
more »
« less
- PAR ID:
- 10339418
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let $$k \leq n$$ be positive integers, and let $$X_n = (x_1, \dots , x_n)$$ be a list of $$n$$ variables. The Boolean product polynomial$$B_{n,k}(X_n)$$ is the product of the linear forms $$\sum _{i \in S} x_i$$, where $$S$$ ranges over all $$k$$-element subsets of $$\{1, 2, \dots , n\}$$. We prove that Boolean product polynomials are Schur positive. We do this via a new method of proving Schur positivity using vector bundles and a symmetric function operation we call Chern plethysm. This gives a geometric method for producing a vast array of Schur positive polynomials whose Schur positivity lacks (at present) a combinatorial or representation theoretic proof. We relate the polynomials $$B_{n,k}(X_n)$$ for certain $$k$$ to other combinatorial objects including derangements, positroids, alternating sign matrices, and reverse flagged fillings of a partition shape. We also relate $$B_{n,n-1}(X_n)$$ to a bigraded action of the symmetric group $${\mathfrak{S}}_n$$ on a divergence free quotient of superspace.more » « less
-
We prove that the K-k-Schur functions are part of a family of inhomogenous symmetric functions whose top homogeneous components are Catalan functions, the Euler characteristics of certain vector bundles on the flag variety. Lam-Schilling-Shimozono identified the K-k-Schur functions as Schubert representatives for K-homology of the affine Grassmannian for SL_{k+1}. Our perspective reveals that the K-k-Schur functions satisfy a shift invariance property, and we deduce positivity of their branching coefficients from a positivity result of Baldwin and Kumar. We further show that a slight adjustment of our formulation for K-k-Schur functions produces a second shift-invariant basis which conjecturally has both positive branching and a rectangle factorization property. Building on work of Ikeda-Iwao-Maeno, we conjecture that this second basis gives the images of the Lenart-Maeno quantum Grothendieck polynomials under a K-theoretic analog of the Peterson isomorphism.more » « less
-
Ta-Shma, Amnon (Ed.)We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric.more » « less
-
We define a combinatorial model for $$F$$-polynomials and $$g$$-vectors for type $$D_n$$ cluster algebras where the associated quiver is acyclic. Our model utilizes a combination of dimer configurations and double dimer configurations which we refer to as mixed dimer configurations. In particular, we give a graph theoretic recipe that describes which monomials appear in such $$F$$-polynomials, as well as a graph theoretic way to determine the coefficients of each of these monomials. In addition, we prove that a weighting on our mixed dimer configuration model yields the associated $$g$$-vector. To prove this formula, we use a combinatorial formula due to Thao Tran (arXiv:0911.4462, 2009) and provide explicit bijections between her combinatorial model and our own.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnac049
