Hardness of Sparse Sets and Minimal Circuit Size Problem

2020/03/02 by Bin Fu, Fu, Bin
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2003.00669

openalex publication_date 2020/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a polynomial method on finite fields to amplify the hardness of spare sets in nondeterministic time complexity classes on a randomized streaming model. One of our results shows that if there exists a 2^n^o(1)-sparse set in NTIME(2^n^o(1)) that does not have any randomized streaming algorithm with n^o(1) updating time, and n^o(1) space, then NEXP\not=BPP, where a f(n)-sparse set is a language that has at most f(n) strings of length n. We also show that if MCSP is ZPP-hard under polynomial time truth-table reductions, then EXP\not=ZPP.

Related

• Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
• Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
• New Techniques for Constructing Rare-Case Hard Functions
• Symmetric Exponential Time Requires Near-Maximum Circuit Size
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials