Pseudorandom generators for space-bounded computation
From MaRDI portal
Recommendations
Cites work
- Expanders, randomness, or time versus space
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Probabilistic algorithm for testing primality
- The computational complexity of universal hashing
- Universal classes of hash functions
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
Cited in
(only showing first 100 items - show all)- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Synthesizers and their application to the parallel construction of pseudo-random functions
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- Randomness in interactive proofs
- \(\text{RL}\subseteq \text{SC}\)
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
- Universal traversal sequences with backtracking.
- Randomness is linear in space
- How strong is Nisan's pseudo-random generator?
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Tight time-space lower bounds for finding multiple collision pairs and their applications
- On the streaming indistinguishability of a random permutation and a random function
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- Counting distinct items over update streams
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Pseudorandom generators from regular one-way functions: new constructions with improved parameters
- Graph exploration by a finite automaton
- Quantum vs. classical algorithms for solving the heat equation
- Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- scientific article; zbMATH DE number 1689047 (Why is no real title available?)
- On recycling the randomness of states in space bounded computation
- A new pseudorandom generator from collision-resistant hash functions
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- A statistical analysis of probabilistic counting algorithms
- Almost Optimal Pseudorandom Generators for Spherical Caps
- On probabilistic space-bounded machines with multiple access to random tape
- Single pass spectral sparsification in dynamic streams
- Space pseudorandom generators by communication complexity lower bounds
- Massive online teaching to bounded learners
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Low-weight halfspaces for sparse boolean vectors
- Learnability of DNF with representation-specific queries
- Can theories be tested?
- Making evolution rigorous: the error threshold
- On the convergence of the Hegselmann-Krause system
- Is privacy compatible with truthfulness?
- Differentially private data analysis of social networks via restricted sensitivity
- Characterizing the sample complexity of private learners
- Barriers in cryptography with weak, correlated and leaky sources
- On the possibilities and limitations of pseudodeterministic algorithms
- Evasiveness through a circuit lens (extended abstract)
- The garden-hose model
- Space-bounded communication complexity
- Towards an optimal query efficient PCP?
- A characterization of approximation resistance for even k-partite CSPs
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of many one-bit provers
- Approaching utopia, strong truthfulness and externality-resistant mechanisms
- Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
- Welfare maximization and the supermodular degree
- Reachability in graph timelines
- Runtime guarantees for regression problems
- An energy complexity model for algorithms
- Streaming computations with a loquacious prover
- Adversary lower bound for the k-sum problem
- Stronger methods of making quantum interactive proofs perfectly complete
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- An equational approach to secure multi-party computation
- Publicly verifiable proofs of sequential work
- On the power of nonuniformity in proofs of security
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
- Resource-based corruptions and the combinatorics of hidden diversity
- Time hierarchies for sampling distributions
- Properties and applications of Boolean function composition
- Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
- Competing provers protocols for circuit evaluation
- Catch them if you can
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- Robust optimization in the presence of uncertainty
- Sorting noisy data with partial information
- New affine-invariant codes from lifting
- H-wise independence
- Sparse extractor families for all the entropy
- Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- Periodicity and cyclic shifts via linear sketches
- Bravely, moderately: a common theme in four recent works
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- scientific article; zbMATH DE number 3876586 (Why is no real title available?)
- On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
- Sublinear estimation of weighted matchings in dynamic data streams
- Pseudorandom Bit Generators That Fool Modular Sums
- Pseudorandom generators for combinatorial checkerboards
- scientific article; zbMATH DE number 1301964 (Why is no real title available?)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Pseudorandomness via the discrete Fourier transform
- Randomness-efficient non-interactive zero knowledge
- Bounded independence plus noise fools products
- Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
- An Almost m-wise Independent Random Permutation of the Cube
- Randomness buys depth for approximate counting
- Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
- Pseudorandom generators for low sensitivity functions
- Constant-round interactive proofs for delegating computation
This page was built for publication: Pseudorandom generators for space-bounded computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1204523)
