Size-treewidth tradeoffs for circuits computing the element distinctness function

DOI10.1007/S00224-017-9814-5MaRDI QIDQ1702852zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira

Publication date 1 March 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/5757/

zbMATH Keywords

circuit complexityelement distinctnesssuper-linear 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

Cites work

• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 2187726 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A Boolean function requiring 3n network size
• A generalization of Spira's theorem and circuits with small segregators or separators
• A lower bound technique for the size of nondeterministic finite automata
• A partial k-arboretum of graphs with bounded treewidth
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• Applications of a Planar Separator Theorem
• Balancing bounded treewidth circuits
• Boolean function complexity. Advances and frontiers.
• Branching Programs and Binary Decision Diagrams
• Communication Complexity and Lower Bounds on Multilective Computations
• Communication complexity
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Constant-degree graph expansions that preserve treewidth
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Graph minors. XIII: The disjoint paths problem
• Limiting negations in bounded treewidth and upward planar circuits
• Local tree-width, excluded minors, and approximation algorithms
• On multi-partition communication complexity
• On the complexity of planar Boolean circuits
• On the limits of sparsification
• Satisfiability, branch-width and Tseitin tautologies
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Square roots of minor closed graph classes
• The Shrinkage Exponent of de Morgan Formulas is 2
• Theory and Applications of Satisfiability Testing
• Width-parametrized SAT: time-space tradeoffs

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 Q1702852)