Circuit lower bounds for MCSP from local pseudorandom generators

DOI10.1145/3404860MaRDI QIDQ5053073zbMATH OpenOpenAlexFDO

Authors Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

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

zbMATH Keywords

branching programscircuit lower boundsconstant-depth circuitsde Morgan formulaslocal PRGsminimum circuit-size problem (MCSP)pseudorandom generators (PRGs)

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Circuit lower bounds for MCSP from local pseudorandom generators
• On the average-case complexity of MCSP and its variants
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the (non) NP-hardness of computing circuit complexity
• On the NP-Completeness of the Minimum Circuit Size Problem.

Cited in

(7)

• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Circuit lower bounds for MCSP from local pseudorandom generators
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• Algorithms and lower bounds for comparator circuits from shrinkage
• Paradigms for Unconditional Pseudorandom Generators
• One-tape Turing machine and branching program lower bounds for MCSP

This page was built for publication: Circuit lower bounds for MCSP from local pseudorandom generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5053073)