Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
From MaRDI portal
Publication:5053073
DOI10.1145/3404860zbMath1499.68102OpenAlexW3044440032MaRDI QIDQ5053073
Dimitrios Myrisiotis, Valentine Kabanets, Mahdi Cheraghchi, Zhenjian Lu
Publication date: 5 December 2022
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3404860
branching programsconstant-depth circuitscircuit lower boundsde Morgan formulaslocal PRGsminimum circuit-size problem (MCSP)pseudorandom generators (PRGs)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Algorithms and lower bounds for comparator circuits from shrinkage, Paradigms for Unconditional Pseudorandom Generators, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization