scientific article; zbMATH DE number 7528580
From MaRDI portal
Publication:5077146
DOI10.4086/toc.2022.v018a004OpenAlexW4225724611MaRDI QIDQ5077146
Li-Yang Tan, Rocco A. Servedio
Publication date: 18 May 2022
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1801.03590
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Qxx)
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
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Approximate inclusion-exclusion
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Hardness vs randomness
- The average sensitivity of bounded-depth formulas
- On deterministic approximation of DNF
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- 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
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Simple Constructions of Almost k-wise Independent Random Variables
- Non-Malleable Codes
- On polynomial approximations to AC
- What Circuit Classes Can Be Learned with Non-Trivial Savings?
- An Average-Case Depth Hierarchy Theorem for Boolean Circuits
- 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
- On Small-depth Frege Proofs for Tseitin for Grids
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- On the Correlation of Parity and Small-Depth Circuits
- Pseudorandom generators for width-3 branching programs
- Pseudorandomness from Shrinkage
- On derandomizing algorithms that err extremely rarely
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Computational Complexity
- 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
- Reducing the complexity of reductions
This page was built for publication:
