scientific article; zbMATH DE number 7650112
From MaRDI portal
Publication:5875501
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.45MaRDI QIDQ5875501
Li-Yang Tan, Rocco A. Servedio
Publication date: 3 February 2023
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (6)
Quantified Derandomization: How to Find Water in the Ocean ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Unnamed Item ⋮ 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
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Estimation of certain exponential sums arising in complexity theory
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- On the power of small-depth threshold circuits
- Exponential lower bounds for the pigeonhole principle
- Pseudorandom bits for constant depth circuits
- Lower bounds for recognizing small cliques on CRCW PRAM's
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Approximate inclusion-exclusion
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Hardness vs randomness
- On deterministic approximation of DNF
- On beating the hybrid argument
- BQP and the polynomial hierarchy
- A Simple Proof of Bazzi’s Theorem
- Pseudorandom Bits for Polynomials
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Constant depth circuits, Fourier transform, and learnability
- Parity, circuits, and the polynomial-time hierarchy
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- On the Power of Small-Depth Computation
- Polylogarithmic independence fools AC 0 circuits
- Pseudorandom generators for low degree polynomials
- Improved Pseudorandom Generators for Depth 2 Circuits
- Polylogarithmic Independence Can Fool DNF Formulas
- Simple Constructions of Almost k-wise Independent Random Variables
- Non-Malleable Codes
- What Circuit Classes Can Be Learned with Non-Trivial Savings?
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Non-malleable codes and extractors for small-depth circuits, and affine functions
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- On the Correlation of Parity and Small-Depth Circuits
- Pseudorandomness from Shrinkage
- On derandomizing algorithms that err extremely rarely
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Near-optimal small-depth lower bounds for small distance connectivity
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3
- Reducing the complexity of reductions
This page was built for publication:
