One-tape Turing machine and branching program lower bounds for MCSP

DOI10.1007/S00224-022-10113-9MaRDI QIDQ6614616zbMATH OpenFDO

Authors Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

Publication date 7 October 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-022-10113-9

zbMATH Keywords

lower boundsKolmogorov complexitypseudorandom generatorsbranching programsminimum circuit size problemone-tape Turing machineshitting set generators

Mathematics Subject Classification ID

Theory of computing (68Qxx) Circuits, networks (94Cxx) Computability and recursion theory (03Dxx)

Recommendations

• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit lower bounds for MCSP from local pseudorandom generators
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• On the average-case complexity of MCSP and its variants
• Hardness magnification near state-of-the-art lower bounds

Cites work

• scientific article; zbMATH DE number 3557235 (Why is no real title available?)
• scientific article; zbMATH DE number 1405644 (Why is no real title available?)
• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• Amplifying lower bounds by means of self-reducibility
• Automata, Languages and Programming
• Beyond natural proofs: hardness magnification and locality
• Boolean function complexity. Advances and frontiers.
• Bounded independence plus noise fools products
• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit minimization problem
• Complexity of computation in finite fields
• Fourier bounds and pseudorandom generators for product tests
• Hardness magnification near state-of-the-art lower bounds
• Learning algorithms from natural proofs
• Limits of minimum circuit size problem as oracle
• Natural proofs
• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• On lower bounds for read-\(k\)-times branching programs
• On the (non) NP-hardness of computing circuit complexity
• On the NP-Completeness of the Minimum Circuit Size Problem.
• On the average-case complexity of MCSP and its variants
• One-tape, off-line Turing machine computations
• Power from Random Strings
• Pseudorandomness
• Pseudorandomness from shrinkage
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• The time-precision tradeoff problem on on-line probabilistic Turing machines
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

This page was built for publication: One-tape Turing machine and branching program lower bounds for MCSP

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