اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHeat and Noise on Cubes and Spheres: The Sensitivity of Randomly Rotated Polynomial Threshold Functions
202
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We establish a precise relationship between spherical harmonics and Fourier basis functions over a hypercube randomly embedded in the sphere. In particular, we give a bound on the expected Boolean noise sensitivity of a randomly rotated function in terms of its spherical sensitivity, which we define according to its evolution under the spherical heat equation. As an application, we prove an average case of the Gotsman-Linial conjecture, bounding the sensitivity of polynomial threshold functions subjected to a random rotation.
قيم البحث
اقرأ أيضاً
We identify the dimension of the centralizer of the symmetric group $mathfrak{S}_d$ in the partition algebra $mathcal{A}_d(delta)$ and in the Brauer algebra $mathcal{B}_d(delta)$ with the number of multidigraphs with $d$ arrows and the number of disj
oint union of directed cycles with $d$ arrows, respectively. Using Schur-Weyl duality as a fundamental theory, we conclude that each centralizer is related with the $G$-invariant space $P^d(M_n(mathbf{k}))^G$ of degree $d$ homogeneous polynomials on $n times n$ matrices, where $G$ is the orthogonal group and the group of permutation matrices, respectively. Our approach gives a uniform way to show that the dimensions of $P^d(M_n(mathbf{k}))^G$ are stable for sufficiently large $n$.
This is a survey on the exact complexity of computing the Tutte polynomial. It is the longer 2017 version of Chapter 25 of the CRC Handbook on the Tutte polynomial and related topics, edited by J. Ellis-Monaghan and I. Moffatt, which is due to appear
in the first quarter of 2020. In the version to be published in the Handbook the Sections 5 and 6 are shortened and made into a single section.
Let $f: {0,1}^n to {0, 1}$ be a boolean function, and let $f_land (x, y) = f(x land y)$ denote the AND-function of $f$, where $x land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_land$ and show that, up to a $log
n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_land$. This comes within a $log n$ factor of establishing the log-rank conjecturefor 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 $mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_land$ 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 to {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 to mathbb{R}$ with a larger range.
Regular semisimple Hessenberg varieties are subvarieties of the flag variety $mathrm{Flag}(mathbb{C}^n)$ arising naturally in the intersection of geometry, representation theory, and combinatorics. Recent results of Abe-Horiguchi-Masuda-Murai-Sato an
d Abe-DeDieu-Galetto-Harada relate the volume polynomials of regular semisimple Hessenberg varieties to the volume polynomial of the Gelfand-Zetlin polytope $mathrm{GZ}(lambda)$ for $lambda=(lambda_1,lambda_2,ldots,lambda_n)$. The main results of this manuscript use and generalize tools developed by Anderson-Tymoczko, Kiritchenko-Smirnov-Timorin, and Postnikov, in order to derive an explicit formula for the volume polynomials of regular semisimple Hessenberg varieties in terms of the volumes of certain faces of the Gelfand-Zetlin polytope, and also exhibit a manifestly positive, combinatorial formula for their coefficients with respect to the basis of monomials in the $alpha_i := lambda_i-lambda_{i+1}$. In addition, motivated by these considerations, we carefully analyze the special case of the permutohedral variety, which is also known as the toric variety associated to Weyl chambers. In this case, we obtain an explicit decomposition of the permutohedron (the moment map image of the permutohedral variety) into combinatorial $(n-1)$-cubes, and also give a geometric interpretation of this decomposition by expressing the cohomology class of the permutohedral variety in $mathrm{Flag}(mathbb{C}^n)$ as a sum of the cohomology classes of a certain set of Richardson varieties.
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3, there exists a polynomial-time algorithm based on Lo
vasz theory of polymatroid matching. Here we give a completely different, randomized polynomial-time algorithm in the case k=3. The main ingredients are a Pfaffian formula by Vaintrob and one of the authors (G.M.) for a polynomial that enumerates spanning hypertrees with some signs, and a lemma on the number of roots of polynomials over a finite field.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
