On the Limits of Sparsification

DOI10.1007/978-3-642-31594-7_65zbMath1272.68161OpenAlexW1556385097MaRDI QIDQ2843300

Srikanth Srinivasan, Rahul Santhanam

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/17928327/Santhanam_Srinivasan_2012_On_the_Limits_of_Sparsification.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Computational complexity of distance edge labeling ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Unnamed Item ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction

This page was built for publication: On the Limits of Sparsification