Circuit lower bounds for MCSP from local pseudorandom generators
DOI10.4230/LIPICS.ICALP.2019.39zbMATH Open1499.68101MaRDI QIDQ5091189FDOQ5091189
Authors: Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis 
Publication date: 21 July 2022
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.
constant-depth circuitsbranching programscircuit 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)
Cites Work
- Title not available (Why is that?)
- Randomness is linear in space
- Title not available (Why is that?)
- The Shrinkage Exponent of de Morgan Formulas is 2
- Pseudorandomness from shrinkage
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Circuit minimization problem
- Title not available (Why is that?)
- Power from Random Strings
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- On the average-case complexity of MCSP and its variants
- Title not available (Why is that?)
- Formula lower bounds via the quantum method
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
Cited In (5)
- MCSP is hard for read-once nondeterministic branching programs
- Title not available (Why is that?)
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Circuit lower bounds for MCSP from local 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 Q5091189)
