Size-treewidth tradeoffs for circuits computing the element distinctness function
From MaRDI portal
Publication:1702852
DOI10.1007/s00224-017-9814-5zbMath1386.68065OpenAlexW2760836007MaRDI QIDQ1702852
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/
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Satisfiability, branch-width and Tseitin tautologies
- Constant-degree graph expansions that preserve treewidth
- Boolean function complexity. Advances and frontiers.
- A lower bound technique for the size of nondeterministic finite automata
- A Boolean function requiring 3n network size
- Communication complexity
- A partial k-arboretum of graphs with bounded treewidth
- Balancing bounded treewidth circuits
- On the complexity of planar Boolean circuits
- On multi-partition communication complexity
- Graph minors. XIII: The disjoint paths problem
- Square roots of minor closed graph classes
- Local tree-width, excluded minors, and approximation algorithms
- On the Limits of Sparsification
- A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators
- An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Limiting Negations in Bounded Treewidth and Upward Planar Circuits
- Applications of a Planar Separator Theorem
- Communication Complexity and Lower Bounds on Multilective Computations
- The Shrinkage Exponent of de Morgan Formulas is 2
- Branching Programs and Binary Decision Diagrams
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Theory and Applications of Satisfiability Testing
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Size-treewidth tradeoffs for circuits computing the element distinctness function
