Pseudorandom generators for combinatorial checkerboards
From MaRDI portal
Publication:395607
DOI10.1007/s00037-012-0036-6zbMath1290.68042OpenAlexW2137006591MaRDI QIDQ395607
Publication date: 29 January 2014
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-012-0036-6
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Bounded Independence Plus Noise Fools Products, Fourier bounds and pseudorandom generators for product tests, A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields]
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Pseudorandom bits for constant depth circuits
- Reducing the seed length in the Nisan-Wigderson generator
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Expanders obtained from affine transformations
- Explicit construction of linear sized tolerant networks
- Ramanujan graphs
- Explicit constructions of linear-sized superconcentrators
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Pseudorandom generators for space-bounded computation
- On read-once vs. multiple access to randomness in logspace
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- \(\text{RL}\subseteq \text{SC}\)
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Hardness vs randomness
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Improved pseudorandom generators for combinatorial rectangles
- Randomness is linear in space
- On deterministic approximation of DNF
- Time-space tradeoff in derandomizing probabilistic logspace
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Pseudorandom Generators for Polynomial Threshold Functions
- An invariance principle for polytopes
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- A Simple Proof of Bazzi’s Theorem
- Pseudorandom Bits for Polynomials
- In a World of P=BPP
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple extractors for all min-entropies and a new pseudorandom generator
- Polylogarithmic independence fools AC 0 circuits
- Pseudorandom generators for low degree polynomials
- Improved Pseudorandom Generators for Depth 2 Circuits
- Undirected connectivity in log-space
- Pseudorandom Bit Generators That Fool Modular Sums
- Small-Bias Spaces for Group Products
- Polylogarithmic Independence Can Fool DNF Formulas
- Better expanders and superconcentrators
- Simple Constructions of Almost k-wise Independent Random Variables
- Tiny families of functions with random properties: A quality-size trade-off for hashing
- Efficient approximation of product distributions
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
- Bounded Independence Fools Halfspaces
- Pseudorandom generators for combinatorial shapes
- Pseudorandom generators for group products
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Linear Advice for Randomized Logarithmic Space
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- On ε‐biased generators in NC0
- Pseudorandomness for Read-Once Formulas
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Pseudorandom generators without the XOR lemma
