scientific article; zbMATH DE number 7378658
From MaRDI portal
Publication:5009542
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.46MaRDI QIDQ5009542
Valentine Kabanets, Zhenjian Lu
Publication date: 4 August 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
derandomizationpseudorandom generatorsSATconstant-depth circuitspolynomial threshold functionsquantified derandomizationcircuit analysis algorithms
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 ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
- Majority gates vs. general weighted threshold gates
- Hardness vs randomness
- Theory of majority decision elements
- Discrete Mathematics of Neural Networks
- Pseudorandom Generators for Polynomial Threshold Functions
- Improving exhaustive search implies superpolynomial lower bounds
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
- New algorithms and lower bounds for circuits with linear threshold gates
- Depth Reduction for Composites
- A polynomial restriction lemma with applications
- Quantified derandomization of linear threshold circuits
- On derandomizing algorithms that err extremely rarely
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- A logical calculus of the ideas immanent in nervous activity
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
