Pseudorandom generators for space-bounded computation
From MaRDI portal
Publication:1204523
DOI10.1007/BF01305237zbMath0759.68024MaRDI QIDQ1204523
Publication date: 10 March 1993
Published in: Combinatorica (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
Universal traversal sequences with backtracking. ⋮ \(\text{RL}\subseteq \text{SC}\) ⋮ 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 ⋮ Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Counting distinct items over update streams ⋮ On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ A Statistical Analysis of Probabilistic Counting Algorithms ⋮ Fooling Polytopes ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality ⋮ Improved hardness amplification in NP ⋮ Randomness-efficient non-interactive zero knowledge ⋮ Efficient construction of a small hitting set for combinatorial rectangles in high dimension ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ (De)randomized construction of small sample spaces in \(\mathcal{NC}\) ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Quantum vs. classical algorithms for solving the heat equation ⋮ Unnamed Item ⋮ Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)). ⋮ Unnamed Item ⋮ How strong is Nisan's pseudo-random generator? ⋮ Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Massive online teaching to bounded learners ⋮ Learning mixtures of spherical gaussians ⋮ Low-weight halfspaces for sparse boolean vectors ⋮ Learnability of DNF with representation-specific queries ⋮ Can theories be tested? ⋮ Making evolution rigorous ⋮ 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 ⋮ 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 ⋮ Learning and incentives in user-generated content ⋮ 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 ⋮ Competing provers protocols for circuit evaluation ⋮ Catch them if you can ⋮ Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints ⋮ 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 ⋮ On the power of conditional samples in distribution testing ⋮ Randomness buys depth for approximate counting ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ 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 ⋮ Bounded Independence Plus Noise Fools Products ⋮ Impact of memory size on graph exploration capability ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Unnamed Item ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ Periodicity and Cyclic Shifts via Linear Sketches ⋮ Tight time-space lower bounds for finding multiple collision pairs and their applications ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ An Almost m-wise Independent Random Permutation of the Cube ⋮ 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})\) ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Graph exploration by a finite automaton ⋮ Pseudorandom Functions: Three Decades Later ⋮ Randomness in interactive proofs ⋮ On the streaming indistinguishability of a random permutation and a random function
Cites Work
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Expanders, randomness, or time versus space
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Probabilistic algorithm for testing primality
- The computational complexity of universal hashing
- Universal classes of hash functions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
This page was built for publication: Pseudorandom generators for space-bounded computation
