Complexity and Avoidance
- URL: http://arxiv.org/abs/2204.11289v1
- Date: Sun, 24 Apr 2022 14:36:38 GMT
- Title: Complexity and Avoidance
- Authors: Hayden Jananthan
- Abstract summary: We show that for suitable $f$ and $p$, there are $q$ and $g$ such that $mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$, as well as the growth rates of $q$ and $g$.
Concerning shift complexity, explicit bounds are given on how slow-growing $q$ must be for any member of $rmLUA(q)$ to compute $delta$-shift complex sequences.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this dissertation we examine the relationships between the several
hierarchies, including the complexity, $\mathrm{LUA}$ (Linearly Universal
Avoidance), and shift complexity hierarchies, with an eye towards quantitative
bounds on growth rates therein. We show that for suitable $f$ and $p$, there
are $q$ and $g$ such that $\mathrm{LUA}(q) \leq_\mathrm{s} \mathrm{COMPLEX}(f)$
and $\mathrm{COMPLEX}(g) \leq_\mathrm{s} \mathrm{LUA}(p)$, as well as quantify
the growth rates of $q$ and $g$. In the opposite direction, we show that for
certain sub-identical $f$ satisfying $\lim_{n \to \infty}{f(n)/n}=1$ there is a
$q$ such that $\mathrm{COMPLEX}(f) \leq_\mathrm{w} \mathrm{LUA}(q)$, and for
certain fast-growing $p$ there is a $g$ such that $\mathrm{LUA}(p)
\leq_\mathrm{s} \mathrm{COMPLEX}(g)$, as well as quantify the growth rates of
$q$ and $g$.
Concerning shift complexity, explicit bounds are given on how slow-growing
$q$ must be for any member of $\rm{LUA}(q)$ to compute $\delta$-shift complex
sequences. Motivated by the complexity hierarchy, we generalize the notion of
shift complexity to consider sequences $X$ satisfying $\operatorname{KP}(\tau)
\geq f(|\tau|) - O(1)$ for all substrings $\tau$ of $X$ where $f$ is any order
function. We show that for sufficiently slow-growing $f$, $f$-shift complex
sequences can be uniformly computed by $g$-complex sequences, where $g$ grows
slightly faster than $f$.
The structure of the $\mathrm{LUA}$ hierarchy is examined using bushy tree
forcing, with the main result being that for any order function $p$, there is a
slow-growing order function $q$ such that $\mathrm{LUA}(p)$ and
$\mathrm{LUA}(q)$ are weakly incomparable. Using this, we prove new results
about the filter of the weak degrees of deep nonempty $\Pi^0_1$ classes and the
connection between the shift complexity and $\mathrm{LUA}$ hierarchies.
Related papers
- $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model.
For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits.
For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
arXiv Detail & Related papers (2023-07-11T08:51:53Z) - Matching upper bounds on symmetric predicates in quantum communication
complexity [0.0]
We focus on the quantum communication complexity of functions of the form $f circ G = f(G)mathrmQCC_mathrmE(G)) when the parties are allowed to use shared entanglement.
We show that the same statement holds emphwithout shared entanglement, which generalizes their result.
arXiv Detail & Related papers (2023-01-01T08:30:35Z) - Randomised Composition and Small-Bias Minimax [0.9252523881586053]
We prove two results about query complexity $mathrmR(f)$.
First, we introduce a "linearised" complexity measure $mathrmLR$ and show that it satisfies an inner-conflict composition theorem: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$ and $g$, and moreover, $mathrmLR$ is the largest possible measure with this property.
arXiv Detail & Related papers (2022-08-26T23:32:19Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm.
Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$.
We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
arXiv Detail & Related papers (2021-05-17T16:40:48Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph.
We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
arXiv Detail & Related papers (2021-03-17T00:59:33Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model.
Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
arXiv Detail & Related papers (2020-02-09T03:39:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.