English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and$S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix.For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$,which we view as the heat measured by $v$ after an initial heat configuration$u$ is let to diffuse for $t$ time steps according to $S$. Since $S$ is entropyimproving, one may intuit that $m_t$ should not change too rapidly over time.We give the following formalizations of this intuition.  We prove that $m_{t+2} \ge m_t^{1+2/t}\!,$ an inequality studied earlier byBlakley and Dixon (also Erd\H{o}s and Simonovits) for $u=v$ and shown trueunder the restriction $m_t\ge e^{-4t}$. Moreover we prove that for any$\epsilon>0$, a stronger inequality $m_{t+2} \ge t^{1-\epsilon}\cdot\smash{m_t^{1+2/t}}$ holds unless $m_{t+2}m_{t-2}\ge \delta m_t^2$ for some$\delta$ that depends on $\epsilon$ only. Phrased differently, $\forall\epsilon> 0, \exists \delta> 0$ such that $\forall S,u,v$ \begin{equation*}\frac{m_{t+2}}{m_{t}^{1+2/t}}\ge \min\left\{t^{1-\epsilon},\delta\frac{m_t^{1-2/t}}{m_{t-2}}\right\}, \quad \forall t \ge 2,\end{equation*} which can be viewed as a truncated log-convexity statement.  Using this inequality, we answer two related open questions in complexitytheory: Any property tester for $k$-linearity requires $\Omega(k\log k)$queries and the randomized communication complexity of the $k$-Hamming distanceproblem is $\Omega(k\log k)$. Further we show that any randomized paritydecision tree computing $k$-Hamming weight has size $\exp\left(\Omega(k\logk)\right)$.

Near log-convexity of measured heat in (discrete) time and consequences