Size-treewidth tradeoffs for circuits computing the element distinctness function

DOI10.1007/S00224-017-9814-5zbMATH Open1386.68065OpenAlexW2760836007MaRDI QIDQ1702852FDOQ1702852

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/

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

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)

Cites Work

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

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)