On the sparse set conjecture for sets with low density

DOI10.1007/3-540-59042-0_109MaRDI QIDQ4596657zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, M. Hermo

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/97218

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the existence of hard sparse sets under weak reductions
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• scientific article; zbMATH DE number 1008513
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• scientific article; zbMATH DE number 1088261

Cited in

(9)

• Sparse selfreducible sets and nonuniform lower bounds
• Highly sparse sets as additive complements for a prescribed density
• Highly spare sets as additive complements for a prescribed density: an open problem
• Sparse sets, approximable sets, and parallel queries to NP
• Sparse and Lopsided Set Disjointness via Information Theory
• scientific article; zbMATH DE number 3845567 (Why is no real title available?)
• scientific article; zbMATH DE number 5363789 (Why is no real title available?)
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• scientific article; zbMATH DE number 4106273 (Why is no real title available?)

This page was built for publication: On the sparse set conjecture for sets with low density

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