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
Towards Optimal Moment Estimation in Streaming and Distributed Models, Unnamed Item, Unnamed Item, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Towards Optimal Moment Estimation in Streaming and Distributed Models, Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel, Paradigms for Unconditional Pseudorandom Generators, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Simple Optimal Hitting Sets for Small-Success RL, Unnamed Item, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, McCulloch-Pitts Brains and Pseudorandom Functions, Improved Explicit Hitting-Sets for ROABPs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Near-optimal pseudorandom generators for constant-depth read-once formulas, Fourier bounds and pseudorandom generators for product tests, Typically-correct derandomization for small time and space, Derandomizing Isolation in Space-Bounded Settings, Unnamed Item, Optimal $\varepsilon$-Biased Sets with Just a Little Randomness, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Perfect $L_p$ Sampling in a Data Stream, A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3, 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
