اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHuangs theorem and the exterior algebra
99
0
0.0
(
0
)
تأليف
Roman Karasev
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this note we give a version of Hao Huangs proof of the sensitivity conjecture, shedding some light on the origin of the magical matrix $A$ in that proof. For the history of the subject and the importance of this conjecture to the study of boolean functions, we refer to the original paper. Here we only state the main result: Consider the boolean cube $Q_n={0,1}^n$ as a graph, whose edges connect pairs of vertices differing in one coordinate. Then any its induced subgraph on greater than $2^{n-1}$ (the half) vertices has degree of some vertex at least $sqrt{n}$.
قيم البحث
اقرأ أيضاً
We analyze the structure of the algebra N of symmetric polynomials in non-commuting variables in so far as it relates to its commutative counterpart. Using the place-action of the symmetric group, we are able to realize the latter as the invariant po
lynomials inside the former. We discover a tensor product decomposition of N analogous to the classical theorems of Chevalley, Shephard-Todd on finite reflection groups.
We introduce a Hopf algebra structure of subword complexes, including both finite and infinite types. We present an explicit cancellation free formula for the antipode using acyclic orientations of certain graphs, and show that this Hopf algebra indu
ces a natural non-trivial sub-Hopf algebra on $c$-clusters in the theory of cluster algebras.
Let $Lambda$ be the set of partitions of length $geq 0$. We introduce an $mathbb{N}$-graded algebra $mathbb{A}_q^d(Lambda)$ associated to $Lambda$, which can be viewed as a quantization of the algebra of partitions defined by Reineke. The multiplicat
ion of $mathbb{A}^d_q(Lambda)$ has some kind of quasi-commutativity, and the associativity comes from combinatorial properties of certain polynomials appeared in the quantized cohomological Hall algebra $mathcal{H}^d_q$ of the $d$-loop quiver. It turns out that $mathbb{A}^d_q(Lambda)$ is isomorphic to $mathcal{H}^d_q$, thus can be viewed as a combinatorial realization for $mathcal{H}^d_q$.
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known sepa
ration (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = Omega(n)$, which is also optimal.
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $bullet quad mathrm{deg}(f) = O(widetilde{mathrm{deg}}(f)^2)$: The degree of $f$ is at most quadratic in the approximate degree of $f$. This is optim
al as witnessed by the OR function. $bullet quad mathrm{D}(f) = O(mathrm{Q}(f)^4)$: The deterministic query complexity of $f$ is at most quartic in the quantum query complexity of $f$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrm{Q}(f)=Omega(n)$, which is also optimal. We also show that the approximate degree of any read-once formula on $n$ variables is $Theta(sqrt{n})$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
