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

DOI10.1007/S00224-022-10113-9MaRDI QIDQ6614616FDOQ6614616

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)

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

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)

Cites Work

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

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)