Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHuangs theorem and the exterior algebra
99
0
0.0
(
0
)
Authors
Roman Karasev
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
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 polynomials 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 induces 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 multiplication 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 separation (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 optimal 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})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
