One-tape Turing machine and branching program lower bounds for MCSP
From MaRDI portal
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?)
- 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
- Fourier bounds and pseudorandom generators for product tests
- Hardness magnification for all sparse NP languages
- Hardness magnification for natural problems
- Hardness magnification near state-of-the-art lower bounds
- Learning algorithms from natural proofs
- Limits of minimum circuit size problem as oracle
- Natural proofs
- Non-black-box worst-case to average-case reductions within NP
- 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
- Pseudorandom generators for read-once branching programs, in any order
- Pseudorandomness from shrinkage
- 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 Q7231546)
