Strong average-case lower bounds from non-trivial derandomization

DOI10.1145/3357713.3384279MaRDI QIDQ5145016zbMATH OpenOpenAlexFDO

Authors Lijie Chen, Hanlin Ren

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384279

zbMATH Keywords

derandomizationcircuit complexityaverage-case complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(9)

• Average-case lower bounds for the plurality problem
• Robustness of average-case meta-complexity via pseudorandomness
• Average-case rigidity lower bounds
• MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications
• The value of help bits in randomized and average-case complexity
• Uniform Derandomization from Pathetic Lower Bounds
• Quantified Derandomization: How to Find Water in the Ocean
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• Uniform derandomization from pathetic lower bounds

This page was built for publication: Strong average-case lower bounds from non-trivial derandomization

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