Dimension in Complexity Classes
From MaRDI portal
Publication:4429684
DOI10.1137/S0097539701417723zbMath1026.68059WikidataQ30049129 ScholiaQ30049129MaRDI QIDQ4429684
Publication date: 28 September 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
computational complexitymartingalesHausdorff dimensioncomplexity classesresource-bounded dimensiongalescircuit-size complexity
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hausdorff and packing measures (28A78)
Related Items
Scaled dimension and nonuniform complexity, Hausdorff dimension and oracle constructions, Finite-state dimension, Constructive dimension equals Kolmogorov complexity, The dimensions of individual strings and sequences, Mutual dimension and random sequences, Dimensions of Copeland-Erdös sequences, The Kolmogorov complexity of infinite words, Dimension spectra of lines1, Automatic Kolmogorov complexity, normality, and finite-state dimension revisited, A divergence formula for randomness and dimension, Strict process machine complexity, Compressibility and Kolmogorov complexity, Martingales in the Study of Randomness, Dimension and the structure of complexity classes, The Kučera-Gács theorem revisited by Levin, Projection theorems using effective dimension, Effective Dimensions and Relative Frequencies, Fractal dimension and logarithmic loss unpredictability., Exact constructive and computable dimensions, A zero-one SUBEXP-dimension law for BPP, Unnamed Item, Dimension is compression, Bounded Pushdown Dimension vs Lempel Ziv Information Density, ALGORITHMS FOR FRACTAL DIMENSION CALCULATION, Dimension, halfspaces, and the density of hard sets, Base invariance of feasible dimension, Bounding the dimension of points on a line, Effective dimensions and relative frequencies, Finite-state dimension and real arithmetic, Subcomputable Hausdorff function dimension, Nondeterminisic sublinear time has measure 0 in P, A Divergence Formula for Randomness and Dimension, Partial bi-immunity, scaled dimension, and NP-completeness, On the degree of univariate polynomials over the integers, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, Complex network dimension and path counts, Information measures for infinite sequences, Dimension, entropy rates, and compression, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Prediction and dimension, A note on dimensions of polynomial size circuits, Effective Hausdorff dimension in general metric spaces, Pushdown dimension, High-confidence predictions under adversarial uncertainty, Quantum rejection sampling, Compressed matrix multiplication, Constructive dimension and Turing degrees, Unnamed Item, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Dimension extractors and optimal decompression, Learning hurdles for sleeping experts, Restriction access, Mechanism design with approximate valuations, Quantum strategic game theory, The curse of simultaneity, No justified complaints, 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, Sherali-Adams relaxations and indistinguishability in counting logics, Graph densification, Spectral sparsification via random spanners, Multicommodity flows and cuts in polymatroidal networks, 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, Calibrating Randomness, Resource-bounded strong dimension versus resource-bounded category, Thinking with notations: epistemic actions and epistemic activities in mathematical practice, Algorithmic Fractal Dimensions in Geometric Measure Theory, Entropy rates and finite-state dimension
