Related references
Note: Only part of the references are listed.Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
Mahdi Cheraghchi et al.
ACM TRANSACTIONS ON COMPUTATION THEORY (2020)
Pseudorandomness from Shrinkage
Russell Impagliazzo et al.
JOURNAL OF THE ACM (2019)
Hardness Magnification for all Sparse NP Languages
Lijie Chen et al.
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019) (2019)
Comparator Circuits over Finite Bounded Posets
Balagopal Komarath et al.
INFORMATION AND COMPUTATION (2018)
Hardness Magnification for Natural Problems
Igor C. Oliveira et al.
2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) (2018)
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching WorstCase Lower Bound
Ilan Komargodski et al.
SIAM JOURNAL ON COMPUTING (2017)
Exponential Lower Bounds for Monotone Span Programs
Robert Robere et al.
2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) (2016)
Mining Circuit Lower Bound Proofs for Meta-Algorithms
Ruiwen Chen et al.
COMPUTATIONAL COMPLEXITY (2015)
Nonuniform ACC Circuit Lower Bounds
Ryan Williams
JOURNAL OF THE ACM (2014)
The Complexity of the Comparator Circuit Value Problem
Stephen A. Cook et al.
ACM TRANSACTIONS ON COMPUTATION THEORY (2014)
IMPROVING EXHAUSTIVE SEARCH IMPLIES SUPERPOLYNOMIAL LOWER BOUNDS
Ryan Williams
SIAM JOURNAL ON COMPUTING (2013)
Share Paper
