Explicit time and space efficient encoders exist only with random access
From MaRDI portal
Cites work
- A brief history of the development of error correcting codes
- A nondeterministic space-time tradeoff for linear codes
- A note on the decoding complexity of error-correcting codes
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Constant-round interactive proofs for delegating computation
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Construction of extractors using pseudo-random generators (extended abstract)
- Cumulative memory lower bounds for randomized and quantum computation
- Delegating computation: interactive proofs for muggles
- Delegating computations with (almost) minimal time and space overhead
- Endcoding Complexity Versus Minimum Distance
- Error detecting and error correcting codes
- Expander codes
- Extracting all the randomness and reducing the error in Trevisan's extractors
- High-rate codes with sublinear-time decoding
- High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
- scientific article; zbMATH DE number 3174791 (Why is no real title available?)
- scientific article; zbMATH DE number 3550189 (Why is no real title available?)
- scientific article; zbMATH DE number 1263215 (Why is no real title available?)
- Improved non-malleable extractors, non-malleable codes and independent source extractors
- Invertible Extractors and Wiretap Protocols
- Linear-time encodable and decodable error-correcting codes
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Locally testable codes with constant rate, distance, and locality
- Loss-less condensers, unbalanced expanders, and extractors
- Non-malleable coding against bit-wise and split-state tampering
- Non-malleable extractors and codes, with their many tampered extensions
- On black-box constructions of time and space efficient sublinear arguments from symmetric-key primitives
- On the concrete efficiency of probabilistically-checkable proofs
- On the distribution of the number of roots of polynomials and explicit weak designs
- One-tape, off-line Turing machine computations
- Randomness is linear in space
- Succinct arguments from multi-prover interactive proofs and their efficiency benefits
- Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
- Time-space trade-off lower bounds for randomized computation of decision problems
- Time-space tradeoffs for algebraic problems on general sequential machines
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- Time/Space Trade-Offs for Reversible Computation
- Unbalanced expanders from multiplicity codes
This page was built for publication: Explicit time and space efficient encoders exist only with random access
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866492)
