Recommendations
- The Complexity of Decision Versus Search
- With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
- Sharply bounded alternation and quasilinear time
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Bounded queries to SAT and the Boolean hierarchy
Cites work
- scientific article; zbMATH DE number 3936518 (Why is no real title available?)
- scientific article; zbMATH DE number 4101157 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 48941 (Why is no real title available?)
- scientific article; zbMATH DE number 107774 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 4126690 (Why is no real title available?)
- scientific article; zbMATH DE number 512828 (Why is no real title available?)
- scientific article; zbMATH DE number 1142308 (Why is no real title available?)
- scientific article; zbMATH DE number 3992933 (Why is no real title available?)
- scientific article; zbMATH DE number 4114007 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate
- A taxonomy of complexity classes of functions
- A taxonomy of problems with fast parallel algorithms
- Absolute results concerning one-way functions and their applications
- Bounded queries to SAT and the Boolean hierarchy
- Bounded query classes and the difference hierarchy
- Classes of bounded nondeterminism
- Complete sets and the polynomial-time hierarchy
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Fast decoding of codes from algebraic plane curves
- Linear time transformations between combinatorial problems
- NP is as easy as detecting unique solutions
- Natural Self-Reducible Sets
- Nondeterminism within $P^ * $
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- On O(Tlog T) reduction from RAM computations to satisfiability
- On helping by robust oracle machines
- On truth-table reducibility to SAT
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- PP is as Hard as the Polynomial-Time Hierarchy
- Polynomial terse sets
- Power indices and easier hard problems
- Probabilistic Algorithms in Finite Fields
- Processor-efficient exponentiation in finite fields
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Relations Among Complexity Measures
- Relativization of questions about log space computability
- Relativized circuit complexity
- Relativized isomorphisms of NP-complete sets
- Robust algorithms: a different approach to oracles
- Rudimentary Predicates and Relative Computation
- Satisfiability Is Quasilinear Complete in NQL
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Some observations on the probabilistic algorithms and NP-hard problems
- Terse, superterse, and verbose sets
- The complexity of optimization problems
- The polynomial-time hierarchy
- Time bounded random access machines
- Two-Tape Simulation of Multitape Turing Machines
- Universal classes of hash functions
Cited in
(10)- Sharply bounded alternation and quasilinear time
- Algorithmic theory of free solvable groups: randomized computations.
- Hardness and hierarchy theorems for probabilistic quasi-polynomial time
- Is Valiant-Vazirani's isolation probability improvable?
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Observations on complete sets between linear time and polynomial time
- Amplifying circuit lower bounds against polynomial time, with applications
- Nonerasing, counting, and majority over the linear time hierarchy
- Magnus embedding and algorithmic properties of groups \(F/N^{(d)}\)
This page was built for publication: On quasilinear-time complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672330)
