Dimension in Complexity Classes
From MaRDI portal
Publication:4429684
Recommendations
Cited in
(93)- Dimension Characterizations of Complexity Classes
- Compressed matrix multiplication
- Linear programming, width-1 CSPs, and robust satisfaction
- Gadgets and anti-gadgets leading to a complexity dichotomy
- The curse of simultaneity
- scientific article; zbMATH DE number 2038717 (Why is no real title available?)
- Strict process machine complexity
- Thinking with notations: epistemic actions and epistemic activities in mathematical practice
- High-confidence predictions under adversarial uncertainty
- A divergence formula for randomness and dimension
- Kolmogorov-Loveland stochasticity and Kolmogorov complexity
- 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
- Entropy rates and finite-state dimension
- Constructive dimension equals Kolmogorov complexity
- (Leveled) fully homomorphic encryption without bootstrapping
- Subcomputable Hausdorff function dimension
- Quantum strategic game theory
- A note on dimensions of polynomial size circuits
- Extracting Kolmogorov complexity with applications to dimension zero-one laws
- Fractal dimension and logarithmic loss unpredictability.
- Dimension and the structure of complexity classes
- Martingales in the Study of Randomness
- Resource-bounded strong dimension versus resource-bounded category
- Pushdown dimension
- Fairness through awareness
- Compressibility and Kolmogorov complexity
- 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
- Effective Dimensions and Relative Frequencies
- Dimension extractors and optimal decompression
- 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
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Crowdsourced Bayesian auctions
- A divergence formula for randomness and dimension
- Scaled dimension and nonuniform complexity
- 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
- ALGORITHMS FOR FRACTAL DIMENSION CALCULATION
- 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
- The Kolmogorov complexity of infinite words
- Calibrating Randomness
- 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
- 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
- Algorithms on evolving graphs
- scientific article; zbMATH DE number 7215284 (Why is no real title available?)
- scientific article; zbMATH DE number 7378388 (Why is no real title available?)
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- A zero-one SUBEXP-dimension law for BPP
- Dimension is compression
- 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
- Effective dimensions and relative frequencies
- Dimension, entropy rates, and compression
- Dimension, Halfspaces, and the Density of Hard Sets
- Exact constructive and computable dimensions
- Approximately optimal mechanism design via differential privacy
- Logical Approaches to Computational Barriers
- On beating the hybrid argument
- Projection theorems using effective dimension
- Dimensions of Copeland-Erdös sequences
- Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
- Prediction and dimension
- Mechanism design with approximate valuations
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)
