Effective Strong Dimension in Algorithmic Information and Computational Complexity
From MaRDI portal
computational complexityeffective dimensionHausdorff dimensionKolmogorov complexityMartin-Löf randomnesspacking dimension
Theory of numerations, effectively presented structures (03D45) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Fractals (28A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Recommendations
Cited in
(94)- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- Resource-bounded strong dimension versus resource-bounded category
- Finite-state dimension
- The dimensions of individual strings and sequences
- Compressibility and Kolmogorov complexity
- Dimension is compression
- Dimension spectra of lines
- KL-randomness and effective dimension under strong reducibility
- Subcomputable Hausdorff function dimension
- Base invariance of feasible dimension
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- The Kučera-Gács theorem revisited by Levin
- scientific article; zbMATH DE number 1670880 (Why is no real title available?)
- Learning hurdles for sleeping experts
- Restriction access
- Mechanism design with approximate valuations
- Quantum strategic game theory
- The curse of simultaneity
- No justified complaints: on fair sharing of multiple resources
- 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: homomorphic encryption for restricted computations
- Sherali-Adams relaxations and indistinguishability in counting logics
- Graph densification
- Spectral sparsification via random spanners
- 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
- A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
- Randomness, computation and mathematics
- Bounded pushdown dimension vs Lempel Ziv information density
- On the Polynomial Depth of Various Sets of Random Strings
- Relative Kolmogorov complexity and geometry
- Effective fractal dimensions
- Who asked us? How the theory of computing answers questions about analysis
- Effective Dimensions and Relative Frequencies
- Dimensions of Points in Self-similar Fractals
- Connectivity properties of dimension level sets
- Effective packing dimension of $\Pi ^0_1$-classes
- A divergence formula for randomness and dimension
- Dimension spectra of random subfractals of self-similar fractals
- Dimension in Complexity Classes
- scientific article; zbMATH DE number 1754653 (Why is no real title available?)
- Avoiding effective packing dimension 1 below array noncomputable c.e. degrees
- Completeness, Compactness, Effective Dimensions
- Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
- scientific article; zbMATH DE number 7378388 (Why is no real title available?)
- Results on the dimension spectra of planar lines
- Dimension spectra of lines
- scientific article; zbMATH DE number 7576618 (Why is no real title available?)
- Fractal Intersections and Products via Algorithmic Dimension
- STACS 2004
- scientific article; zbMATH DE number 5269064 (Why is no real title available?)
- A perfect set of reals with finite self-information
- Translating the Cantor set by a random real
- scientific article; zbMATH DE number 2222024 (Why is no real title available?)
- High-confidence predictions under adversarial uncertainty
- On the degree of univariate polynomials over the integers
- Compressed matrix multiplication
- Extending the reach of the point-to-set principle
- Projection theorems using effective dimension
- A divergence formula for randomness and dimension
- Dimension, halfspaces, and the density of hard sets
- Effective dimensions and relative frequencies
- Covariance parameter estimation of Gaussian processes with approximated functional inputs
- On the Hausdorff dimension of maximal chains and antichains of Turing and hyperarithmetic degrees
- Algorithmically optimal outer measures
- Real numbers equally compressible in every base
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- Algorithmic dimensions via learning functions
- Constructive dimension and Turing degrees
- Complex network dimension and path counts
- Information measures for infinite sequences
- Turing degrees of reals of positive effective packing dimension
This page was built for publication: Effective Strong Dimension in Algorithmic Information and Computational Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507516)
