Size-treewidth tradeoffs for circuits computing the element distinctness function

DOI10.4230/LIPICS.STACS.2016.56zbMATH Open1380.68205MaRDI QIDQ4601908FDOQ4601908

Authors: Mateus de Oliveira Oliveira 

Publication date: 24 January 2018

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

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)

Cited In (3)

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

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)