Size-treewidth tradeoffs for circuits computing the element distinctness function

DOI10.4230/LIPICS.STACS.2016.56MaRDI QIDQ4601908zbMATH OpenFDO

Authors Mateus de Oliveira Oliveira

Publication date 24 January 2018

zbMATH Keywords

treewidthelement distinctnessnonlinear lower bounds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Size-treewidth tradeoffs for circuits computing the element distinctness function
• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• Balancing Bounded Treewidth Circuits
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
• Balancing bounded treewidth circuits

Cited in

(3)

• A near-quadratic lower bound for the size of quantum circuits of constant treewidth
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Two time-space tradeoffs for element distinctness

This page was built for publication: Size-treewidth tradeoffs for circuits computing the element distinctness function

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