Sparse sets, approximable sets, and parallel queries to NP

DOI10.1016/S0020-0190(99)00008-3MaRDI QIDQ294651zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Jacobo Torán

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019099000083?np=y

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1304328
• On reductions of NP sets to sparse sets
• Approximable sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cites work

• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1256688 (Why is no real title available?)
• scientific article; zbMATH DE number 1306869 (Why is no real title available?)
• scientific article; zbMATH DE number 1335874 (Why is no real title available?)
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• Approximable sets
• Computing functions with parallel queries to NP
• NP is as easy as detecting unique solutions
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the existence of hard sparse sets under weak reductions
• On the sparse set conjecture for sets with low density
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Polynomial-Time Membership Comparable Sets
• Some consequences of non-uniform conditions on uniform classes
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• Upper bounds for the complexity of sparse and tally descriptions

Cited in

(5)

• Sparse dominance queries for many points in optimal time and space
• Approximable sets
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• scientific article; zbMATH DE number 1107624 (Why is no real title available?)

This page was built for publication: Sparse sets, approximable sets, and parallel queries to NP

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