scientific article; zbMATH DE number 7378395
From MaRDI portal
Publication:5005182
DOI10.4230/LIPIcs.MFCS.2018.78MaRDI QIDQ5005182
Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan
Publication date: 4 August 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (2)
Front Matter, Table of Contents, Preface, Conference Organization ⋮ Average-case rigidity lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Randomness-efficient sampling within NC\(^{1}\)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Hardness vs randomness
- On ACC
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Certifying polynomials for AC^0(parity) circuits, with applications
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Nonuniform ACC Circuit Lower Bounds
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Expander graphs and their applications
- Improved Pseudorandom Generators for Depth 2 Circuits
- Simple Constructions of Almost k-wise Independent Random Variables
- A Chernoff Bound for Random Walks on Expander Graphs
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Beating Brute Force for Systems of Polynomial Equations over Finite Fields
- New algorithms and lower bounds for circuits with linear threshold gates
- Analysis of Boolean Functions
- Short PCPs with Projection Queries
- Learning algorithms from natural proofs
This page was built for publication:
