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

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

Yuichi Yoshida, Shuichi Hirahara, Dimitrios Myrisiotis, Mahdi Cheraghchi

Publication date: 7 October 2024

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

zbMATH Keywords

Kolmogorov complexitylower boundspseudorandom 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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity of computation in finite fields
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Boolean function complexity. Advances and frontiers.
• The time-precision tradeoff problem on on-line probabilistic Turing machines
• On lower bounds for read-\(k\)-times branching programs
• Pseudorandomness
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Circuit minimization problem
• Amplifying lower bounds by means of self-reducibility
• Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
• Simple Constructions of Almost k-wise Independent Random Variables
• A Pseudorandom Generator from any One-way Function
• Bounded Independence Plus Noise Fools Products
• Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound Method
• Fourier bounds and pseudorandom generators for product tests
• Hardness magnification near state-of-the-art lower bounds
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• Pseudorandomness from Shrinkage
• On the NP-Completeness of the Minimum Circuit Size Problem.
• Learning algorithms from natural proofs
• Automata, Languages and Programming
• Power from Random Strings
• One-tape, off-line Turing machine computations
• Natural proofs

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)