Dimension in Complexity Classes
From MaRDI portal
Publication:4429684
DOI10.1137/S0097539701417723zbMATH Open1026.68059WikidataQ30049129 ScholiaQ30049129MaRDI QIDQ4429684FDOQ4429684
Authors: Jack H. Lutz 
Publication date: 28 September 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
computational complexitymartingalescomplexity classesHausdorff dimensionresource-bounded dimensiongalescircuit-size complexity
Hausdorff and packing measures (28A78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (93)
- Linear programming, width-1 CSPs, and robust satisfaction
- Gadgets and anti-gadgets leading to a complexity dichotomy
- The curse of simultaneity
- Title not available (Why is that?)
- Strict process machine complexity
- A divergence formula for randomness and dimension
- Kolmogorov-Loveland stochasticity and Kolmogorov complexity
- 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
- Entropy rates and finite-state dimension
- Constructive dimension equals Kolmogorov complexity
- Subcomputable Hausdorff function dimension
- Quantum strategic game theory
- Dimension and the structure of complexity classes
- A note on dimensions of polynomial size circuits
- Fractal dimension and logarithmic loss unpredictability.
- 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
- Pushdown dimension
- Bounded pushdown dimension vs Lempel Ziv information density
- Dimension spectra of lines
- Spectral sparsification via random spanners
- Finite-state dimension
- The dimensions of individual strings and sequences
- On persistent homotopy, knotted complexes and the Alexander module
- STACS 2004
- Dimension extractors and optimal decompression
- 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
- Scaled dimension and nonuniform complexity
- 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
- Partial bi-immunity, scaled dimension, and NP-completeness
- Calibrating Randomness
- The Kolmogorov complexity of infinite words
- Paging for multi-core shared caches
- Sherali-Adams relaxations and indistinguishability in counting logics
- Effective Hausdorff dimension in general metric spaces
- List decoding subspace codes from insertions and deletions
- Dynamics of prisoner's dilemma and the evolution of cooperation on networks
- Restriction access
- Towards deterministic tree code constructions
- Algorithms on evolving graphs
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- Nondeterminisic sublinear time has measure 0 in P
- Targeted malleability: homomorphic encryption for restricted computations
- Hausdorff dimension and oracle constructions
- Bounds on locally testable codes with unique tests
- Base invariance of feasible dimension
- Dimension, Halfspaces, and the Density of Hard Sets
- Dimension, entropy rates, and compression
- Effective dimensions and relative frequencies
- Exact constructive and computable dimensions
- Approximately optimal mechanism design via differential privacy
- Logical Approaches to Computational Barriers
- Dimensions of Copeland-Erdös sequences
- Dimension Characterizations of Complexity Classes
- Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
- Prediction and dimension
- High-confidence predictions under adversarial uncertainty
- Thinking with notations: epistemic actions and epistemic activities in mathematical practice
- Martingales in the Study of Randomness
- 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
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- A zero-one SUBEXP-dimension law for BPP
- Dimension is compression
- Projection theorems using effective dimension
- On beating the hybrid argument
- Mechanism design with approximate valuations
- Compressed matrix multiplication
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)
