No label defined (Q5077146)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7528580

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7528580

Statements

scholarly article

0 references

0 references

Rocco A. Servedio

0 references

Theory of Computing

0 references

publication date

18 May 2022

0 references

full work available at URL

https://arxiv.org/abs/1801.03590

0 references

zbMATH Keywords

pseudorandom generators

0 references

switching lemmas

0 references

circuit complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

BQP and the polynomial hierarchy

0 references

Reducing the complexity of reductions

0 references

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Simple Constructions of Almost k-wise Independent Random Variables

0 references

Computational Complexity

0 references

Random oracles separate PSPACE from the polynomial-time hierarchy

0 references

Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs

0 references

Polylogarithmic Independence Can Fool DNF Formulas

0 references

Lower bounds for recognizing small cliques on CRCW PRAM's

0 references

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

0 references

Pseudorandom generators for low degree polynomials

0 references

Pseudorandom Bits for Polynomials

0 references

Estimation of certain exponential sums arising in complexity theory

0 references

Polylogarithmic independence fools <i>AC</i> <sup>0</sup> circuits

0 references

With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

0 references

0 references

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates

0 references

Non-malleable codes and extractors for small-depth circuits, and affine functions

0 references

0 references

Near-optimal small-depth lower bounds for small distance connectivity

0 references

Improved Pseudorandom Generators for Depth 2 Circuits

0 references

Non-Malleable Codes

0 references

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

On derandomizing algorithms that err extremely rarely

0 references

DNF sparsification and a faster deterministic counting algorithm

0 references

On polynomial approximations to AC

0 references

On the Correlation of Parity and Small-Depth Circuits

0 references

On Small-depth Frege Proofs for Tseitin for Grids

0 references

On the power of small-depth threshold circuits

0 references

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

0 references

Pseudorandomness from Shrinkage

0 references

0 references

An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

0 references

Constant depth circuits, Fourier transform, and learnability

0 references

Approximate inclusion-exclusion

0 references

0 references

Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates

0 references

On deterministic approximation of DNF

0 references

Pseudorandom generators for width-3 branching programs

0 references

Small-Bias Probability Spaces: Efficient Constructions and Applications

0 references

Pseudorandom bits for constant depth circuits

0 references

Hardness vs randomness

0 references

Exponential lower bounds for the pigeonhole principle

0 references

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

0 references

A Simple Proof of Bazzi’s Theorem

0 references

Pseudorandomness for Regular Branching Programs via Fourier Analysis

0 references

0 references

The average sensitivity of bounded-depth formulas

0 references

What Circuit Classes Can Be Learned with Non-Trivial Savings?

0 references

0 references

0 references

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates

0 references

On the Power of Small-Depth Computation

0 references

The sum of \(D\) small-bias generators fools polynomials of degree \(D\)

0 references

0 references

Identifiers

10.4086/toc.2022.v018a004

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5077146

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5077146&oldid=36805019"