Effective Strong Dimension in Algorithmic Information and Computational Complexity
From MaRDI portal
Publication:3507516
computational complexityeffective dimensionHausdorff dimensionpacking dimensionKolmogorov complexityMartin-Löf randomness
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) Theory of numerations, effectively presented structures (03D45)
Recommendations
Cited in
(90)- scientific article; zbMATH DE number 1670880 (Why is no real title available?)
- scientific article; zbMATH DE number 5269064 (Why is no real title available?)
- Compressed matrix multiplication
- Linear programming, width-1 CSPs, and robust satisfaction
- Gadgets and anti-gadgets leading to a complexity dichotomy
- The curse of simultaneity
- Dimension spectra of random subfractals of self-similar fractals
- KL-randomness and effective dimension under strong reducibility
- Effective fractal dimensions
- High-confidence predictions under adversarial uncertainty
- Translating the Cantor set by a random real
- A divergence formula for randomness and dimension
- A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- Quantum money from knots
- On the degree of univariate polynomials over the integers
- Dimension, halfspaces, and the density of hard sets
- Complex network dimension and path counts
- Information measures for infinite sequences
- (Leveled) fully homomorphic encryption without bootstrapping
- Subcomputable Hausdorff function dimension
- Quantum strategic game theory
- Results on the dimension spectra of planar lines
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- On the Polynomial Depth of Various Sets of Random Strings
- Resource-bounded strong dimension versus resource-bounded category
- Fairness through awareness
- Compressibility and Kolmogorov complexity
- Dimension spectra of lines
- Avoiding effective packing dimension 1 below array noncomputable c.e. degrees
- Bounded pushdown dimension vs Lempel Ziv information density
- Dimension spectra of lines
- Randomness, computation and mathematics
- Spectral sparsification via random spanners
- Extending the reach of the point-to-set principle
- Finite-state dimension
- The dimensions of individual strings and sequences
- On persistent homotopy, knotted complexes and the Alexander module
- Effective Dimensions and Relative Frequencies
- Marginal hitting sets imply super-polynomial lower bounds for permanent
- Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
- The Kučera-Gács theorem revisited by Levin
- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- STACS 2004
- Crowdsourced Bayesian auctions
- A divergence formula for randomness and dimension
- From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
- Practical verified computation with streaming interactive proofs
- Constructive dimension and Turing degrees
- Quantum interactive proofs with weak error bounds
- Distribution free evolvability of polynomial functions over all convex loss functions
- No justified complaints: on fair sharing of multiple resources
- Effective packing dimension of $\Pi ^0_1$-classes
- Paging for multi-core shared caches
- Sherali-Adams relaxations and indistinguishability in counting logics
- Fractal Intersections and Products via Algorithmic Dimension
- Turing degrees of reals of positive effective packing dimension
- Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
- List decoding subspace codes from insertions and deletions
- Dynamics of prisoner's dilemma and the evolution of cooperation on networks
- Restriction access
- Mutual dimension
- From randomizing polynomials to parallel algorithms
- Graph densification
- Learning hurdles for sleeping experts
- Linear time decoding of regular expander codes
- Noise vs computational intractability in dynamics
- Towards deterministic tree code constructions
- Dimensions of Points in Self-similar Fractals
- Algorithms on evolving graphs
- A perfect set of reals with finite self-information
- Connectivity properties of dimension level sets
- scientific article; zbMATH DE number 7576618 (Why is no real title available?)
- scientific article; zbMATH DE number 7378388 (Why is no real title available?)
- Dimension is compression
- Targeted malleability: homomorphic encryption for restricted computations
- Covariance parameter estimation of Gaussian processes with approximated functional inputs
- Bounds on locally testable codes with unique tests
- Base invariance of feasible dimension
- Effective dimensions and relative frequencies
- scientific article; zbMATH DE number 1754653 (Why is no real title available?)
- Dimension in Complexity Classes
- Approximately optimal mechanism design via differential privacy
- Relative Kolmogorov complexity and geometry
- Completeness, Compactness, Effective Dimensions
- scientific article; zbMATH DE number 2222024 (Why is no real title available?)
- Who asked us? How the theory of computing answers questions about analysis
- On beating the hybrid argument
- Projection theorems using effective dimension
- Mechanism design with approximate valuations
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)
