Effective Strong Dimension in Algorithmic Information and Computational Complexity
From MaRDI portal
Publication:3507516
DOI10.1137/S0097539703446912zbMath1144.68029WikidataQ60578973 ScholiaQ60578973MaRDI QIDQ3507516
Elvira Mayordomo, John M. Hitchcock, Jack H. Lutz, Krishna B. Athreya
Publication date: 19 June 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
computational complexityHausdorff dimensionKolmogorov complexitypacking dimensioneffective dimensionMartin-Löf randomness
Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Fractals (28A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of numerations, effectively presented structures (03D45)
Related Items (81)
A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one ⋮ Randomness, Computation and Mathematics ⋮ Dimension spectra of lines1 ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES ⋮ A divergence formula for randomness and dimension ⋮ Dimension spectra of random subfractals of self-similar fractals ⋮ Extending the reach of the point-to-set principle ⋮ Compressibility and Kolmogorov complexity ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Projection theorems using effective dimension ⋮ Effective Dimensions and Relative Frequencies ⋮ Dimensions of Points in Self-similar Fractals ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dimension is compression ⋮ Bounded Pushdown Dimension vs Lempel Ziv Information Density ⋮ Connectivity properties of dimension level sets ⋮ Dimension, halfspaces, and the density of hard sets ⋮ Base invariance of feasible dimension ⋮ Fractal Intersections and Products via Algorithmic Dimension ⋮ Effective packing dimension of $\Pi ^0_1$-classes ⋮ Effective dimensions and relative frequencies ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Finite-state dimension and real arithmetic ⋮ Subcomputable Hausdorff function dimension ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ A Divergence Formula for Randomness and Dimension ⋮ On the degree of univariate polynomials over the integers ⋮ Translating the Cantor set by a random real ⋮ Completeness, Compactness, Effective Dimensions ⋮ Dimension spectra of lines ⋮ Complex network dimension and path counts ⋮ Information measures for infinite sequences ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Unnamed Item ⋮ High-confidence predictions under adversarial uncertainty ⋮ Quantum rejection sampling ⋮ Compressed matrix multiplication ⋮ Constructive dimension and Turing degrees ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Learning hurdles for sleeping experts ⋮ Restriction access ⋮ Mechanism design with approximate valuations ⋮ Quantum strategic game theory ⋮ The curse of simultaneity ⋮ No justified complaints ⋮ From randomizing polynomials to parallel algorithms ⋮ Practical verified computation with streaming interactive proofs ⋮ Paging for multi-core shared caches ⋮ Noise vs computational intractability in dynamics ⋮ Distribution free evolvability of polynomial functions over all convex loss functions ⋮ Algorithms on evolving graphs ⋮ Towards deterministic tree code constructions ⋮ Linear time decoding of regular expander codes ⋮ List decoding subspace codes from insertions and deletions ⋮ Bounds on locally testable codes with unique tests ⋮ Approximately optimal mechanism design via differential privacy ⋮ Fairness through awareness ⋮ Dynamics of prisoner's dilemma and the evolution of cooperation on networks ⋮ Crowdsourced Bayesian auctions ⋮ Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure ⋮ Quantum interactive proofs with weak error bounds ⋮ Quantum money from knots ⋮ (Leveled) fully homomorphic encryption without bootstrapping ⋮ From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again ⋮ Targeted malleability ⋮ Sherali-Adams relaxations and indistinguishability in counting logics ⋮ Graph densification ⋮ Spectral sparsification via random spanners ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ On persistent homotopy, knotted complexes and the Alexander module ⋮ Gadgets and anti-gadgets leading to a complexity dichotomy ⋮ On beating the hybrid argument ⋮ Linear programming, width-1 CSPs, and robust satisfaction ⋮ Marginal hitting sets imply super-polynomial lower bounds for permanent ⋮ Mutual Dimension ⋮ Relative Kolmogorov complexity and geometry ⋮ Resource-bounded strong dimension versus resource-bounded category ⋮ KL-randomness and effective dimension under strong reducibility
This page was built for publication: Effective Strong Dimension in Algorithmic Information and Computational Complexity
