Effective Strong Dimension in Algorithmic Information and Computational Complexity
From MaRDI portal
Publication:3507516
DOI10.1137/S0097539703446912zbMATH Open1144.68029DBLPjournals/siamcomp/AthreyaHLM07WikidataQ60578973 ScholiaQ60578973MaRDI QIDQ3507516FDOQ3507516
Authors: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, K. B. Athreya 
Publication date: 19 June 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
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)
Cited In (90)
- High-confidence predictions under adversarial uncertainty
- A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
- On the Polynomial Depth of Various Sets of Random Strings
- Avoiding effective packing dimension 1 below array noncomputable c.e. degrees
- Extending the reach of the point-to-set principle
- Effective Dimensions and Relative Frequencies
- Fractal Intersections and Products via Algorithmic Dimension
- Covariance parameter estimation of Gaussian processes with approximated functional inputs
- Completeness, Compactness, Effective Dimensions
- Projection theorems using effective dimension
- Who asked us? How the theory of computing answers questions about analysis
- 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
- Translating the Cantor set by a random real
- KL-randomness and effective dimension under strong reducibility
- Effective fractal dimensions
- A divergence formula for randomness and dimension
- On the degree of univariate polynomials over the integers
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- Quantum money from knots
- 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
- Results on the dimension spectra of planar lines
- Quantum strategic game theory
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- Fairness through awareness
- Resource-bounded strong dimension versus resource-bounded category
- Compressibility and Kolmogorov complexity
- Bounded pushdown dimension vs Lempel Ziv information density
- Dimension spectra of lines
- Dimension spectra of lines
- Randomness, computation and mathematics
- Spectral sparsification via random spanners
- Finite-state dimension
- The dimensions of individual strings and sequences
- On persistent homotopy, knotted complexes and the Alexander module
- 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
- STACS 2004
- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- 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
- Quantum interactive proofs with weak error bounds
- Constructive dimension and Turing degrees
- 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
- Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
- Turing degrees of reals of positive effective packing 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
- Dimensions of Points in Self-similar Fractals
- Towards deterministic tree code constructions
- A perfect set of reals with finite self-information
- Algorithms on evolving graphs
- Title not available (Why is that?)
- Connectivity properties of dimension level sets
- Title not available (Why is that?)
- Dimension is compression
- Targeted malleability: homomorphic encryption for restricted computations
- Bounds on locally testable codes with unique tests
- Base invariance of feasible dimension
- Effective dimensions and relative frequencies
- Title not available (Why is that?)
- Dimension in Complexity Classes
- Approximately optimal mechanism design via differential privacy
- Title not available (Why is that?)
- Relative Kolmogorov complexity and geometry
- On beating the hybrid argument
- Mechanism design with approximate valuations
- Title not available (Why is that?)
- Compressed matrix multiplication
- Title not available (Why is that?)
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)
