Dimension in Complexity Classes
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Scaled dimension and the Kolmogorov complexity of Turing-hard sets
- Dimension extractors and optimal decompression
- Resource-bounded strong dimension versus resource-bounded category
- Fractal dimension and logarithmic loss unpredictability.
- Exact constructive and computable dimensions
- Prediction and dimension
- Effective Hausdorff dimension in general metric spaces
- Scaled dimension and nonuniform complexity
- Finite-state dimension
- The dimensions of individual strings and sequences
- Compressibility and Kolmogorov complexity
- A zero-one SUBEXP-dimension law for BPP
- Dimension is compression
- Nondeterminisic sublinear time has measure 0 in P
- Thinking with notations: epistemic actions and epistemic activities in mathematical practice
- Subcomputable Hausdorff function dimension
- Hausdorff dimension and oracle constructions
- Dimensions of Copeland-Erdös sequences
- The Kolmogorov complexity of infinite words
- Base invariance of feasible dimension
- Partial bi-immunity, scaled dimension, and NP-completeness
- Dimension, entropy rates, and compression
- A note on dimensions of polynomial size circuits
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- The Kučera-Gács theorem revisited by Levin
- 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
- Bounded pushdown dimension vs Lempel Ziv information density
- Calibrating Randomness
- Effective Dimensions and Relative Frequencies
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
- A divergence formula for randomness and dimension
- Dimension, Halfspaces, and the Density of Hard Sets
- Strict process machine complexity
- scientific article; zbMATH DE number 2038717 (Why is no real title available?)
- scientific article; zbMATH DE number 7378388 (Why is no real title available?)
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Dimension spectra of lines
- scientific article; zbMATH DE number 7215284 (Why is no real title available?)
- STACS 2004
- Dimension Characterizations of Complexity Classes
- High-confidence predictions under adversarial uncertainty
- On the degree of univariate polynomials over the integers
- Compressed matrix multiplication
- Logical Approaches to Computational Barriers
- Martingales in the Study of Randomness
- Dimension and the structure of complexity classes
- 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
- Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
- A point to set principle for finite-state dimension
- Real numbers equally compressible in every base
- Normality, relativization, and randomness
- Effective continued fraction dimension versus effective Hausdorff dimension of reals
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- On the packing dimension of unions and extensions of k-planes
- Algorithmic dimensions via learning functions
- Point-to-set principle and constructive dimension faithfulness
- Constructive dimension and Turing degrees
- Entropy rates and finite-state dimension
- Constructive dimension equals Kolmogorov complexity
- Kolmogorov-Loveland stochasticity and Kolmogorov complexity
- Complex network dimension and path counts
- Information measures for infinite sequences
- Pushdown dimension
This page was built for publication: Dimension in Complexity Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429684)
